由遍历序列确定二叉树

74 阅读 0 评论 49 点赞

我是靠谱客的博主无限小海豚，最近开发中收集的这篇文章主要介绍由遍历序列确定二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

两种遍历序列的组合	能否唯一确定二叉树
先序+中序	能

后序+中序	能


先序+后序	否

已知一棵树的两种序列，如何构造该二叉树
例：已知一棵树的先序和中序序列分别为：
A B C D E F G H I
B C A E D G H F I
试构造该二叉树
答：思路：
首先看先序序列：先序序列先看根，再看左子树、右子树，那么A就是该二叉树的根；然后，看中序序列，中序序列先看左子树，再看根，再看右子树，B C 在A 前头，而且A又是根，那么B C 就是属于左子树，D E F G H I 就是属于右子树。

其次看左子树：在先序序列中，左子树先访问的是B，然后再是C，那么，B 就是左子树的根；再看中序序列，左子树先访问的也是B，然后再是C，那么C就是B 的右子树

然后再看右子树：在先序序列中，右子树先访问的是D，那么D就是右子树的根，再看中序序列，先访问的是E，然后再是D，那么，E就是右子树下的左子树，F G H I 就是右子树下的右子树。

最后看右子树下的右子树（F G H I）：在先序序列中，先访问的是F，那么F就是该分支树的根，再看中序序列，F前面是G H ,后面是I，则G H是分支树下的左子树，I是分支树下的右子树；又 (F G H ),(G H F)与（A B C),(B C A)一样，所以G 是分支根，H 是其右子树。

画出如图：
在这里插入图片描述