二叉树的遍历

二叉树的遍历有多种方式，主要包括：

1. 前序遍历（Pre-order Traversal）：根节点 -> 左子树 -> 右子树
2. 中序遍历（In-order Traversal）：左子树 -> 根节点 -> 右子树
3. 后序遍历（Post-order Traversal）：左子树 -> 右子树 -> 根节点
4. 层序遍历（Level-order Traversal）：按层级顺序遍历

前序遍历

function preOrderTraversal(node) {
  if (node === null) return;
  console.log(node.value);
  preOrderTraversal(node.left);
  preOrderTraversal(node.right);
}

preOrderTraversal(root);

中序遍历

function inOrderTraversal(node) {
  if (node === null) return;
  inOrderTraversal(node.left);
  console.log(node.value);
  inOrderTraversal(node.right);
}

inOrderTraversal(root);

后序遍历

function postOrderTraversal(node) {
  if (node === null) return;
  postOrderTraversal(node.left);
  postOrderTraversal(node.right);
  console.log(node.value);
}

postOrderTraversal(root);

层序遍历

function levelOrderTraversal(node) {
  if (node === null) return;
  const queue = [node];
  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.value);
    if (current.left !== null) queue.push(current.left);
    if (current.right !== null) queue.push(current.right);
  }
}

levelOrderTraversal(root);

总结

总结

二叉树是一种重要的数据结构，具有广泛的应用。通过链式存储和顺序存储，我们可以有效地表示和操作二叉树。二叉树的遍历方法有多种，包括前序遍历、中序遍历、后序遍历和层序遍历，每种方法都有其特定的应用场景。希望这些示例能帮助你更好地理解二叉树及其定义。如果有任何问题，请随时提问！