顺序和后顺序中的二叉树 [英] Binary Tree from inorder and postorder

问题描述

我刚刚开始研究二叉树.给定有序和后序或有序和前序，是否有一种算法可以找出二叉树结构?我一直在尝试手动进行操作，但始终无法正确执行.例如-这两个是对给定树的有效Inorder和Postorder遍历:

I have just started studying Binary Tree. Is there an algorithm to find out the binary tree structure,given the Inorder and Postorder OR Inorder and Preorder? I have been trying to do it manually,but it never comes out correct.For eg.-These two are valid Inorder and Postorder traversal of a given tree:

顺序:D B F E A G C L J H K 邮购:D F E B G L J K H C A

Inorder: D B F E A G C L J H K Postorder : D F E B G L J K H C A

很明显，A是根，因为它是Postorder中的最后一个元素.现在在Inorder中查看，左子树变为:{D B F E}，右子树变为:{G C L J H K}.右子树的根将是前置元素中的倒数第二个元素，即C.我现在可以进一步分割右子树(以C为根)，将{G}设为右子树，将{L J H K}设为左.因此，我有这样的结构:

Clearly A is the root as it is the last element in Postorder. Now looking in Inorder,the left subtree becomes: {D B F E} and right subtree becomes: {G C L J H K}. The root of right subtree would be the second last element in preorder i.e C. I can now further divide the right subtree(with C as root), giving {G} as right subtree and {L J H K} as left. Therefore I have this structure:

                               A
                                \
                                 C
                                /  
                               G

但是，无论我采用哪种算法，接下来的算法似乎对于不同的树都具有不同的作用.有人请解释.

But,whatever algorithm I apply,next seems to work differently for different trees . Someone please explain.

推荐答案

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

If I understand what your asking, your trying to reverse engineer the underlying structure for a given binary tree search algorithm given the raw data in it's pre and post state. If this is the case you could be down a difficult road since although the basic algorithm is the same, there could be nuances to it depending on the developer that build the algorithm since in practice it is often the case the developers do not build a pure implementation of these algorithms.

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

If your just trying to get a better understanding of binary trees, this may explain it a little better: http://www.youtube.com/watch?v=ZkH3SSPwcwI

这篇关于顺序和后顺序中的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！