数据结构与算法——树

1、1 第六章 树和二叉树6.1 树的有关概念树的有关概念6.2 二叉树二叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 Huffman树及其应用树及其应用2 第六章 树和二叉树树树和和二二叉叉树树树的树的ADTADT逻辑结构逻辑结构存储结构存储结构树树 树的应用树的应用HuffmanHuffman树树判定过程判定过程二叉树二叉树逻辑结构逻辑结构存储结构存储结构基本性质基本性质遍历二叉树遍历二叉树线索二叉树线索二叉树树和森林树和森林【本章学习要点本章学习要点】树的存储结构树的存储结构树的遍历树的遍历3 第六章 树和二叉树6

2、.1 树的有关概念树的有关概念6.2 二叉树二叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 Huffman树及其应用树及其应用4 第六章 树和二叉树本章学习重点和难点重点重点：(1)二叉树的定义、存储结构、遍历及应用；二叉树的定义、存储结构、遍历及应用； (2)线索二叉树的定义、存储结构及相应的操作；线索二叉树的定义、存储结构及相应的操作； (3)树和森林与二叉树之间的相互转化方法；树和森林与二叉树之间的相互转化方法； (4)哈夫曼树的建立方法和哈夫曼编码。哈夫曼树的建立方法和哈夫曼编码。难点难点： （1）二叉树的构

3、造）二叉树的构造 、应用；、应用； （2）线索二叉树的遍历和相应的操作。）线索二叉树的遍历和相应的操作。 5 第六章 树和二叉树树形结构是一种重要的非线性结构。树是树形结构是一种重要的非线性结构。树是n个结点的有限集合，个结点的有限集合，在任一棵非空树中：在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为）其余结点可分为m个互不相交的集合，而且这些集合中的每个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。一集合都本身又是一棵树，称为根的子树。说明：说明：树是递归结构，在树的定义中又用到了树的概念树是递归结构，在树的定义中

4、又用到了树的概念 J JI IA AC CB BD DH HG GF FE EK KL LM Mp 树的概念树的概念 6.1 树的有关概念树的有关概念6 第六章 树和二叉树p 树的概念树的概念 6.1 树的有关概念树的有关概念数据对象数据对象 D：D是具有是具有相同特性相同特性的数据元素的集合。的数据元素的集合。 若若D D为空集，则称为空树为空集，则称为空树 。 否则否则: : (1) (1) 在在D D中存在中存在唯一唯一的称为根的数据元素的称为根的数据元素rootroot； (2) (2) 当当n1n1时，其余结点可分为时，其余结点可分为m (m0)m (m0)个个互互 不相交不相交的有

5、限集的有限集T T1 1, T, T2 2, , T, , Tm m，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根rootroot的子树。的子树。 数据关系数据关系 R：ADT TreeADT Tree7 第六章 树和二叉树p 树的概念树的概念 6.1 树的有关概念树的有关概念基本操作基本操作 P P：ADT TreeADT Tree查查 找找 类类 插插 入入 类类删删 除除 类类 数据对象数据对象 D： 数据关系数据关系 R：8 第六章 树和二叉树p 树的基本操作树的基本操作P 6.1 树的有关概念树的有关概念 Root(T) Ro

6、ot(T) / / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) Value(T, cur_e) / / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) Parent(T, cur_e) / / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) LeftChild(T, cur_e) / / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) RightSibling(T, cur_e) / / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) TreeEmpty(

7、T) / / 判定树是否为空树判定树是否为空树 TreeDepth(T) TreeDepth(T) / / 求树的深度求树的深度TraverseTree( T, Visit() ) TraverseTree( T, Visit() ) / / 遍历遍历9 第六章 树和二叉树p 树的基本操作树的基本操作P 6.1 树的有关概念树的有关概念插入类：插入类：InitTree(&T) InitTree(&T) / / 初始化置空树初始化置空树 CreateTree(&T, definition) CreateTree(&T, definition) / / 按定义构造树按定义构造树Assign(T,

8、cur_e, value) Assign(T, cur_e, value) / / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) InsertChild(&T, &p, i, c) / / 将以将以c c为根的树插入为结点为根的树插入为结点p p的第的第i i棵子树棵子树10 第六章 树和二叉树p 树的基本操作树的基本操作P 6.1 树的有关概念树的有关概念删除类：删除类： ClearTree(&T) ClearTree(&T) / / 将树清空将树清空 DestroyTree(&T) DestroyTree(&T) / / 销毁树的结构销毁树的结构Delet

