预订到订单后的遍历

Question

如果二叉搜索树的预订遍历是6,2,1,4,3,7,10,9,11,那么如何获得后序遍历？

Answer 1

您将获得树的预顺序遍历,该结构通过以下方式构造:输出,遍历左,遍历右.

由于后序遍历来自BST,您可以通过对数字进行排序,从后序遍历中推导出有序遍历(遍历左,输出,遍历右).在您的示例中,有序遍历为1,2,3,4,6,7,9,10,11.

从两次遍历中,我们可以构造原始树.让我们使用一个更简单的例子:

• 预购:2,1,4,3
• 有序:1,2,3,4

预顺序遍历为树提供了根2.顺序遍历告诉我们1落入左子树,3,4落入右子树.左子树的结构是微不足道的,因为它包含单个元素.通过从原始预订遍历中获取该子树中的元素的顺序来推导出右子树的预订遍历:4,3.由此我们知道右子树的根是4并且从有序遍历(3,4)我们知道3落入左子树.我们的最终树看起来像这样:

  2
 / \
1   4
   /
  3

通过树结构,我们可以通过遍历树来获得后序遍历:遍历左,遍历右,输出.对于此示例,后序遍历为1,3,4,2.

概括算法:

1. 预先遍历遍历中的第一个元素是树的根.小于根的元素构成左子树.大于根的元素构成右子树.
2. 使用步骤1找到左子树和右子树的结构,其中包含按照它们在原始预订遍历中出现的顺序放置的子树中的元素组成的预先遍历遍历.
3. 在后序中遍历生成的树以获得与给定的预订遍历相关联的后序遍历.

使用上述算法,与问题中的预先遍历相关联的后序遍历是:1,3,4,2,9,11,10,7,6.将其留作练习.

Answer 2

预订 =按当前节点的顺序输出二叉树的值,然后输出左子树,然后输出右子树.

后序 =按左子树的顺序输出二叉树的值,然后输出右子树,即当前节点.

在二叉搜索树中,左子树中所有节点的值小于当前节点的值; 和相似的正确子树.因此,如果您知道二叉搜索树的预订转储的开始(即其根节点的值),您可以轻松地将整个转储分解为根节点值,左子树节点的值以及值右子树的节点.

要按顺序输出树,应用递归和输出重新排序.这项任务留给了读者.