何时使用先序、后序和中序二叉搜索树遍历策略

Question

我最近意识到，尽管我在生活中经常使用二叉搜索树（BST），但我从未考虑过除中序遍历以外的其他遍历方式（虽然我知道如何轻松地调整程序以使用前序或后序遍历）。

在意识到这一点后，我拿出了一些旧的数据结构教科书，寻找前序遍历和后序遍历有用性背后的原因-不过他们没有说太多。

有哪些实际场景下需要使用先序/后序遍历呢？什么情况更适合使用先序/后序而不是中序遍历？

- John Humphreys

Answer 1

何时使用先序、中序和后序遍历策略

在了解何时使用二叉树的先序、中序和后序遍历之前，您必须了解每种遍历策略的工作原理。以下以该树为例：

树的根节点为7，最左边的节点是0，最右边的节点是10。

先序遍历：

概述：从根节点（7）开始，以最右侧节点（10）结束。

遍历顺序：7、1、0、3、2、5、4、6、9、8、10

中序遍历：

概述：从最左边的节点（0）开始，以最右边的节点（10）结束。

遍历顺序：0、1、2、3、4、5、6、7、8、9、10

后序遍历：

概述：从最左边的节点（0）开始，以根节点（7）结束。

遍历顺序：0、2、4、6、5、3、1、8、10、9、7

何时使用先序、中序或后序遍历？

程序员选择的遍历策略取决于正在设计的算法的特定需求。目标是速度，因此选择可以最快获取所需节点的策略。

1. 如果您知道需要在检查任何叶子之前探索根节点，则选择先序遍历，因为您将在所有叶子之前遇到所有根。

2. 如果您知道需要在任何节点之前探索所有叶子，则选择后序遍历，因为您不会浪费时间检查寻找叶子的根。

3. 如果您知道树中存在节点的内在顺序，并且希望将树展平回其原始顺序，则应使用中序遍历。树将以创建它的相同方式被展平。 先序或后序遍历可能无法将树解开回创建它的序列。

用于先序、中序和后序遍历的递归算法（C ++）：

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

- Eric Leschinski

---

非递归遍历怎么样？在我看来，与中序遍历/后序遍历相比，以前序遍历的方式非递归遍历树要容易得多，因为它不需要返回到先前的节点。 - bluenote10

@bluenote10 你能详细说明你的意思吗？在预订中，您仍然需要“返回”到节点以处理其右子节点，而在处理完其左子节点后。当然，您可以使用“尚未访问的节点”队列，但这实际上只是将隐式（堆栈）存储与显式队列进行交换。在所有遍历方法中，都必须处理左右子节点，这意味着在完成其中一个之后，您必须“返回”到父级。 - Joshua Taylor

@JoshuaTaylor：是的，它们都属于相同的复杂度类，但如果你看一下典型的实现，后序遍历可能会更加棘手。 - bluenote10

预订遍历按照插入的顺序给出节点的值。如果您想创建树的副本，则需要以这种方式遍历源树。 中序遍历给出排序后的节点值。 至于后序遍历，您可以使用此方法删除整个树，因为它首先访问叶节点。 - albin

我认为这是正确的，即使树没有正确排序，我的意思是如果序列一开始没有排序，那么按顺序排列也不会给出排序后的序列。 - CodeYogi

Answer 2

预序遍历：用于创建树的副本。例如，如果您想要创建一棵树的复制品，请使用预序遍历将节点放入数组中。然后对数组中的每个值执行插入操作，以在新树上执行此操作。最终将得到原始树的副本。

中序遍历：用于按非递减顺序获取BST中节点的值。

后序遍历：用于从叶子到根删除树。

- Viraj Nimbalkar

---

这是一个很好、简洁的回答，帮助我理解了先序遍历和后序遍历的使用情况。不过，由于问题直接提到了这一点，可能很显然，但请注意这只适用于二叉搜索树，并不一定适用于普通的二叉树。例如，在复制普通二叉树时不能保证使用先序遍历，因为在复制过程中插入逻辑将无法正常工作。 - markckim

按顺序：为了按“非递减”顺序获取节点的值 - 而非“非增”的顺序。 - rahil008

Answer 3

