数据结构第5章课件

《数据结构第5章课件》由会员分享，可在线阅读，更多相关《数据结构第5章课件（110页珍藏版）》请在装配图网上搜索。

1、第第5 5章章 树树14 八月 2023本章概述本章概述在前面的章节中介绍了数据结构中的线性结构，其在前面的章节中介绍了数据结构中的线性结构，其逻辑结构的特点是数据元素之间存在一对一的关系。而逻辑结构的特点是数据元素之间存在一对一的关系。而生活中的许多事物之间关系并非如此简单，如家族成员生活中的许多事物之间关系并非如此简单，如家族成员之间的关系，一个单位的组成结构等。这些结构的共同之间的关系，一个单位的组成结构等。这些结构的共同特点是具有明显的层次特点，并且其中的每个元素最多特点是具有明显的层次特点，并且其中的每个元素最多只有一个前驱，但可以有多个后继，因而可以抽象为本只有一个前驱，但可以有多

2、个后继，因而可以抽象为本章所要学习的树形结构。树在计算机领域中也有着广泛章所要学习的树形结构。树在计算机领域中也有着广泛的应用，例如，在编译程序中，用树来表示源程序的语的应用，例如，在编译程序中，用树来表示源程序的语法结构；在数据库系统中，用树来组织信息。法结构；在数据库系统中，用树来组织信息。14 八月 20235.1 5.1 树的基本概念树的基本概念 树（树（treetree）是）是n n（n0n0）个有限数据元素的集合，当）个有限数据元素的集合，当集合为空时称为集合为空时称为空树空树，否则它满足如下两个条件：，否则它满足如下两个条件：（1 1）有且仅有一个特定的结点称之为根（）有且仅有一

3、个特定的结点称之为根（rootroot）。）。（2 2）其余的结点可分为）其余的结点可分为m m（m0m0）个互不相交的子集）个互不相交的子集T1,T2,T1,T2,Tm,Tm，其中每个子集又是一棵树，并称为根，其中每个子集又是一棵树，并称为根的子树（的子树（subtreesubtree）。每棵子树的根结点有且仅有一个）。每棵子树的根结点有且仅有一个直接前驱，但可以有零个或多个直接后继。直接前驱，但可以有零个或多个直接后继。5.1.1 5.1.1 树的定义树的定义14 八月 2023 树的定义是一个递归的定义。树的定义是一个递归的定义。下图是树的示例，其中图下图是树的示例，其中图(a)(a)是

4、一棵空树；图是一棵空树；图(b)(b)是一棵只是一棵只有根结点的树；图有根结点的树；图(c)(c)是一棵具有是一棵具有1111个结点的树，即个结点的树，即T=A,B,C,D,E,F,G,H,I,J,KT=A,B,C,D,E,F,G,H,I,J,K，结点，结点A A为树为树T T的根结点，除根结的根结点，除根结点点A A之外的其余结点分为之外的其余结点分为3 3个不相交的集合：个不相交的集合：T1=B,E,FT1=B,E,F，T2=CT2=C，T3=D,G,H,I,J,KT3=D,G,H,I,J,K，它们构成了结点，它们构成了结点A A的的3 3棵子树，棵子树，T1T1、T2T2、T3T3本身也

5、分别是一棵树。本身也分别是一棵树。14 八月 2023 从树的定义和示例可以看出，树的逻辑结构具有下面从树的定义和示例可以看出，树的逻辑结构具有下面的特点：的特点：（1 1）树中结点，只有根结点没有前驱。）树中结点，只有根结点没有前驱。（2 2）除根结点外，其余结点都有且仅有一个前驱。）除根结点外，其余结点都有且仅有一个前驱。（3 3）树的结点，可以有零个或多个后继。）树的结点，可以有零个或多个后继。（4 4）除根结点以外的其他结点，都存在唯一一条从根）除根结点以外的其他结点，都存在唯一一条从根结点到该结点的路径。结点到该结点的路径。（5 5）树是一种分支结构。）树是一种分支结构。由此特点可知

6、，下图所示的不是树结构。由此特点可知，下图所示的不是树结构。14 八月 2023 树可以表示具有分支结构关系的对象。例如，家族树可以表示具有分支结构关系的对象。例如，家族族谱和单位行政机构的组织关系等。族谱和单位行政机构的组织关系等。树也是常用的数据组织形式。树也是常用的数据组织形式。有些应用中数据元素之间并不存在分支结构关系，有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组但是为了便于管理和使用数据，将它们用树的形式来组织。例如，在计算机的文件系统中，不论是织。例如，在计算机的文件系统中，不论是DOSDOS文件系统文件系统还是还是WindowsWi

7、ndows文件系统，所有的文件都是用树的形式来组文件系统，所有的文件都是用树的形式来组织的，如下图所示。织的，如下图所示。14 八月 2023 结点：是指树中的一个数据元素，一般用一个字母表结点：是指树中的一个数据元素，一般用一个字母表示。示。结点的度：一个结点包含子树的数目。结点的度：一个结点包含子树的数目。树的度：树中结点度的最大值。树的度：树中结点度的最大值。叶子：度为叶子：度为0 0的结点称为叶子结点或树叶，也叫终端结的结点称为叶子结点或树叶，也叫终端结点。点。分支结点：度不为分支结点：度不为0 0的结点称为分支结点，也叫非终端结的结点称为分支结点，也叫非终端结点。点。孩子结点：树中一

