“树的遍历”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
第29行： 第29行：
 
=== 2）由前序、中序遍历序列构造二叉树 ===
 
=== 2）由前序、中序遍历序列构造二叉树 ===
 
由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树；
 
由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树；
 +
[[文件:构造二叉树.png|无|缩略图|423x423像素]]
 +
解题思路：
  
−
前序序列是根、左、右的顺序，已知“前序序列为A......”，得知这个二叉树的根结点是A；
+
根据前序序列的规则（先遍历根结点，然后遍历左子树，再遍历右子树）得到子树的根结点，再根据中序序列中根结点出现的位置把序列分为左子树跟右子树两部分。
  
−
中序序列是左、根、右的顺序，已知“中序序列为HBEDFAGC”，得知A前面的结点（HBEDF）都在以A为根节点的树的左子树中，A后面的结点（GC）都在以A为根节点的树的右子树中，则有：
+
依据前序序列ABHFDECG先遍历根结点，然后遍历左子树，再遍历右子树，得知A是根节点，又有中序序列HBEDFAGC先遍历左子树，然后遍历根结点，最后遍历右子树，得知H、B、E、D、F在A为根节点的树的左子树中，G、C在A为根节点的树的右子树中
−
[[文件:构造二叉树1.png|无|缩略图|300x300像素]]
+
{| class="wikitable"
 +
! colspan="2" |A
 +
|-
 +
|H、B、E、D、F
 +
|GC
 +
|}
 +
其中左子树中，前序序列为BHFDE，那么B是根结点，中序序列HBEDF，以B为根结点拆成H和E、D、F一个左子树，一个右子树
 +
{| class="wikitable"
 +
! colspan="2" |B
 +
|-
 +
|H
 +
|E、D、F
 +
|}
 +
以B为根结点的右子树中，前序序列FDE，中序序列EDF，那么F是根结点，E、D都在以F为根结点的左子树中
 +
{| class="wikitable"
 +
! colspan="2" |F
 +
|-
 +
|E、D
 +
|
 +
|}
 +
在以F为根结点的左子树中，前序序列是DE，中序序列是ED，那么D是根结点，E是左叶子结点
 +
{| class="wikitable"
 +
! colspan="2" |D
 +
|-
 +
|E
 +
|
 +
|}
 +
在以A为根结点的右子树中，前序序列是CG，中序序列是GC，那么C是根结点，G在以C为根结点的树中的左子树中
 +
{| class="wikitable"
 +
! colspan="2" |C
 +
|-
 +
|G
 +
|
 +
|}
 +
以上子树合并起来就是
 +
{| class="wikitable"
 +
! colspan="6" |A
 +
|-
 +
! colspan="4" |B
 +
! colspan="2" |C
 +
|-
 +
!H
 +
! colspan="3" |F
 +
!G
 +
!
 +
|-
 +
!
 +
! colspan="2" |D
 +
!
 +
!
 +
!
 +
|-
 +
!
 +
!E
 +
!
 +
!
 +
!
 +
!
 +
|}

2022年9月19日 (一) 06:52的版本

https://www.bilibili.com/video/BV1hg411V7Bm?p=60

1）二叉树的遍历方式

前序/先序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。根、左、右

中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。 左、根、右

后序遍历：先遍历左子树，然后遍历右子树，最后遍历根结点。左、右、根

层序遍历：从上往下逐层遍历。上到下、左到右

二叉树的遍历方式.png

图中前序遍历结果是？

1、2、4、5、7、8、3、6

图中中序遍历结果是？

4、2、7、8、5、1、3、6

图中后序遍历结果是？

4、8、7、5、2、6、3、1

图中层序遍历结果是？

1、2、3、4、5、6、7、8


2）由前序、中序遍历序列构造二叉树

由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树；

构造二叉树.png

解题思路：

根据前序序列的规则（先遍历根结点，然后遍历左子树，再遍历右子树）得到子树的根结点，再根据中序序列中根结点出现的位置把序列分为左子树跟右子树两部分。

依据前序序列ABHFDECG先遍历根结点，然后遍历左子树，再遍历右子树，得知A是根节点，又有中序序列HBEDFAGC先遍历左子树，然后遍历根结点，最后遍历右子树，得知H、B、E、D、F在A为根节点的树的左子树中，G、C在A为根节点的树的右子树中

A
H、B、E、D、F GC

其中左子树中，前序序列为BHFDE，那么B是根结点，中序序列HBEDF，以B为根结点拆成H和E、D、F一个左子树，一个右子树

B
H E、D、F

以B为根结点的右子树中，前序序列FDE，中序序列EDF，那么F是根结点，E、D都在以F为根结点的左子树中

F
E、D

在以F为根结点的左子树中，前序序列是DE，中序序列是ED，那么D是根结点，E是左叶子结点

D
E

在以A为根结点的右子树中，前序序列是CG，中序序列是GC，那么C是根结点，G在以C为根结点的树中的左子树中

C
G

以上子树合并起来就是

A
B C
H F G
D
E
取自“https://www.jihongchang.top/index.php?title=树的遍历&oldid=2088”