2

我刚开始研究二叉树。给定中序和后序或中序和前序，是否有算法可以找出二叉树结构？我一直在尝试手动操作，但它永远不会正确。例如，这两个是给定树的有效 Inorder 和 Postorder 遍历：

订购：DBFEAGCLJHK 后订购：DFEBGLJKHCA

显然 A 是根，因为它是 Postorder 中的最后一个元素。现在按顺序看，左子树变为：{DBFE}，右子树变为：{GCLJHK}。右子树的根将是前序中的倒数第二个元素，即 C。我现在可以进一步划分右子树（以 C 为根），将 {G} 作为右子树，将 {LJHK} 作为左子树。因此我有这个结构：

                               A
                                \
                                 C
                                /  
                               G

但是，无论我应用什么算法，next 似乎对不同的树都有不同的工作方式。有人请解释一下。

4

2 回答 2

1

如果我理解您的要求，那么您尝试对给定二叉树搜索算法的底层结构进行逆向工程，因为它的原始数据处于前后状态。如果是这种情况，您可能会走上一条艰难的道路，因为尽管基本算法是相同的，但可能会有细微差别，具体取决于构建算法的开发人员，因为在实践中，开发人员通常不会构建纯粹的这些算法的实现。

如果您只是想更好地理解二叉树，这可能会更好地解释它：http ://www.youtube.com/watch?v=ZkH3SSPwcwI

于 2012-09-23T22:47:55.407 回答
0

让中序和前序遍历分别在数组 iorder 和 porder 中给出。

构建树的函数将由 buildTree(i,j,k) 表示，其中 i,j 指的是要查看的中序数组的范围，k 是前序数组中的位置。

初始调用将是 buildTree(0,n-1,0)

该算法有以下步骤：

  1. 从头开始遍历。第一个节点是根，然后我们有左子树，然后是右子树。创建一个以此为元素的节点。

  2. 在 iorder 数组中搜索节点。假设它在 x 处找到。递减 k。k 指的是我们当前所在的 porder 数组中的位置。k 必须通过引用传递。

  3. 最后用递归调用的返回值填充左孩子和右孩子 left child = buildTree(i,x-1,k) right child = buildTree(x+1,j,k)

  4. 最后返回节点

PS：得到上述算法接受的代码

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=477

于 2012-09-27T19:24:13.990 回答