8、个结点的子树的根结点称为这个结点孩子结点：树中一个结点的子树的根结点称为这个结点的孩子结点，也称为孩子、儿子、子女等。的孩子结点，也称为孩子、儿子、子女等。5.1.2 5.1.2 有关树的基本术语有关树的基本术语14 八月 2023 双亲结点：若树中的某个结点有孩子结点，则这个双亲结点：若树中的某个结点有孩子结点，则这个结点就称为它的孩子结点的双亲结点。结点就称为它的孩子结点的双亲结点。祖先结点：从根结点到该结点所经过分支上的所有祖先结点：从根结点到该结点所经过分支上的所有结点为该结点的祖先结点。结点为该结点的祖先结点。子孙结点：某一结点的孩子及孩子的孩子都为该结子孙结点：某一结点的孩子及孩子

9、的孩子都为该结点的子孙结点。点的子孙结点。兄弟结点：具有同一个双亲的结点，称为兄弟结兄弟结点：具有同一个双亲的结点，称为兄弟结点。点。层数：根结点的层数为层数：根结点的层数为1 1，其他结点的层数为从根结，其他结点的层数为从根结点到该结点所经过的分支数目再加点到该结点所经过的分支数目再加1 1。树的高度（深度）：树中结点所处的最大层数称为树的高度（深度）：树中结点所处的最大层数称为树的高度。树的高度。14 八月 2023 有序树：若一棵树中所有子树从左到右的排序是有顺有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序，称该树为有序树。序的，不能颠倒次序，称该树为有序树。无序树：若

10、一棵树中所有子树的次序无关紧要，则称无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。为无序树。森林：森林：m m（m0m0）棵互不相交的树组成的集合称为森）棵互不相交的树组成的集合称为森林。从定义可知，一棵树由根结点和林。从定义可知，一棵树由根结点和m m棵子树组成，若把树棵子树组成，若把树中的根结点删除，则树就变成了包含中的根结点删除，则树就变成了包含m m棵子树的森林。棵子树的森林。14 八月 20235.25.2 二叉树二叉树 二叉树（二叉树（binary treebinary tree）：由结点的有限集合构）：由结点的有限集合构成，这个集合或为空集，或由一个根结点及两棵不相成，

11、这个集合或为空集，或由一个根结点及两棵不相交的分别称为这个根结点的左子树和右子树的树构成，交的分别称为这个根结点的左子树和右子树的树构成，并且左、右子树本身也是二叉树。当集合为空时，称并且左、右子树本身也是二叉树。当集合为空时，称该二叉树为该二叉树为空二叉树空二叉树。在二叉树中，一个元素也称为。在二叉树中，一个元素也称为一个结点。一个结点。5.2.1 5.2.1 二叉树的基本概念二叉树的基本概念14 八月 2023 二叉树有以下几个特点：二叉树有以下几个特点：（1 1）二叉树中每个结点最多有两棵子树，二叉树每个结）二叉树中每个结点最多有两棵子树，二叉树每个结点的度小于等于点的度小于等于2 2。

12、（2 2）二叉树是有序的，其左、右子树不能颠倒，否则就）二叉树是有序的，其左、右子树不能颠倒，否则就成为另一棵不同的二叉树，即使只有一个结点也要区成为另一棵不同的二叉树，即使只有一个结点也要区分它是左子树还是右子树。分它是左子树还是右子树。（3 3）二叉树是递归结构，在二叉树的定义中又用到了二）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。叉树的概念。二叉树具有二叉树具有5 5种基本形态，如下图所示。种基本形态，如下图所示。14 八月 2023 二叉树、树及有序树是有区别的，二叉树不是树的特二叉树、树及有序树是有区别的，二叉树不是树的特例，主要差别在于二叉树的子树有左右之分。例，主要

13、差别在于二叉树的子树有左右之分。在有序树中，虽然一个结点的孩子之间是有左右次序在有序树中，虽然一个结点的孩子之间是有左右次序的，但若该结点只有一个孩子时，就无须区分其左右次序。的，但若该结点只有一个孩子时，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。例如，而在二叉树中，即使是一个孩子也有左右之分。例如，由由3 3个结点构成的树和二叉树的所有形态就明显不同，如下个结点构成的树和二叉树的所有形态就明显不同，如下图所示。图所示。14 八月 2023 满二叉树：在一棵二叉树中，如果所有分支结点都存满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都集中

14、在树的最下在左子树和右子树，并且所有叶子结点都集中在树的最下一层，这样的一棵二叉树称为满二叉树。一层，这样的一棵二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到最大值。满二叉树的特点是每一层的结点数都达到最大值。完全二叉树：一棵含有完全二叉树：一棵含有n n个结点的二叉树，对树中的个结点的二叉树，对树中的结点按从上到下、从左到右的顺序进行编号，如果树中所结点按从上到下、从左到右的顺序进行编号，如果树中所含的含的n n个结点和满二叉树中个结点和满二叉树中14 八月 2023 编号为编号为1n1n的结点一一对应，则这棵二叉树就称为的结点一一对应，则这棵二叉树就称为完全二叉树。完全二叉树。完

15、全二叉树的特点：叶子结点只能出现在最下层和完全二叉树的特点：叶子结点只能出现在最下层和次下层，也就是说至多是最下面的两层上结点的度数可次下层，也就是说至多是最下面的两层上结点的度数可以小于以小于2 2，且最下层的叶子结点集中在树的左部。，且最下层的叶子结点集中在树的左部。满二叉树必定是完全二叉树，完全二叉树未必是满满二叉树必定是完全二叉树，完全二叉树未必是满二叉树。二叉树。14 八月 2023 下图下图(a)(a)和图和图(b)(b)就是完全二叉树，而图就是完全二叉树，而图(c)(c)和图和图(b)(b)就就不是完全二叉树。不是完全二叉树。14 八月 2023 性质性质1 1 一棵非空二叉树的