9、eChild(&T, &p, i) DeleteChild(&T, &p, i) / / 删除结点删除结点p p的第的第i i棵子树棵子树11 第六章 树和二叉树例如：集合例如：集合 T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J，K K，L L，MMA A是根，其余结点可以划分为是根，其余结点可以划分为3 3个个互不相交的集合互不相交的集合： T1=B, E, FT1=B, E, F，K K，L , T2=C, G , T3=D, H, I, JL , T2=C, G , T3=D, H, I, J，MM这些集合中的每

10、一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的概念树的概念 12 第六章 树和二叉树 从逻辑结构看：从逻辑结构看：树是一种分枝结构，树中只有根结点没有前趋；其余结点有零树是一种分枝结构，树中只有根结点没有前趋；其余结点有零个或多个后继；个或多个后继；除根外，其余结点都除根外，其余结点都有且仅一个有且仅一个前趋；都存在前趋；都存在唯一唯一一条从根到一条从根到该结点的路径该结点的路径。J JI IA AC CB BD DH HG GF

11、FE EK KL LM M6.1 树的有关概念树的有关概念p 树的概念树的概念 13 第六章 树和二叉树6.1 树的有关概念树的有关概念p 树的概念树的概念 线性结构线性结构非线形结构非线形结构树树第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点( (无前驱无前驱) )最后一个数据元素最后一个数据元素 ( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) ) 其它数据元素其它数据元素( (一个前驱、一个后继一个前驱、一个后继) ) 其它数据元素其它数据元素( (一个前驱、多个后继一个前驱、多个后继) )14 第六章 树和二叉树 单位行政机构的组织关系单位行

12、政机构的组织关系1）树可表示具有分枝结构关系的对象）树可表示具有分枝结构关系的对象J JI IA AC CB BD DH HG GF FE EK KL LM M例例6.1 树的有关概念树的有关概念p 树的应用树的应用 15 第六章 树和二叉树 2）树是常用的数据组织形式）树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。于管理和使用数据，将它们用树的形式来组织。C C文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹11 11 文件夹文件夹

13、12 12 文件文件11 11 文件文件1212 计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件是用树文件系统，所有的文件是用树的形式来组织的。的形式来组织的。例例6.1 树的有关概念树的有关概念p 树的应用树的应用 16 第六章 树和二叉树（1 1）树形表示法）树形表示法ABEKLFCGDHMJI（2 2）凹入表示法）凹入表示法J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 17 第六章 树和二叉树（3 3）嵌套集合表示法）嵌套集合表示法 （文氏图