如果我想要以线性格式打印树的层次结构，我可能会使用先序遍历。例如：

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

- Oliver Charlesworth

---

或者在 GUI 应用程序中的 TreeView 组件中。 - svick

Answer 4

先序遍历和后序遍历分别与自顶向下和自底向上的递归算法相关。如果您想以迭代方式编写给定的二叉树递归算法，则基本上就是这样做。

此外，请注意，先序遍历和后序遍历序列一起完全指定了手头的树，从而产生了紧凑的编码（对于稀疏树至少如此）。

- Raphael

---

我认为您尝试表达一些重要的内容，请问能否解释一下前半部分？ - CodeYogi

@CodeYogi 你需要解释什么具体内容？ - Raphael

"Pre-和post-order与自顶向下和自底向上的递归算法有关。我想你想说的是，在第一种情况下，在调用任何递归方法之前处理节点，而在后一种情况下则相反，对吗？" - CodeYogi

@CodeYogi 是的，基本上是这样。 - Raphael

Answer 5

有很多情况下，这种差异会发挥真正的作用。

我要指出一个很好的例子，那就是编译器的代码生成。考虑以下语句：

x := y + 32

你生成代码的方法是（当然是一种朴素的方法），首先生成将y加载到寄存器中的代码，然后加载32到寄存器中，并生成一个加法指令。因为在操作之前必须将某些东西放入寄存器中（假设可以始终进行常量操作），所以必须这样做。

总的来说，你可以得出的答案基本上归结为这个问题：当处理数据结构的不同部分之间存在某种依赖关系时，差异真的很重要。 当打印元素，生成代码（外部状态会使差异，当然也可以将其视为单子），或者在涉及依赖于先处理儿童的计算的结构上进行其他类型的计算时，会看到这一点。

- Kristopher Micinski

Answer 6

• 如果给定的二叉树是二叉查找树，中序遍历会按顺序打印出节点。例如，如果您需要在二叉查找树中找到第k个最小元素：

      class Solution:
        def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
            res=None
            def inorder(node):
                if not node:
                    return
                # in bst this is the smallest value
                inorder(node.left)
                # python determines the scope at creation time of the function
                nonlocal k
                k-=1
                if k==0:
                    nonlocal res
                    res=node.val
                    return
                inorder(node.right)
            inorder(root)
            return res

• 在后序遍历中，我们在递归中访问左子树和右子树，然后访问当前节点。一个例子是，如果给定的二叉树是高度平衡的，即每个节点的左右子树的高度差不超过1。在这种情况下，我们必须获取左子树和右子树的高度，然后将结果传递给父节点。

      class Solution:
        def isBalanced(self, root: Optional[TreeNode]) -> bool:
            def post_order(root):
                # leaf node is balanced
                if not root:
                    # we carry the height of each subtree
                    return [True,0]
                # with recursion, we start from bottom, so we do not have repetitive work
                left,right=post_order(root.left),post_order(root.right)
                # if any of the subtree return false, then we know entire tree is not balanced
                balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
                # 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
                return [balanced,1+max(left[1],right[1])]
            return post_order(root)[0]

• 在先序遍历中，我们首先访问当前节点，然后进入左子树。在触摸左子树的每个节点后，我们将向右子树移动，并以类似的方式访问。一个例子是从先序遍历和中序遍历构造二叉树。为了构造一棵树，我们必须先处理节点，然后构建其左右子树。

      class Solution:
        def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
            if not preorder or not inorder:
                return None
            # first element of preorder is root
            root=TreeNode(preorder[0])
            # mid value in inorder gives us root. left values of root will be the left subtree, right values will be the right subtree
            # mid tells us how many elements we want from left subtree and howmany for right subtree
            mid = inorder.index(preorder[0])
            # we took 1 out of each array. preorder will not include the first, inorder will not include the mid value
            root.left=self.buildTree(preorder[1:mid+1],inorder[:mid])
            root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
            return root

- Yilmaz

Answer 7

顺序：为了从任何解析树中获取原始输入字符串，因为解析树遵循运算符的优先级。首先遍历最深的子树。因此，父节点中的运算符优先级低于子树中的运算符。

- UNREAL