16、第一棵非空二叉树的第i i层上最多有层上最多有2 2i-1i-1个结点个结点（i1i1）。）。性质性质2 2 深度为深度为k k的二叉树最多具有的二叉树最多具有2 2k-1k-1个结点（个结点（k1k1）。）。由性质由性质1 1可知，第可知，第i i层的最大结点数为层的最大结点数为2 2i-1i-1（1ik1ik），则深），则深度为度为k k的二叉树的最大结点数为的二叉树的最大结点数为2 20 0+2+21 1+2+2k-1k-1=2=2k-1k-1。5.2.2 5.2.2 二叉树的性质二叉树的性质14 八月 2023 性质性质3 3 对于一棵非空的二叉树，如果叶子结点数为对于一棵非空的二叉树

17、，如果叶子结点数为n n0 0，度数为，度数为2 2的结点数为的结点数为n n2 2，则有，则有n n0 0=n=n2 21 1。性质性质4 4 具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度k k为为loglog2 2n+1n+1。性质性质5 5 对于具有对于具有n n个结点的完全二叉树，如果按照个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从从上到下和从左到右的顺序对二叉树中的所有结点从1 1开始顺序编号，则对于任意的序号为开始顺序编号，则对于任意的序号为i i的结点，有以下的结点，有以下性质：性质：14 八月 2023 （1 1）如果）如果i=1

18、i=1，则序号为，则序号为i i的结点是根结点，无双亲结点；的结点是根结点，无双亲结点；如果如果i i1 1，则序号为，则序号为i i的结点的双亲结点的序号为的结点的双亲结点的序号为i/2 i/2。（2 2）如果）如果2in2in，则序号为，则序号为i i的结点的左孩子结点的序号为的结点的左孩子结点的序号为2i2i；如果；如果2i2in n，则序号为，则序号为i i的结点无左孩子。的结点无左孩子。（3 3）如果）如果2i+1n2i+1n，则序号为，则序号为i i的结点的右孩子结点的序号的结点的右孩子结点的序号为为2i+12i+1；如果；如果2i+12i+1n n，则序号为，则序号为i i的结点

19、无右孩子。的结点无右孩子。完全二叉树如下图所示：完全二叉树如下图所示：14 八月 2023 1 1顺序存储结构顺序存储结构 二叉树的顺序存储是使用一组连续的空间存储二叉二叉树的顺序存储是使用一组连续的空间存储二叉树的数据元素和数据元素之间的关系。树的数据元素和数据元素之间的关系。完全二叉树和满二叉树采用顺序存储比较合适，因完全二叉树和满二叉树采用顺序存储比较合适，因为树中结点的序号可以反映出结点之间的逻辑关系。为树中结点的序号可以反映出结点之间的逻辑关系。1 1）完全二叉树的顺序存储）完全二叉树的顺序存储5.2.3 5.2.3 二叉树的存储结构二叉树的存储结构14 八月 2023 完全二叉树从

20、一个结点的编号就可推知其双亲、完全二叉树从一个结点的编号就可推知其双亲、左右孩子等结点的编号。左右孩子等结点的编号。假设编号假设编号i i的结点是的结点是k ki i（1in1in），则有），则有:（1 1）若）若i i1 1，则，则k ki i的双亲结点编号为的双亲结点编号为 ；若；若i=1i=1，则，则k ki i是根结点，无双亲结点。是根结点，无双亲结点。（2 2）若）若2in2in，则，则k ki i的左孩子结点的编号为的左孩子结点的编号为2i2i，否，否则则kiki无左孩子结点，即无左孩子结点，即kiki是叶子结点。因此完全二叉是叶子结点。因此完全二叉树中编号树中编号i i 的结点必

21、定是叶子结点。的结点必定是叶子结点。（3 3）若）若2i+1n2i+1n，则，则k ki i的右孩子结点编号是的右孩子结点编号是2i+12i+1；否则否则k ki i无右孩子结点。无右孩子结点。14 八月 2023 可用一维数组可用一维数组btbt存放一棵完全二叉树，将标号存放一棵完全二叉树，将标号为为i i的结点的数据元素存放在分量的结点的数据元素存放在分量btibti 中，中，bt0bt0不用不用或用来存储结点数目。或用来存储结点数目。下图是下图是5.2.25.2.2中所示的完全二叉树的顺序存储示意中所示的完全二叉树的顺序存储示意图。例如，图。例如，bt3bt3的双亲为的双亲为 =1=1，

22、即在，即在bt1bt1中，其中，其左孩子在左孩子在bt2i=bt6bt2i=bt6中，右孩子在中，右孩子在bt2i+1=bt7bt2i+1=bt7中。中。14 八月 2023 2 2）一般二叉树的顺序存储）一般二叉树的顺序存储 一般的二叉树采取的办法是按完全二叉树的形式补齐二一般的二叉树采取的办法是按完全二叉树的形式补齐二叉树所缺少的结点，对补齐后的二叉树进行编号，将二叉叉树所缺少的结点，对补齐后的二叉树进行编号，将二叉树的原有结点按编号存储到一维数组中。树的原有结点按编号存储到一维数组中。下图给出了一棵一般二叉树改造后的完全二叉树形态和下图给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存

23、储状态示意图。其顺序存储状态示意图。14 八月 2023 这种存储需增加许多空结点才能将一棵二叉树改造这种存储需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树，会造成空间的大量浪费，不宜用成为一棵完全二叉树，会造成空间的大量浪费，不宜用顺序存储结构。顺序存储结构。二叉树顺序存储结构适合于完全二叉树，既不浪费二叉树顺序存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置以及结点的双存储空间，又能很快确定结点的存放位置以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费，特别是深度和结点数的比例偏高的二存

