中序遍历是怎么遍历的

什么是中序遍历

中序遍历（In-order traversal）是二叉树遍历的一种方法，顾名思义，它的遍历顺序是从左子树开始，到根节点，再到右子树。在中序遍历中，每个节点的左子树都会被先遍历，其次才是节点本身和其右子树。

中序遍历所得的节点序列通常可以用于搜索二叉树，即判断二叉树上某个节点是否存在。

递归实现中序遍历

算法思路

递归实现中序遍历的算法思路如下：

首先遍历左子树

接着访问根节点

最后遍历右子树

代码实现

以下代码实现的是使用递归实现中序遍历的过程：

// Node定义

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
// 中序遍历递归实现
function inOrderTraversal(root) {
  if (root === null) {
    return;
  }
  inOrderTraversal(root.left);
  console.log(root.value);
  inOrderTraversal(root.right);
}
// 示例使用
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);
const node5 = new Node(5);
node3.left = node1;
node3.right = node5;
node1.right = node2;
node5.left = node4;
inOrderTraversal(node3); // 结果为1, 2, 3, 4, 5

迭代实现中序遍历

算法思路

使用迭代实现中序遍历的算法思路如下：

从根节点开始，将当前节点压入栈中。

如果当前节点有左子节点，将左子节点压入栈中，并移到左子节点。

如果当前节点没有左子节点，弹出当前节点并访问之，然后将当前节点更新为右子节点。

重复上述过程直到当前节点为空且栈中元素为空。

代码实现

以下代码实现的是使用迭代实现中序遍历的过程：

// Node定义

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
// 中序遍历迭代实现
function inOrderTraversal(root) {
  if (root === null) {
    return;
  }
  const stack = [];
  let current = root;
  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    console.log(current.value);
    current = current.right;
  }
}
// 示例使用
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);
const node5 = new Node(5);
node3.left = node1;
node3.right = node5;
node1.right = node2;
node5.left = node4;
inOrderTraversal(node3); // 结果为1, 2, 3, 4, 5

总结

本文介绍了中序遍历的算法和实现方法。中序遍历是一种将二叉树中的节点按照一定顺序遍历的方式。在实际使用中，可以根据需要选择递归或迭代方式来实现中序遍历。在递归实现过程中，需要理解递归函数的回溯机制；在迭代实现过程中，则需要加深对栈的理解。