何时使用预订、后订和顺序二叉查找树遍历策略

我最近意识到，虽然在我的生活中已经使用了大量的 BST 的，我甚至从来没有考虑使用任何东西，但 Inorder 遍历(虽然我知道，也知道它是多么容易适应使用前/后序遍历程序)。

意识到这一点之后，我拿出了一些旧的数据结构教科书，寻找预先排序和后排序遍历有用性背后的原因——尽管它们没有说太多。

有哪些例子可以说明什么时候应该实际使用 preorder/postorder? 什么时候它比 in-order 更有意义？

86550 次浏览
小开

如果我想简单地以线性格式打印出树的分层格式，我可能会使用预排序遍历。例如:

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

在很多地方，你会发现这种差异起到了真正的作用。

我要指出的一个很好的例子是编译器的代码生成:

x := y + 32

为此生成代码的方法是(当然是比较天真的)首先生成将 y 加载到寄存器中的代码，然后将32加载到寄存器中，然后生成一条指令将这两者相加。因为在你操作它之前，有些东西必须在一个寄存器中(让我们假设，你总是可以做常数操作数，但是无论如何) ，你必须这样做。

通常，您可以得到的这个问题的答案基本上归结为: 当处理数据结构的不同部分之间存在某种依赖关系时，差异真的很重要。当打印元素时，当生成代码时(当然，外部状态决定了代码的不同，你也可以一元地查看) ，或者当在结构上进行其他类型的计算时，根据先处理的子结构进行计算时，你会看到这一点。

小开

前序和后序分别与自顶向下和自底向上递归算法有关。如果您希望以迭代的方式在二叉树上编写一个给定的递归算法，那么这就是您实际要做的。

进一步观察，前序和后序序列一起完全指定手边的树，产生一个紧凑的编码(至少对于稀疏树)。

小开
最佳答案

何时使用预订、按订单和后订单遍历策略

在理解在什么情况下对二叉树使用预排序、顺序和后排序之前，必须准确地理解每个遍历策略是如何工作的。以下面的树为例。

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

enter image description here

预订遍历 :

摘要: 从根(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
}
小开

用于创建树的副本。例如，如果要创建树的副本，请将节点放在具有预先排序遍历的数组中。然后对数组中的每个值在新树上执行 插入操作。你最终会得到一个原始树的副本。

In-order: : 用于获取 BST 中按非递减顺序排列的节点值。

Post-order: : 用于从叶子到根删除树

小开

In-order : 从任何解析树获取原始输入字符串，因为解析树遵循运算符的优先级。最深的子树首先穿越。因此，父节点中的运算符相对于子树中的运算符的优先级较低。

小开
  • 如果给定的二叉树是一个二叉查找树，那么遍历将按排序顺序打印出节点。举个例子，如果你需要找到二叉查找树中的 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
  • 在 Postorder 中，在递归访问当前节点之前，我们先访问左子树和右子树。例如，如果给定的二叉树是高度平衡的，这是一个二叉树，其中每个节点的左右子树的高度相差不超过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]
  • 在 Preorder 中，我们首先访问当前节点，然后转到左边的子树。在接触到左边子树的每个节点之后，我们将向右边子树移动并以类似的方式访问。一个例子是从预订和顺序遍历构造二叉树。为了构造一棵树，我们必须首先处理节点，然后构建它的左和右
      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

提交答案