来自有序和水平顺序遍历的二叉树？

Question

我们能否证明可以从其有序和级别顺序遍历中明确地构造二叉树？

我正在考虑一个关于级别数量的归纳证明.

基本情况:1或2级的树木.这些案件很清楚.

假设这适用于具有l级别的树.也就是说:可以从其有序和水平顺序遍历中明确地构造具有l级的二叉树.

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

Answer 1

我在我的博客上给了这个教程a) - INORDER Traversal -POSTORDER Traversal

要么

b)-INORDER Traversal -PREORDER Traversal

我们通常会收到以下问题: -

从以下树遍历创建Binery树

1)

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

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

在PREorder FIRST元素是树的ROOT

在POSTorder中, LAST元素是树的ROOT

我希望你明白了:P

即考虑1)问题

1)Inorder:EACKFHDBG预购:FAEKCDHGB

F 是root

EACK将转到Root的LEFT SUB TREE

HDBG将转到Root的右子树

Step 1)

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

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


Step 2)

现在,对于LEFT SUB TREE,我们有来自Inorder的EACK和来自Preorder的相同字母AEKC

即

 Inorder   E A C K
 Preorder A E K C

现在再次找到A作为Root,所以现在树就是

                     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的右子树上执行相同的过程

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

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

Answer 2

不确定是否有证据,但这样做的alg就是这样,

f(inorder, levelorder):
      if length(levelorder) == 0:
          return None
      root = levelorder[0]#set root to first element in levelorder
      subIn1, subIn2 = partition(inorder, levelorder[0]) #partition inorder based on root
      subLevel1 = extract(levelOrder, subIn1)#remove elements in level order not in subIn1
      subLevel2 = extract(levelOrder, subIn2)#remove elements in level order not in subIn2
      root->left = f(subIn1, subLevel1)
      root->right = f(subIn2, subLevel2)
      return root

为了证明这一点,你必须证明inorder遍历中根节点的左边序列是左子树的顺序遍历,然后是右边的相同遍历.没错,但要证明这很乏味.

您还需要显示为子树维护的levelorder.也是如此,但要证明是乏味的.

哦,是的,您可能必须证明级别顺序遍历中的第一个元素是树的根,但这应该来自定义.