24、储空间的浪费，特别是深度和结点数的比例偏高的二叉树。叉树。14 八月 2023 2 2链式存储结构链式存储结构 1 1）二叉链表存储）二叉链表存储 二叉树的每个结点最多有两个孩子，在每个结点中二叉树的每个结点最多有两个孩子，在每个结点中除了存储结点本身的数据外再设置两个指针域除了存储结点本身的数据外再设置两个指针域lchildlchild和和rchildrchild，分别指向结点的左孩子和右孩子，当结点的某，分别指向结点的左孩子和右孩子，当结点的某个孩子为空时，则相应的指针为空指针。个孩子为空时，则相应的指针为空指针。C C 语言的类型描述如下：语言的类型描述如下：14 八月 2023type

25、def struct BiTNodetypedef struct BiTNode /结点结构结点结构ElemTypeElemType data;data;struct BiTNode *lchild,*rchildstruct BiTNode *lchild,*rchild;/;/左右孩子指针左右孩子指针 BiTNode,*BiTree BiTNode,*BiTree;一棵二叉树里所有这样形式的结点，再加上一个指向一棵二叉树里所有这样形式的结点，再加上一个指向树根的指针（根指针），即可构成二叉树的存储表示，这种树根的指针（根指针），即可构成二叉树的存储表示，这种存储方法称为二叉链表。存储方法称

26、为二叉链表。下图给出了顺序存储示意图下图给出了顺序存储示意图(a)(a)所示的一棵二叉树的二所示的一棵二叉树的二叉链表表示。叉链表表示。14 八月 2023 2 2）三叉链表存储）三叉链表存储 在结点中增加了一个指向其双亲结点的指针域。在结点中增加了一个指向其双亲结点的指针域。下图给出了顺序存储示意图下图给出了顺序存储示意图(a)(a)所示二叉树的三叉链表所示二叉树的三叉链表表示。表示。14 八月 2023 1.1.二叉树的遍历二叉树的遍历 遍历二叉树（遍历二叉树（traversing binary treetraversing binary tree）：按照）：按照某种顺序访问二叉树中的每个

27、结点，使每个结点恰被某种顺序访问二叉树中的每个结点，使每个结点恰被访问一次。访问一次。1 1）二叉树的遍历方法）二叉树的遍历方法 一棵非空二叉树的遍历可以分解为一棵非空二叉树的遍历可以分解为3 3个子问题：访个子问题：访问根结点，遍历左子树和遍历右子树。问根结点，遍历左子树和遍历右子树。5.2.4 5.2.4 二叉树的遍历和线索二叉树二叉树的遍历和线索二叉树14 八月 2023 令令L L、D D、R R分别表示遍历左子树、访问根结点、遍历分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右，则按照访问根结点的先后次序右子树，限定先左后右，则按照访问根结点的先后次序不同分别称之为：先序遍历

28、不同分别称之为：先序遍历(DLR)(DLR)、中序遍历、中序遍历(LDR)(LDR)和后和后序遍历序遍历(LRD)(LRD)。3 3种遍历方法的具体实现过程：种遍历方法的具体实现过程：先序遍历过程如下：先序遍历过程如下：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：（1 1）访问根结点。）访问根结点。（2 2）先序遍历左子树。）先序遍历左子树。（3 3）先序遍历右子树。）先序遍历右子树。14 八月 2023中序遍历过程如下：中序遍历过程如下：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：（1 1）中序遍历左子树。）中序遍历左子树。（2 2）访问根结点。）访问根结点。

29、（3 3）中序遍历右子树。）中序遍历右子树。后序遍历过程：后序遍历过程：若二叉树为空，则空操作；否则：若二叉树为空，则空操作；否则：（1 1）后序遍历左子树。）后序遍历左子树。（2 2）后序遍历右子树。）后序遍历右子树。（3 3）访问根结点。）访问根结点。14 八月 2023 【例【例5-15-1】假设访问二叉树假设访问二叉树T T的结点的操作是输出结点的结点的操作是输出结点的值，请分别写出如下图所示的二叉树的先序、中序和后的值，请分别写出如下图所示的二叉树的先序、中序和后序遍历序列。序遍历序列。14 八月 2023解：该问题的求解序列如下：解：该问题的求解序列如下：A A ;A B A B

30、B BL L B BR R F F F FL L F FR R ;A B C A B C D D F G F G I I。由此可以写出先序遍历序列为：由此可以写出先序遍历序列为：ABCDEFGHIJABCDEFGHIJ同样的方法可得其他遍历序列分别如下：同样的方法可得其他遍历序列分别如下：中序：中序：CBEDAGHFIJCBEDAGHFIJ后序：后序：CEDBHGJIFACEDBHGJIFA14 八月 2023 【例【例5-25-2】已知二叉树的先序和中序序列如下，试已知二叉树的先序和中序序列如下，试构造出相应的二叉树。构造出相应的二叉树。先序：先序：ABCDEFGHIABCDEFGHI中序：

31、中序：CDBAGFEHICDBAGFEHI 解：（解：（1 1）根结点的确定：由先序遍历的描述可知，）根结点的确定：由先序遍历的描述可知，先序序列中的第一个结点为根结点。因此，本题中的根先序序列中的第一个结点为根结点。因此，本题中的根结点为结点为A A。14 八月 2023 （2 2）左右子树的确定：根结点）左右子树的确定：根结点A A将左右子树的中序序将左右子树的中序序列划分为列划分为CDBCDB和和GFEHIGFEHI，左、右子树的先序序列在先序序列，左、右子树的先序序列在先序序列中是连在一起的，分别为中是连在一起的，分别为BCDBCD和和EFGHIEFGHI，求解过程如下图所，求解过程如