14、）（文氏图）AEDHJIKLMFGCBJ JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 18 第六章 树和二叉树（4 4）广义表表示法）广义表表示法(A(A）第一层）第一层( (A(A(B, C, DB, C, D) ) 第二层第二层(A(A(B B( (E,FE,F), ), C C( (G G), ), D D( (H,I,JH,I,J) ) 第三层第三层(A(A(B B( (E(E(K,LK,L),F),F), ), C C( (G G), ), D D( (H(H(M M),I,J),I,J) ) 第四层

15、第四层J JI IA AC CB BD DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的表示树的表示 19 第六章 树和二叉树结点层结点层：根结点的层定义为：根结点的层定义为1，其它依此类推；，其它依此类推；树的深度树的深度：树中最大的结点层；：树中最大的结点层；结点的度结点的度：结点子树的个数；：结点子树的个数；树的度树的度： 树中最大的结点度；树中最大的结点度；叶子结点叶子结点：也叫终端结点，是度为：也叫终端结点，是度为 0 的结点；的结点；树的度为树的度为3树的深度为树的深度为4第第1层层第第3层层第第2层层第第4层层J JI IA AC CB BD

16、DH HG GF FE EK KL LM M6.1 树的有关概念树的有关概念p 树的有关术语树的有关术语 20 第六章 树和二叉树分枝结点：分枝结点：度不为度不为0的结点；的结点；有序树：有序树：子树有序的树，如：家族树；子树有序的树，如：家族树；无序树：无序树：不考虑子树的顺序；不考虑子树的顺序；森林：森林：互不相交的树集合；互不相交的树集合；6.1 树的有关概念树的有关概念p 树的有关术语树的有关术语 树和森林的关系：树和森林的关系：（1）一棵树去掉根）一棵树去掉根 ，其子树构成一个森林；，其子树构成一个森林；（2）一个森林增加一个根结点成为树。）一个森林增加一个根结点成为树。21 第六章

17、 树和二叉树6.1 树的有关概念树的有关概念6.2 二叉树二叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 Huffman树及其应用树及其应用22 第六章 树和二叉树 树是一种分枝结构的对象，在树的概念中，对每一树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，个结点孩子的个数没有限制，因此树的形态多种多样，本节我们主要讨论另一种树型结构本节我们主要讨论另一种树型结构二叉树。二叉树。6.2 二叉树二叉树 A A F F G G E E D D C C B B23 第六章 树和二

18、叉树 6.2.1 6.2.1 二叉树的概念二叉树的概念 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树24 第六章 树和二叉树6.2.1 二叉树的概念二叉树的概念特点：特点：二叉树中每个结点最多有两棵子树；即二叉树二叉树中每个结点最多有两棵子树；即二叉树每个结每个结点度小于等于点度小于等于2 2; ;左、右子树不能颠倒左、右子树不能颠倒有序树有序树; ;二叉树是二叉树是递归结构递归结构，在二叉树的定义中又用到了二叉，在二叉树的定义中又用到了二叉树的概念树的概念; ; A A F F G G E E D D C C

19、B B概念：二叉树概念：二叉树或为空树，或由根及或为空树，或由根及两颗不相交的两颗不相交的左、右左、右子树构成，并且子树构成，并且左、右子树本身也是二叉树左、右子树本身也是二叉树。25 第六章 树和二叉树 A A F F G G E E D D C C B B(a) F F A A G G E E D D B B C C(b)二叉树是有左右之分的6.2.1 二叉树的概念二叉树的概念26 第六章 树和二叉树p 二叉树的基本形态二叉树的基本形态(a)空树(b)仅有根(c) 右子树空(d) 左子树空(e) 左、右子树均在6.2.1 二叉树的概念二叉树的概念27 第六章 树和二叉树 6.2.1 6.2

20、.1 二叉树的概念二叉树的概念 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树28 第六章 树和二叉树证明：最多结点数为各层结点个数相加，即证明：最多结点数为各层结点个数相加，即 1+2+4+21+2+4+2k-1k-1=2=2k k-1-1性质性质2 2 深度为深度为k k的二叉树的二叉树有有个结点。个结点。性质性质1 1 在二叉树的第在二叉树的第i(i1)i(i1)层上层上有有个结点。个结点。 证明：用数学归纳法就可以证明。证明：用数学归纳法就可以证明。ABCDEFGIHJ k k层二叉树层二叉树6.2.2 二

21、叉树的性质二叉树的性质29 第六章 树和二叉树p 两种特殊的二叉树两种特殊的二叉树 A A G G F F E E D D C C B B(a)(a)K=3K=3的满二叉树的满二叉树满二叉树：满二叉树：如果深度为如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树；完全二叉树：二叉树中所含的二叉树中所含的 n n 个结点和满二叉树中编号为个结点和满二叉树中编号为1 1至至n n的的 结点结点一一对应一一对应。 A A E E D D C C B B(b)(b)(b)(b)完全二叉树 G G A A E E D D C C B B(c)(c)(c

22、) (c) 不是不是完全二叉树完全二叉树结论：满二叉树一定是完全二叉树，反之不一定6.2.2 二叉树的性质二叉树的性质30 第六章 树和二叉树证明：设所求完全二叉树的深度为证明：设所求完全二叉树的深度为k 由性质由性质2 2和完全二叉树的定义知：和完全二叉树的定义知： 2k-1 1-1 1n2k-1 1 性质性质3 3 具有具有n n个结点的个结点的完全二叉树的深度完全二叉树的深度为为 loglog2 2n n +1 +1 由此可以推出：由此可以推出：2k-1 1 n2k取对数得：取对数得： k-1 1log2nk由于由于k为整数，故有为整数，故有k-1 1= log2n 即：即： k= lo

23、g2n +1 1 性质性质2:2:深度为深度为k k的二叉树最多有的二叉树最多有2 2k k-1-1个结点个结点 A A E E D D C C B B E E D D D Dk层的最多结点数层的最多结点数k-1-1层的最多结点数层的最多结点数6.2.2 二叉树的性质二叉树的性质31 第六章 树和二叉树性质性质4 4 对任意二叉树对任意二叉树T T，如果度数为，如果度数为0 0结点数为结点数为n n0 0, ,度数为度数为1 1结点数为结点数为n n1 1, ,度数为度数为2 2结点数为结点数为n n2 2，则，则n n0 0=n=n2 2+1+1。 证明：二叉树证明：二叉树T T的的结点总数

24、结点总数 n=nn=n0 0+n+n1 1+n+n2 2 （1 1） 注意：注意：n1 1生成生成n1 1*1个节点，个节点，n2 2生成生成n2 2*2个节点，个节点， 根结点不由任何结点产生根结点不由任何结点产生由于分支结点是由度为由于分支结点是由度为1 1和度为和度为2 2的结点生成的的结点生成的 即即分支结点总数分支结点总数b=b=n1+2*n2 （3 3）二叉树的二叉树的分支结点总数分支结点总数 b=n-1 b=n-1 （2 2） 由由(1)(2)(3)(1)(2)(3)得得 求得：求得：n n0 0=n=n2 2+1+1ABCDEFGIHJ6.2.2 二叉树的性质二叉树的性质32

25、第六章 树和二叉树性质性质5:5:若对含若对含 n n 个结点的完全二叉树从上到下且从左个结点的完全二叉树从上到下且从左至右进行至右进行 1 1 至至 n n 的编号，则对完全二叉树中任意一个的编号，则对完全二叉树中任意一个编号为编号为 i i 的结点的结点: :(1) (1) 若若 i=1i=1，则该结点是二叉树的根，无双亲，否则，则该结点是二叉树的根，无双亲，否则， 编号为编号为 i/2i/2 的结点为其的结点为其双亲双亲结点；结点；(3) (3) 若若 2i+1n2i+1n，则该结点无右孩子结点，否则，编号为，则该结点无右孩子结点，否则，编号为 2i+1 2i+1 的结点为其的结点为其右

26、孩子右孩子结点。结点。(2) (2) 若若 2in2in，则该结点无左孩子，否则，编号为，则该结点无左孩子，否则，编号为 2i2i的的 结点为其结点为其左孩子左孩子结点；结点； 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i i6.2.2 二叉树的性质二叉树的性质33 第六章 树和二叉树编号编号i=4i=4双亲为双亲为 i/2i/2 =2 =2左子树为左子树为2i=82i=8右子树为右子树为2i+1=92i+1=9i=1 只有根结点只有根结点编号编号i=5i=5双亲为双亲为 i/2i/2 =2 =2左子树为左子树为2i=10 2i=10 右子树为右子树为2i+1=11

27、2i+1=11i=8,i=8,2in2in无左子树无左子10 11 12 13 146.2.2 二叉树的性质二叉树的性质通过性质5把非线性结构轻易转化成了线性结构。34 第六章 树和二叉树 6.2.1 二叉树的概念二叉树的概念 6.2.2 二叉树的性质二叉树的性质 6.2.3 二叉树的存储结构二叉树的存储结构6.2 二叉树二叉树35 第六章 树和二叉树p二叉树的链式存储表示二叉树的链式存储表示p 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 二叉树的存储结构二叉树的存储结构36 第六章 树和二叉树 (1)(1)完全（或满）二叉树完全（或满）二叉树ABCDEFGI

28、HJ采用采用一维数组一维数组，按，按层序顺序层序顺序依依次存储二叉树的每一个结点。次存储二叉树的每一个结点。如下图所示：如下图所示：p 二叉树的顺序存储表示二叉树的顺序存储表示利用性质利用性质5 5实现实现线性结构线性结构和和非线性结构非线性结构的灵活转换。的灵活转换。 2i+2 2i+2 i/2 2i+12i+1 2i2i i+1i+1 i iA B C D E F G1 2 3 4 5 6 7 8 9 10H IJ6.2.3 二叉树的存储结构二叉树的存储结构37 第六章 树和二叉树(2)(2)一般二叉树一般二叉树A B C 0E 0G1 2 3 4 5 6 7 8 9 1000J通过通过虚

29、设虚设部分结点，使其变成相应的部分结点，使其变成相应的完全二叉树完全二叉树。ABCEGJABC0E0G00Jp 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 二叉树的存储结构二叉树的存储结构38 第六章 树和二叉树(3)(3)特殊的二叉树特殊的二叉树说明：说明：顺序存储方式对于畸形二叉树，浪费较大空间顺序存储方式对于畸形二叉树，浪费较大空间p 二叉树的顺序存储表示二叉树的顺序存储表示6.2.3 二叉树的存储结构二叉树的存储结构ABCJ39 第六章 树和二叉树二叉链表存储：二叉链表存储：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域二叉链表中每个结点包含三个域：数据域、左指针域、

30、右指针域 typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node * *lch,lch,* *rch;rch; BinTNode; BinTNode;lchrchdataC 语言的类型描述如下语言的类型描述如下: :p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构40 第六章 树和二叉树二叉链表图示二叉链表图示 D D A A C C E E F F B B root A A F F E E D D C C B B二叉树二叉树n

31、 个结点的二叉树中，有多少个空链接域？p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构41 第六章 树和二叉树性质性质6 6：n n 个结点的二叉树中，共有个结点的二叉树中，共有 n+1n+1 个空指针域。个空指针域。证：证：n n个结点总的指针域数个结点总的指针域数2n 2n 除了根结点外，其余除了根结点外，其余n-1n-1个结点个结点都是由指针域指出的结点；都是由指针域指出的结点； 所以，剩余的结点数即所以，剩余的结点数即空指针域个数空指针域个数为：为：2n-2n-（n-1n-1）=n+1 =n+1 二叉链表的缺点二叉链表的缺点是很难找到结点的双亲是

32、很难找到结点的双亲二叉链表图示二叉链表图示 D D A A C C E E F F B B rootp 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构42 第六章 树和二叉树三叉链表（三叉链表（带双亲指针的二叉链表带双亲指针的二叉链表）: :三叉链表中每个结点三叉链表中每个结点包含四个域：数据域、左指针域、右指针域、包含四个域：数据域、左指针域、右指针域、双亲指针域双亲指针域typedef typedef Struct nodeStruct node DataType data; DataType data; Struct nodeStruct node

33、* *lch,lch,* *rch,rch,* *parent;parent;lch data rch parent结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :p 二叉树的链式存储表示二叉树的链式存储表示6.2.3 二叉树的存储结构二叉树的存储结构43 第六章 树和二叉树 A A F F E E D D C C B BA AB BD DF FE EC Crootlch data rch parentp 二叉树的链式存储表示二叉树的链式存储表示-三叉链表三叉链表6.2.3 二叉树的存储结构二叉树的存储结构44 第六章 树和二叉树6.1 树的有关概念树的有关概念6.2 二叉树二

34、叉树6.3 二叉树的遍历二叉树的遍历6.4 遍历的应用遍历的应用6.5 线索二叉树线索二叉树6.6 树和森林树和森林6.7 Huffman树及其应用树及其应用45 第六章 树和二叉树 6.3.1 二叉树的遍历方法二叉树的遍历方法 6.3.2 二叉树的遍历算法二叉树的遍历算法 6.3 二叉树的遍历二叉树的遍历46 第六章 树和二叉树 遍历遍历：按某种搜索路径：按某种搜索路径访问访问二叉树的每个结点，而二叉树的每个结点，而且每个结点仅被访问一次。且每个结点仅被访问一次。访问访问：访问是指对结点进行各种操作的简称，包括：访问是指对结点进行各种操作的简称，包括输出、查找、修改等等操作。输出、查找、修改

35、等等操作。遍历遍历是各种数据结构最基本的操作，许多其它的操是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。作可以在遍历基础上实现。 6.3 .1 二叉树的遍历方法二叉树的遍历方法47 第六章 树和二叉树 “ “遍历遍历”是任何类型均有的操作：是任何类型均有的操作：线性结构的遍历：只有一条搜索路径线性结构的遍历：只有一条搜索路径( (因为每个结点均只因为每个结点均只有一个后继有一个后继) )；非线性结构的遍历：二叉树是非线性结构，则非线性结构的遍历：二叉树是非线性结构，则存在如何遍存在如何遍历历即按什么样的即按什么样的搜索路径搜索路径遍历的问题。遍历的问题。 如何访问二叉树的每个

36、结点，如何访问二叉树的每个结点， 而且每个结点仅被访问一次？而且每个结点仅被访问一次？6.3 .1 二叉树的遍历方法二叉树的遍历方法48 第六章 树和二叉树 对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜索路径：先上后下先上后下的按层次遍历；的按层次遍历；先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历；先右先右（子树）（子树）后左后左（子树）的遍历（子树）的遍历。6.3 .1 二叉树的遍历方法二叉树的遍历方法49 第六章 树和二叉树 二叉树由根、左子树、右子树三部分组成二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树

37、二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树遍历左子树 T T：访问根结点访问根结点 R R：遍历右子树遍历右子树 有六种遍历方法：有六种遍历方法： T T L L R R，L L T T R R，L L R R T T， T T R R L L，R R T T L L，R R L L T T 约定先左后右约定先左后右, ,有三种遍历方法：有三种遍历方法： T T L L R R、L L T T R R、L L R R T T ，分别称分别称为为 先序遍历、中序遍历、后序遍历先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B

38、6.3 .1 二叉树的遍历方法二叉树的遍历方法50 第六章 树和二叉树若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历序列：中序遍历序列：中序遍历右图所示的二叉树中序遍历右图所示的二叉树 p中序遍历中序遍历（ L T RL T R ） A A F F G G E E D D C C B B,F例例D,G,B,A,E,C图示图示6.3 .1 二叉树的遍历方法二叉树的遍历方法51 第六章 树和二叉树 d d e e c c b b f f a a + + * * / / - - - - 中序遍历下图所

39、示的二叉树中序遍历下图所示的二叉树 中序中序 a,+,b,a,+,b,* *,c,-,d,c,-,d, ,- -,e,/,f,e,/,f练习练习6.3 .1 二叉树的遍历方法二叉树的遍历方法52 第六章 树和二叉树 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树；）先序遍历右子树； 先序遍历序列：先序遍历序列：A A, ,B B, ,D D,E,E,G G,C,F,C,F A A F F G G E E D D C C B B 先先序遍历右图所示的二叉树序遍历右图所示的二叉树 （1 1）访问根结点）访问根结

40、点A A （2 2）先序遍历左子树：即按先序遍历左子树：即按 T T L L R R 的顺序遍历的顺序遍历左子树左子树 （3 3）先序遍历右子树：即按）先序遍历右子树：即按 T T L L R R 的顺序遍历的顺序遍历右子树右子树图示图示p先序遍历先序遍历（T L RT L R）例例6.3 .1 二叉树的遍历方法二叉树的遍历方法53 第六章 树和二叉树 d d e e c c b b f f a a + + * * / / - - - - 先序遍历下图所示的二叉树先序遍历下图所示的二叉树 先序先序 - -,+,+,a,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,f练习练习6

41、.3 .1 二叉树的遍历方法二叉树的遍历方法54 第六章 树和二叉树若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点 后序遍历序列：后序遍历序列： D D, ,G G,E,E,B B,F,C,F,C,A A 后后序遍历右图所示的二叉树序遍历右图所示的二叉树 （1 1）后序遍历左子树：即按）后序遍历左子树：即按 L L R R T T 的顺序遍历的顺序遍历左子树左子树 （2 2）后序遍历右子树：即按）后序遍历右子树：即按 L L R R T T 的顺序遍历的顺序遍历右子树右子树 （3 3）访问根结点）访问根结

42、点A A图示图示p后序遍历后序遍历（ L L T T R R ） A A F F G G E E D D C C B B例例6.3 .1 二叉树的遍历方法二叉树的遍历方法55 第六章 树和二叉树 d d e e c c b b f f a a + + * * / / - - - - 后序遍历下图所示的二叉树后序遍历下图所示的二叉树 后序后序 a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/,e,f,/,- -练习练习6.3 .1 二叉树的遍历方法二叉树的遍历方法56 第六章 树和二叉树p按层遍历按层遍历 A A F F G G E E D D C C B B 层次遍历序列：层

43、次遍历序列： A,B,C,D,E,F,GA,B,C,D,E,F,G6.3 .1 二叉树的遍历方法二叉树的遍历方法57 第六章 树和二叉树p按层遍历按层遍历按层遍历引入了按层遍历引入了队列队列作为辅助工具。作为辅助工具。算法思想为：算法思想为：（1）将二叉树根入队列；）将二叉树根入队列；（2）将队头元素出队列，并判断此元素是否有左右孩）将队头元素出队列，并判断此元素是否有左右孩子，若有，则将它的左右孩子入列，否则转（子，若有，则将它的左右孩子入列，否则转（3）；）；（3）重复步骤（）重复步骤（2），直到队列为空），直到队列为空 。 A A F F G G E E D D C C B B课后思考：

44、按层遍历算法课后思考：按层遍历算法6.3 .1 二叉树的遍历方法二叉树的遍历方法58 第六章 树和二叉树6.3 二叉树的遍历二叉树的遍历 6.3.1 二叉树的遍历方法二叉树的遍历方法 6.3.2 二叉树的遍历算法二叉树的遍历算法 59 第六章 树和二叉树 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）

45、访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树；）先序遍历右子树；6.3.2 二叉树的遍历算法二叉树的遍历算法p先序遍历先序遍历（T T L L R R）的定义的定义60 第六章 树和二叉树 void prev (BinTree T) if (T) visit(T-data)； prev(T-lch); prev(T-rch); 先序序列为先序序列为 + * a b c / d e称为称为前缀表达式前缀表达式 e e a a + + * * / / / d d / - -T T b b c c a a* *(b-c)+d/e(b-c)+d/ep先序遍历递归

46、算法先序遍历递归算法6.3.2 二叉树的遍历算法二叉树的遍历算法61 第六章 树和二叉树void Mid (BinTree T) if (T) Mid(T-lch); visit( T-data)； Mid(T-rch); 中序序列为中序序列为 a * b c+ d / e称为称为中缀表达式中缀表达式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c p中序遍历递归算法中序遍历递归算法6.3.2 二叉树的遍历算法二叉树的遍历算法62 第六章 树和二叉树void Post(BinTree T) if (T) Po

47、st(T-lch); Post(T-rch); visti( T-data)； 后序序列为后序序列为 a b c * d e / + 称为称为后缀表达式后缀表达式a a* *(b-c)+d/e(b-c)+d/e e e a a + + * * / / / d d / - -T T b b c c p后序遍历递归算法后序遍历递归算法6.3.2 二叉树的遍历算法二叉树的遍历算法63 第六章 树和二叉树BiTNode *GoFarLeft(BiTree T, Stack *S)/找到左子树的最左下的结点找到左子树的最左下的结点 if (!T ) return NULL; while (T-lch )

48、 Push(S, T); T = T-lch; return T; d d b b e e a a * * - - / / c c + +p 中序遍历的非递归算法中序遍历的非递归算法中序序列为：中序序列为： a * b c+ d / e6.3.2 二叉树的遍历算法二叉树的遍历算法64 第六章 树和二叉树p 中序遍历的非递归算法中序遍历的非递归算法void Inorder_I(BiTree T)void Inorder_I(BiTree T) Stack Stack * *S;S; t = t = GoFarLeftGoFarLeft(T, S);(T, S); / / 找到最左下的结点找到最左

49、下的结点 while(t)while(t) visit(t-data);visit(t-data); if (t-rch) if (t-rch) t = t = GoFarLeft(t-rch, S); GoFarLeft(t-rch, S); else if ( !StackEmpty(S ) else if ( !StackEmpty(S ) / / 栈不空时退栈栈不空时退栈 t = Pop(S);t = Pop(S); else t = NULL; else t = NULL; / 栈空表明遍历结束栈空表明遍历结束 / while / while/ Inorder_I / Inorder

50、_I 6.3.2 二叉树的遍历算法二叉树的遍历算法65 第六章 树和二叉树6.4 遍历的应用遍历的应用遍历是二叉树各种操作的基础，可以在遍历过程中对结遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作：点进行各种操作：（1 1）求结点的双亲、孩子结点、结点的层次；）求结点的双亲、孩子结点、结点的层次；（2 2）求孩子结点；）求孩子结点；（3 3）求结点的层次；）求结点的层次；（4 4）遍历过程中生成结点，建立二叉树；）遍历过程中生成结点，建立二叉树；遍历二叉树的过程实质遍历二叉树的过程实质:是把二叉树的结点进行线性排列的过程。是把二叉树的结点进行线性排列的过程。66 第六章 树和二

51、叉树 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价6.4 遍历的应用遍历的应用67 第六章 树和二叉树递归建立二叉树递归建立二叉树 我们按先序递归遍历的思想来建立二叉树。我们按先序递归遍历的思想来建立二叉树。其建立思想如下：其建立思想如下：（1）建立二叉树的根结点；）建立二叉树的根结点；（2）先序建立二叉树的左子树；）先序建立二叉树的左子树；（3）先序建立二叉树的右子树。）先序建立二叉树的右子树。p 二叉树的生成二叉树的生成6.4.1 遍历的基本应用遍历的基本应用68 第六章 树

52、和二叉树二叉树的生成的递归算法二叉树的生成的递归算法bitree *creat() bitree *t; t=(bitree*)malloc(sizeof(bitree); t-data=x; t-lch=creat(); t-rch=creat(); return t;p 二叉树的生成二叉树的生成6.4.1 遍历的基本应用遍历的基本应用69 第六章 树和二叉树p 求二叉树的叶子数。求二叉树的叶子数。算法思想：采用任何遍历方法，遍历时判断访问的结点是不是叶子，算法思想：采用任何遍历方法，遍历时判断访问的结点是不是叶子，若是则叶子数加若是则叶子数加1 1。int countleaf(bitree

53、 t ,int num) if(t!=NULL) if(t-lch=NULL) &(t- rch)=NULL) num+; num=countleaf(t-lch,num); num=countleaf(t-rch,num); return num;6.4.1 遍历的基本应用遍历的基本应用70 第六章 树和二叉树p 求二叉树的深度求二叉树的深度算法思想：从第一层的根结点开始往下递推可得到。算法思想：从第一层的根结点开始往下递推可得到。下面给出后序遍历求二叉树深度的递归算法下面给出后序遍历求二叉树深度的递归算法：Int treedepth(bitree *t) int h,lh,rh; if(t

54、=NULL) h=0; else lh=treedepth(t-lch); rh=treedepth(t-rch); if(lh=rh) h=lh+1; else h=rh+1; return h; 6.4.1 遍历的基本应用遍历的基本应用71 第六章 树和二叉树 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价6.4. 遍历的应用遍历的应用72 第六章 树和二叉树问题：问题：给定一个遍历序列，能否唯一确定一棵二叉树？给定一个遍历序列，能否唯一确定一棵二叉树？例如：先序序列为例如：先

55、序序列为ABCD,ABCD,其二叉树的结构是什么？其二叉树的结构是什么？答案是不唯一6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 A A C C B B D D A A D D C C B B A A C C D D B Bp二叉树的遍历与存储结构之间的转化二叉树的遍历与存储结构之间的转化73 第六章 树和二叉树p构造二叉树构造二叉树 给定某两种遍历序列能否唯一确定一棵二叉树？给定某两种遍历序列能否唯一确定一棵二叉树？ 给定中序和后序给定中序和后序 给定中序和前序给定中序和前序 给定先序和后序给定先序和后序不能不能唯一确定一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树唯一

56、确定一棵二叉树唯一确定一棵二叉树唯一确定一棵二叉树关键关键（1 1）确定二叉树的根结点；）确定二叉树的根结点； （2 2）结点的左右次序。）结点的左右次序。6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用74 第六章 树和二叉树 给定二叉树先序和中序遍历序列，如何构造二叉树？给定二叉树先序和中序遍历序列，如何构造二叉树？ 先序：先序：1 2 4 6 3 5 7 81 2 4 6 3 5 7 8 中序：中序：2 6 4 1 3 7 5 82 6 4 1 3 7 5 81前前 246中中264前前3578中中3758例例左左2前前 46中中64右右461前前3578中中37582

57、46p构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用75 第六章 树和二叉树根据给定的遍历次序构造二叉树，并给出先根据给定的遍历次序构造二叉树，并给出先序遍历序列。序遍历序列。中序遍历序列：中序遍历序列：a,+,b,a,+,b,* *,c,-,d,-,e,/,f,c,-,d,-,e,/,f后序遍历序列：后序遍历序列：a,b,c,d,-,a,b,c,d,-,* *,+,e,f,/,-,+,e,f,/,-作业作业p构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用76 第六章 树和二叉树 e e d d c c b b f

58、 f a a + + * * / / - - - -先序先序:-,+,a,:-,+,a,* *,b,-,c,d,b,-,c,d,/,e,f,/,e,fp构造二叉树构造二叉树6.4.2二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用77 第六章 树和二叉树6.4 遍历的应用遍历的应用 6.4.1 遍历的基本应用遍历的基本应用 6.4.2 二叉树的遍历与存储结构的应用二叉树的遍历与存储结构的应用 6.4.3 二叉树的相似与等价二叉树的相似与等价78 第六章 树和二叉树p二叉树的相似与等价的含义二叉树的相似与等价的含义两株二叉树具有两株二叉树具有相同结构相同结构指：指： （1）它们都是空的）

59、它们都是空的 ； （2）它们都是非空的，且左右子树分别具有相同结构。）它们都是非空的，且左右子树分别具有相同结构。 “形状形状”相相同同6.4.3 二叉树的相似与等价二叉树的相似与等价79 第六章 树和二叉树p判断两株二叉树是否等价判断两株二叉树是否等价int EQUAL( t1 , t2 )BTREE t1 , t2 ; int x ; x = 0 ; if ( ISEMPTY(t1) & ISEMPTY(t2) )/二叉树空二叉树空 x = 1 ; else if ( !ISEMPTY( t1 ) & ! ISEMPTY( t2) ) /二叉树不空二叉树不空 if ( DATA( t1 )

60、 = DATA( t2 ) ) if ( EQUAL( LCHILD( t1 ) , LCHILD( t2 ) ) ) x= EQUAL( RCHILD( t1) , RCHILD( t2) ) return( x ) ; /* EQUAL */6.4.3 二叉树的相似与等价二叉树的相似与等价80 第六章 树和二叉树p二叉树的复制二叉树的复制BTREE COPY( BTREE oldtree ) BTREE temp ; if ( oldtree != NULL ) temp = new Node ; temp - lch = COPY( oldtree-lch ) ; temp - rch