algorithm - 来自有序和级别顺序遍历的二叉树？

Question

我们能否证明可以从中序和层序遍历中明确构造一棵二叉树？

我正在考虑通过对级别数进行归纳来证明。

基本情况:具有 1 层或 2 层的树。这些情况很清楚。

假设这适用于具有 l 层的树。即:可以通过中序遍历和层序遍历明确地构造出 l 层的二叉树。

归纳案例:证明这适用于具有 l+1 层的树。不清楚在这种情况下如何进行。任何帮助将不胜感激。

Answer 1

我已经在我的博客上给出了这个教程 a) - INORDER Traversal-POSTORDER遍历

或

b) -INORDER 遍历 -PREORDER遍历

我们通常会收到这样的问题:-

根据树的遍历创建二叉树

1)

Inorder:   E  A  C  K  F  H  D  B  G
Preorder:  F  A  E  K  C  D  H  G  B

这里最重要的想法是永远记住:-

In PREorder FIRST element is ROOT of the tree

In POSTorder LAST element is ROOT of the tree

我希望你明白了:P

即考虑 1) 问题

1) 按顺序:E A C K F H D B G 预购:F A E K C D H G B

F 是根

E A C K 将转到根的左子树

H D B G 会去根的右子树

Step 1)

现在我们知道哪个是 Root 所以...

                     F
                   /  \
        ( E A C K)      (H D B G) 


Step 2)

现在对于左子树我们有Inorder 中的 E A C K 和 Preorder 中的相同字母 A E K C

即

 Inorder   E A C K
 Preorder A E K C

现在再次找到 A 作为根，所以现在树是

                     F
                   /   \
                  A      (H D B G) 
                /  \
               E    (C K)


Step 3)

现在字母是

Inorder   C K
Preorder  K C

所以现在树是

                           F
                         /   \
                        A     (H D B G) 
                      /  \
                     E    K
                         /
                        C

同样的过程可以在根F的右子树上完成

对于后序，我们必须找到 Root 作为遍历中的最后一个元素....

创辉版或者这个可以看这里http://bloggerplugnplay.blogspot.in/2012/11/construction-of-binary-tree-from.html :P