32、下图所示。示。14 八月 20232 2）遍历算法的递归描述）遍历算法的递归描述 先序遍历算法如算法先序遍历算法如算法5.15.1所示。所示。void PreOrder(BiTreevoid PreOrder(BiTree T)T)/先序遍历以先序遍历以T T为根指针的二叉树的算法为根指针的二叉树的算法if(T)if(T)Visit(T Visit(T-data);-data);/访问访问T T的根结点的根结点 PreOrder(T-lchildPreOrder(T-lchild););/先序遍历先序遍历T T的左子树的左子树 PreOrder(T-rchildPreOrder(T-rchil

33、d););/先序遍历先序遍历T T的右子树的右子树 算法算法5.1 5.1 14 八月 2023中序遍历算法如算法中序遍历算法如算法5.25.2所示。所示。void InOrder(BiTreevoid InOrder(BiTree T)T)/中序遍历以中序遍历以T T为根指针的二叉树的算法为根指针的二叉树的算法if(T)if(T)InOrder(T-lchild InOrder(T-lchild););/中序遍历中序遍历T T的左子树的左子树 Visit(TVisit(T-data);-data);/访问访问T T的根结点的根结点 InOrder(T-rchildInOrder(T-rchi

34、ld););/中序遍历中序遍历T T的右子树的右子树 /InOrder/InOrder算法算法5.25.214 八月 2023 后序遍历算法如算法后序遍历算法如算法5.35.3所示。所示。void PostOrder(BiTreevoid PostOrder(BiTree T)T)/后序遍历以后序遍历以T T为根指针的二叉树的算法为根指针的二叉树的算法if(T)if(T)PostOrder(T-lchild PostOrder(T-lchild););/后序遍历后序遍历T T的左子树的左子树 PostOrder(T-rchildPostOrder(T-rchild););/后序遍历后序遍历T

35、T的右子树的右子树 Visit(TVisit(T-data);-data);/访问访问T T的根结点的根结点 /PostOrder/PostOrder算法算法5.35.314 八月 2023 3 3）二叉树的层次遍历）二叉树的层次遍历 二叉树的层次遍历是指从二叉树的第一层开始，自上二叉树的层次遍历是指从二叉树的第一层开始，自上而下逐层遍历，在同一层中，则按从左到右的顺序对结点而下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。逐个访问。在进行层次遍历时，可设置一个队列结构，遍历从二在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队叉树的根结

