数据结构笔记——由遍历序列构造二叉树

た入场券 2023-02-13 08:05 16阅读 0赞

**目录**

一、不同二叉树的中序遍历序列

二、前序+中序遍历序列

三、后序+中序遍历序列

四、层序+中序遍历序列

五、若前序、后序、层序序列两两组合？

六、总结

--------------------

## **一、不同二叉树的中序遍历序列** ##

**中序遍历：中序遍历左子树、根结点、中序遍历右子树**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

**前序遍历：根结点、前序遍历左子树、前序遍历右子树**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

**后序遍历：前序遍历左子树、前序遍历右子树、根结点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

**结论：若只给出一棵二叉树的前、中、后、层序遍历序列中的一种，不能唯一确定一棵二叉树**

![20200527215552929.png][]

## **二、前序+中序遍历序列** ##

![20200527215840965.png][]

前序遍历序列：根结点 左子树的前序遍历序列  右子树的前序遍历序列

中序遍历序列：左子树的中序遍历序列 根结点 右子树的中序遍历序列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

例1：

![20200527220032422.png][]

![20200527220055298.png][]

例2：

![20200527220308142.png][]

![20200527220324436.png][]

## **三、后序+中序遍历序列** ##

后序遍历序列：左子树的中序遍历序列 右子树的中序遍历序列 根结点

中序遍历序列：左子树的中序遍历序列 根结点 右子树的中序遍历序列

![20200527220445868.png][]

例：

![20200527220458525.png][]

![20200527220324436.png][]

## **四、层序+中序遍历序列** ##

层序遍历序列：根结点 左子树的根右子树的根

中序遍历序列：左子树的中序遍历序列 根结点 右子树的中序遍历序列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

例1：

![20200527220742792.png][]

![20200527220324436.png][]

例2：

![20200527220928530.png][]

![20200527220946384.png][]

## **五、若前序、后序、层序序列两两组合？** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

## **六、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527215045217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200527215253431.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200527215345329.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200527215552929.png]: https://img-blog.csdnimg.cn/20200527215552929.png
[20200527215840965.png]: https://img-blog.csdnimg.cn/20200527215840965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200527215831404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200527220032422.png]: https://img-blog.csdnimg.cn/20200527220032422.png
[20200527220055298.png]: https://img-blog.csdnimg.cn/20200527220055298.png
[20200527220308142.png]: https://img-blog.csdnimg.cn/20200527220308142.png
[20200527220324436.png]: https://img-blog.csdnimg.cn/20200527220324436.png
[20200527220445868.png]: https://img-blog.csdnimg.cn/20200527220445868.png
[20200527220458525.png]: https://img-blog.csdnimg.cn/20200527220458525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200527220732604.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200527220742792.png]: https://img-blog.csdnimg.cn/20200527220742792.png
[20200527220928530.png]: https://img-blog.csdnimg.cn/20200527220928530.png
[20200527220946384.png]: https://img-blog.csdnimg.cn/20200527220946384.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020052722131338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200527221021667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70