中序遍历是如何遍历的

什么是中序遍历？

中序遍历是二叉树遍历的一种方法，其遍历顺序是从左子树根节点开始，然后是根节点，最后是右子树根节点。中序遍历的方法可以用递归或栈的方式实现。

如何使用递归实现中序遍历？

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

// 例子1
inorder(root);

从上面的代码可以看出，中序遍历的递归方法首先检查当前节点是否为NULL，如果不是NULL，它将递归遍历左子树，访问当前节点，然后递归遍历右子树。

如何使用栈实现中序遍历？

function inorder(node){
  var stack = [];
  var current = node;

  while(stack.length > 0 || current !== null){
    while(current !== null){
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    console.log(current.value);
    current = current.right;
  }
}

// 例子2
inorder(root);

从上面的代码可以看出，中序遍历的栈方法首先将当前节点的左子节点推入堆栈，然后持续迭代到最左侧节点并将其推入堆栈。然后从堆栈中弹出节点，将其值添加到输出数组中，并检查当前节点的右子树。

中序遍历的应用场景是什么？

中序遍历可以用于对二叉搜索树进行排序。由于根据二叉搜索树的定义，左子树节点的值小于根节点的值，右子树节点的值大于根节点的值，所以中序遍历二叉搜索树会以升序序列输出。

同时，中序遍历也可以用于查找二叉搜索树中的中间值或某一个范围之间的值。例如，当需要查找第k小的元素时，可以使用中序遍历并记录每个节点的排名，到达第k个节点时停止遍历并返回该节点的值。