36、点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：头取出一个元素，每取一个元素，执行下面两个操作：（1 1）访问该元素所指结点。）访问该元素所指结点。（2 2）若该元素所指结点的左、右孩子结点非空，则将）若该元素所指结点的左、右孩子结点非空，则将 该元素所指结点的左孩子指针和右孩子指针顺序入该元素所指结点的左孩子指针和右孩子指针顺序入队。队。具体过程如算法具体过程如算法5.45.4所示。所示。14 八月 2023Status LevelOrder(BiTreeStatus LevelOrder(BiTree T)T)层序遍历二叉树层序遍历二叉树T Tif(

37、Tif(T=NULL)return ERROR;=NULL)return ERROR;若若T T为空树，则直接返回为空树，则直接返回InitQueue(QInitQueue(Q););初始化一个队列初始化一个队列EnQueue(Q,TEnQueue(Q,T););根结点入队根结点入队while(!QueueEmpty(Qwhile(!QueueEmpty(Q)若队列非空若队列非空DeQueue(Q,pDeQueue(Q,p););队头元素出队并访问它队头元素出队并访问它Visit(pVisit(p-data);-data);if(p-lchild)EnQueue(Q,p-lchildif(p-

38、lchild)EnQueue(Q,p-lchild););若其左孩子不空，则将其左孩子入队若其左孩子不空，则将其左孩子入队if(p-rchild)EnQueue(Q,p-rchildif(p-rchild)EnQueue(Q,p-rchild););若其右孩子不空，则将其右孩子入队若其右孩子不空，则将其右孩子入队 return OK;return OK;算法算法5.45.414 八月 2023 4 4）遍历算法的简单应用）遍历算法的简单应用 【例【例5-35-3】设计算法按中序次序输出二叉树设计算法按中序次序输出二叉树T T中度为中度为2 2的结点的值。的结点的值。算法思想：算法思想：本例算法

39、的基本思想和中序遍历算法相似。相同之处本例算法的基本思想和中序遍历算法相似。相同之处是输出次序均为中序；不同之处是要输出其中度为是输出次序均为中序；不同之处是要输出其中度为2 2的结的结点的值，即有条件输出。为此，只需将中序遍历中的访问点的值，即有条件输出。为此，只需将中序遍历中的访问改为条件输出即可。改为条件输出即可。14 八月 2023 具体过程如算法具体过程如算法5.55.5所示。所示。void InOrder2(BiTree T)void InOrder2(BiTree T)/按中序次序输出二叉树按中序次序输出二叉树T T中的度为中的度为2 2的结点的值的结点的值if(T)if(T)I

40、nOrder2(T-lchildInOrder2(T-lchild););/按要求输出左子树中满足条件的结点值按要求输出左子树中满足条件的结点值if(T-lchild&T-rchildif(T-lchild&T-rchild)/当前结点满足条件时输出其值当前结点满足条件时输出其值 printf(%c,Tprintf(%c,T-data);-data);InOrder2(T-rchildInOrder2(T-rchild););/按要求输出右子树中满足条件的结点值按要求输出右子树中满足条件的结点值 /InOrder2/InOrder2算法算法5.5 5.5 14 八月 2023 【例【例5-45

41、-4】求二叉树的深度。求二叉树的深度。算法思想：算法思想：首先分析二叉树的深度和它的左、右子树深度之间的关首先分析二叉树的深度和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的较大值加子树深度的较大值加1 1。由此，需先分别求得左、右子树的。由此，需先分别求得左、右子树的深度。深度。递归算法设计可分为递归项和终止项，在本题中：递归算法设计可分为递归项和终止项，在本题中：终止项：当二叉树终止项：当二叉树T T为空，则其深度为为空，则其深度为0 0。递归项：当递归项：当T T不为空时，其深度等于其左右子树深

42、度较大值不为空时，其深度等于其左右子树深度较大值加加1 1。得到求二叉树深度的算法如算法得到求二叉树深度的算法如算法5.65.6所示。所示。14 八月 2023int Depth(BiTreeint Depth(BiTree T)T)/计算二叉树计算二叉树T T的深度的深度if(!T)return 0;if(!T)return 0;/若若T T为空，则其深度为为空，则其深度为0 0else else/若若T T不空，则返回其子树中深度较大值加不空，则返回其子树中深度较大值加1 1if(Depth(T-lchild)=Depth(T-rchildif(Depth(T-lchild)=Depth(

43、T-rchild)return Depth(T return Depth(T-lchild)+1;-lchild)+1;else return Depth(Telse return Depth(T-rchild)+1;-rchild)+1;算法算法5.6 5.6 14 八月 2023 2 2线索二叉树线索二叉树 把在二叉树某种遍历序列中两个相邻的结点互称把在二叉树某种遍历序列中两个相邻的结点互称为前驱与后继。为前驱与后继。在某些操作中会频繁地使用某个结点的前驱或后继在某些操作中会频繁地使用某个结点的前驱或后继信息，而这些信息只能在遍历的过程中动态得到，因此信息，而这些信息只能在遍历的过程中动态

44、得到，因此会想到使用某种方法把这些信息保存起来。会想到使用某种方法把这些信息保存起来。14 八月 2023 若将二叉树采用二叉链表存储，则具有若将二叉树采用二叉链表存储，则具有n n个结点的个结点的二叉树有二叉树有2n2n个指针域，在个指针域，在2n2n个指针域中有个指针域中有n-1n-1个指针域指个指针域指向结点的孩子，而其余向结点的孩子，而其余n+1n+1个指针域为空，可以利用这些个指针域为空，可以利用这些空指针域来指向结点的前驱和后继的位置。这些指向前空指针域来指向结点的前驱和后继的位置。这些指向前驱或后继结点的指针就称为驱或后继结点的指针就称为线索线索，加上线索的二叉树叫，加上线索的二

45、叉树叫线索二叉树线索二叉树。而对二叉树按某种遍历次序使其变为线索。而对二叉树按某种遍历次序使其变为线索二叉树的过程就叫二叉树的过程就叫线索化线索化。14 八月 2023 按不同的方式遍历二叉树所得到的线索二叉树是不相按不同的方式遍历二叉树所得到的线索二叉树是不相同的。对如下图同的。对如下图(a)(a)所示的二叉树进行线索化，得到先序线所示的二叉树进行线索化，得到先序线索二叉树、中序线索二叉树和后序线索二叉树分别如图索二叉树、中序线索二叉树和后序线索二叉树分别如图(b)(b)、图图(c)(c)、如、如(d)(d)所示。图中实线表示原来的指针，虚线表示所示。图中实线表示原来的指针，虚线表示新增加的

46、线索。新增加的线索。14 八月 2023 为了区分指针和线索，需要在每个结点中增设两个为了区分指针和线索，需要在每个结点中增设两个线索标志位线索标志位LTagLTag和和RTagRTag，分别指示左右指针位置存储的，分别指示左右指针位置存储的是线索还是指针，标志位定义如下：是线索还是指针，标志位定义如下：0 lchild0 lchild指向结点的左孩子指向结点的左孩子1 lchild1 lchild指向结点的前驱结点指向结点的前驱结点0 rchild0 rchild指向结点的右孩子指向结点的右孩子1 rchild1 rchild指向结点的后继结点指向结点的后继结点14 八月 2023这样每个结

47、点的存储结构就变为这样每个结点的存储结构就变为 ：线索二叉树结点类型可以描述为：线索二叉树结点类型可以描述为：typedef struct BiThrNodetypedef struct BiThrNode TElemTypeTElemType data;data;struct BiThrNodestruct BiThrNode*lchild,*rchild*lchild,*rchild;/左右指针左右指针int LTag,RTagint LTag,RTag;/左右标志左右标志 BiThrNode,*BiThrTree BiThrNode,*BiThrTree;14 八月 2023 为了将二叉

48、树中所有指针都利用上，以及算法设为了将二叉树中所有指针都利用上，以及算法设计方便的需要，一般在设计线索二叉树时增设一头结计方便的需要，一般在设计线索二叉树时增设一头结点。点。头结点其数据域不存放信息，其左指针域指向二头结点其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。一个结点。原二叉树在某序遍历下的第一个结点的前驱线索原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点，从而构和最后一个结点的后继线索都指向该头结点，从而构成一个双向线索链表。成一个双向线索链表。14 八月 2

49、023下图是前一图下图是前一图(a)(a)的带头结点的中序线索二叉树结构图。的带头结点的中序线索二叉树结构图。14 八月 2023 中序线索二叉树为例，讨论线索二叉树的建立、线中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历等操作的实现算法。索二叉树的遍历等操作的实现算法。1 1）中序线索二叉树的遍历）中序线索二叉树的遍历 中序线索二叉树的遍历也就是求每个结点的中序后中序线索二叉树的遍历也就是求每个结点的中序后继的问题。设指针继的问题。设指针p p所指结点的左右子树分别为所指结点的左右子树分别为pLpL和和pRpR，中序遍历的次序为，中序遍历的次序为pLpL、p p、pRpR，现分析

50、如下：（，现分析如下：（1 1）若若pRpR不空，则不空，则pRpR中序遍历序列中的第一个结点中序遍历序列中的第一个结点为为p p的后继。中序遍历中某结点的中序后继就是其右子的后继。中序遍历中某结点的中序后继就是其右子树的最左下结点。树的最左下结点。（2 2）若）若pRpR为空（即为空（即p p无右孩子），无右孩子），p p的右孩子指针为的右孩子指针为后继线索，即后继线索，即p-rchildp-rchild为其中序后继的指针。为其中序后继的指针。在中序遍历前还要先确定中序遍历的第一个结点，在中序遍历前还要先确定中序遍历的第一个结点，显然中序遍历的第一个结点就是根结点左子树的最左下显然中序遍历的

51、第一个结点就是根结点左子树的最左下结点。结点。遍历中序线索二叉树的具体过程如算法遍历中序线索二叉树的具体过程如算法5.85.8所示。所示。14 八月 2023Status InOrderTraverse_Thr(BiThrTreeStatus InOrderTraverse_Thr(BiThrTree T)T)中序遍历二叉线索链表表示的二叉树中序遍历二叉线索链表表示的二叉树p=T-lchild;pp=T-lchild;p指左孩子结点指左孩子结点while(pwhile(p!=T)!=T)空树或遍历结束时，空树或遍历结束时，p p等于等于 T Twhile(p-LTag=0)p=p-lchild

52、while(p-LTag=0)p=p-lchild;找最左下结点并访问找最左下结点并访问 Visit(pVisit(p-data);-data);while(p-RTag=1&p-rchildwhile(p-RTag=1&p-rchild!=T)!=T)访问后继线索结点访问后继线索结点 p=p-rchild;Visit(pp=p-rchild;Visit(p-data);-data);p=p-rchildp=p-rchild;如不是后继访问其右子树如不是后继访问其右子树 return OK;return OK;InOrderTraverse_ThrInOrderTraverse_Thr算法算法

53、5.85.814 八月 2023 2 2）中序线索化）中序线索化 实质上就是在中序遍历二叉树的过程中，检查当实质上就是在中序遍历二叉树的过程中，检查当前结点的左、右指针域是否为空，若为空，则将它们前结点的左、右指针域是否为空，若为空，则将它们改为指向前驱结点或后继结点的线索。改为指向前驱结点或后继结点的线索。每个结点线索化操作包括：若其左子树为空，左每个结点线索化操作包括：若其左子树为空，左标志置标志置1 1，左指针指向其前驱；若其右子树为空，右标，左指针指向其前驱；若其右子树为空，右标志置志置1 1，右指针指向其后继。，右指针指向其后继。后继线索化可采用如下办法，对于后继线索化可采用如下办法

54、，对于p p所指结点的线所指结点的线索化分为两步：索化分为两步：14 八月 2023（1）当）当p所指结点为当前结点，前驱线索化。所指结点为当前结点，前驱线索化。（2）当）当p所指结点的后继结点为当前结点，后继线所指结点的后继结点为当前结点，后继线索化。索化。算法算法5.9的功能是在原二叉树上增加一个头结点，的功能是在原二叉树上增加一个头结点，并完成头结点和最后一个结点的线索化，算法并完成头结点和最后一个结点的线索化，算法5.10主要主要是完成中间结点的线索化。是完成中间结点的线索化。14 八月 2023Status InOrderThreading(BiThrTree&Thrt,BiThrT

55、reeStatus InOrderThreading(BiThrTree&Thrt,BiThrTree T)T)中序遍历二叉树中序遍历二叉树T T，并将其中序线索化，并将其中序线索化，ThrtThrt指向头结点指向头结点Thrt=(BiThrTree)malloc(sizeof(BiThrNodeThrt=(BiThrTree)malloc(sizeof(BiThrNode););建头结点建头结点Thrt-LTag=0;Thrt-RTagThrt-LTag=0;Thrt-RTag=1;=1;Thrt-rchild=ThrtThrt-rchild=Thrt;右指针回指右指针回指if(!T)Thr

56、t-lchild=Thrtif(!T)Thrt-lchild=Thrt;若二叉树空，则左指针回指若二叉树空，则左指针回指elseelseThrt-lchild=T;pre=ThrtThrt-lchild=T;pre=Thrt;InThreading(TInThreading(T););算法算法5.10 5.10 中序遍历进行中序线索化中序遍历进行中序线索化pre-rchild=Thrt;pre-RTagpre-rchild=Thrt;pre-RTag=1;=1;最后一个结点线索化最后一个结点线索化Thrt-rchildThrt-rchild=pre;=pre;return OK;return

57、OK;InOrderThreadingInOrderThreading算法算法5.95.914 八月 2023void InThreading(BiThrTreevoid InThreading(BiThrTree p)p)if(pif(p)InThreading(p-lchildInThreading(p-lchild););左子树线索化左子树线索化if(!p-lchildif(!p-lchild)建前驱线索建前驱线索 p-LTag=1;p-lchildp-LTag=1;p-lchild=pre;=pre;if(!pre-rchildif(!pre-rchild)建后继线索建后继线索 pre

58、-RTag=1;pre-rchildpre-RTag=1;pre-rchild=p;=p;pre=p;pre=p;保持保持prepre指向指向p p的前驱的前驱InThreading(p-rchildInThreading(p-rchild););右子树线索化右子树线索化 InThreadingInThreading算法算法5.105.1014 八月 20235.3 5.3 树和森林树和森林 常用的树的存储方式主要有常用的树的存储方式主要有4 4种：种：双亲表示法双亲表示法孩子表示法孩子表示法双亲孩子表示法双亲孩子表示法孩子兄弟表示法。孩子兄弟表示法。1 1双亲表示法双亲表示法 双亲表示法就是

59、用双亲表示法就是用“指针指针”表示出每个结点的双亲结点。表示出每个结点的双亲结点。5.3.1 5.3.1 树的存储结构树的存储结构14 八月 2023 存储树中的结点时，应包含两个信息：结点值存储树中的结点时，应包含两个信息：结点值的信息和其双亲结点在数组中的序号。的信息和其双亲结点在数组中的序号。通常将这两个信息作为一个元素存放在一个一通常将这两个信息作为一个元素存放在一个一维数组中，数组中的一个元素表示树中的一个结点，维数组中，数组中的一个元素表示树中的一个结点，其存储表示可描述为：其存储表示可描述为：14 八月 2023#define MAXSIZE 100#define MAXSIZE

60、 100/树中结点的最大个数树中结点的最大个数typedef struct PTNodetypedef struct PTNode /结点结构结点结构ElemTypeElemType data;data;/结点信息域结点信息域intint parent;parent;/双亲位置域双亲位置域 PTNode PTNode;typedef structtypedef struct /树结构树结构PTNodePTNode nodes MAXSIZE;/nodes MAXSIZE;/带双亲信息的结点数组带双亲信息的结点数组intint r,n;r,n;/根结点的位置和结点个数根结点的位置和结点个数 PT

61、ree PTree;14 八月 2023 下图下图(a)(a)所示的树其双亲表示如图所示的树其双亲表示如图(b)(b)所示，图中的所示，图中的datadata域是结点信息域，域是结点信息域，parentparent域是指示其双亲结点在数组中下域是指示其双亲结点在数组中下标序号的游标域。标序号的游标域。(a)(b)14 八月 2023 双亲表示法对于在树中寻找一个结点的双亲结点双亲表示法对于在树中寻找一个结点的双亲结点的操作和求根结点的操作实现很方便。的操作和求根结点的操作实现很方便。但对于寻找某个结点的孩子结点的操作则需要查但对于寻找某个结点的孩子结点的操作则需要查询整个数组，实现很不方便。询

62、整个数组，实现很不方便。此外，这种存储方式不能反映各兄弟结点之间的此外，这种存储方式不能反映各兄弟结点之间的关系。关系。14 八月 2023 2 2孩子表示法孩子表示法 1 1）多重链表表示法）多重链表表示法 在这种表示法中，树中每个结点有多个指针域，在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法常称为多重链表表示法。形成了多条链表，所以这种方法常称为多重链表表示法。结点的指针域个数的设置有两种方法：结点的指针域个数的设置有两种方法：（1 1）每个结点指针域的个数等于该结点的度数。）每个结点指针域的个数等于该结点的度数。（2 2）每个结点指针域的个数等于树的度数。）每个

63、结点指针域的个数等于树的度数。14 八月 2023树的多重链表表示法如下图所示：树的多重链表表示法如下图所示：14 八月 2023 2 2）孩子链表表示法）孩子链表表示法 将树中所有结点存放在一个一维数组中，每个数组元将树中所有结点存放在一个一维数组中，每个数组元素由两个域组成，一个域用来存放结点信息，另一个用来存素由两个域组成，一个域用来存放结点信息，另一个用来存放指针，指向由该结点孩子组成的单链表的首位置。这个单放指针，指向由该结点孩子组成的单链表的首位置。这个单链表称作孩子链表，其每个结点也由两个域组成，一个存放链表称作孩子链表，其每个结点也由两个域组成，一个存放孩子结点在一维数组中的序

64、号，另一个是指针域，指向下一孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。个孩子。这种存储结构可以说明如下：这种存储结构可以说明如下：14 八月 2023typedef struct CTNodetypedef struct CTNode /孩子链表结点结构孩子链表结点结构intint child;child;/该孩子在数组中的下标序号该孩子在数组中的下标序号struct CTNodestruct CTNode*next;*next;/指示下一个孩子指示下一个孩子*ChildPtr*ChildPtr;typedef structtypedef struct /双亲结点结构双亲结点

65、结构ElemTypeElemType data;data;/结点信息域结点信息域ChildPtr firstchildChildPtr firstchild;/孩子链表的头指针孩子链表的头指针 CTBox CTBox;typedef structtypedef struct /树结构树结构CTBox nodesMAX_TREE_SIZECTBox nodesMAX_TREE_SIZE;/带孩子信息的结点数组带孩子信息的结点数组intint n,r;n,r;/结点数和根结点的位置结点数和根结点的位置 CTree CTree;14 八月 2023树的孩子链表表示法如下图所示树的孩子链表表示法如下图

66、所示 ：14 八月 2023 3 3双亲孩子表示法双亲孩子表示法 将孩子链表表示法与双亲表示法结合起来，形成双亲孩将孩子链表表示法与双亲表示法结合起来，形成双亲孩子表示法。子表示法。双亲表示法增设一个域，存储该结点双亲结点在数组中双亲表示法增设一个域，存储该结点双亲结点在数组中的序号。的序号。下图是双亲孩子表示法的存储示意图。下图是双亲孩子表示法的存储示意图。14 八月 2023 4 4孩子兄弟表示法孩子兄弟表示法 增加两个分别指向该结点的第一个孩子结点和下一增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：在这种存储结构下，树中结点的存储表示可描述为：typedef struct CSNodetypedef struct CSNode /结点结构结点结构ElemTypeElemType data;data;/结点信息域结点信息域struct CSNode *firstchild,*nextsiblingstruct CSNode *firstchild,*nextsibling;/第一个孩子和下一个兄弟指针第