第七章树与二叉树精选PPT.ppt

《第七章树与二叉树精选PPT.ppt》由会员分享，可在线阅读，更多相关《第七章树与二叉树精选PPT.ppt（155页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章树与二叉树第七章树与二叉树第1页，本讲稿共155页全校学生档案管理的组织方式全校学生档案管理的组织方式一树的应用一树的应用7.17.1 树的有关概念树的有关概念第2页，本讲稿共155页文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹11 11 文件夹文件夹12 12 文件文件11 11 文件文件1212C C 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件是用树的形式来组织文件系统，所有的文件是用树的形式来组织的。的。计算机的文件系统计算机的文件系统现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的

2、行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。第3页，本讲稿共155页二树的概念二树的概念 树是树是n个结点的有限集合，在任一棵非空树中：个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的）其余结点可分为个互不相交的集合，而且这些集合中的每每 一集合都本身又是一棵树，称为根的一集合都本身又是一棵树，称为根的子树子树。树是递归结构，在树的定义中又用到了树的概念J JI IA AC CB BD DH HG GF FE EK KL LM M第4页，本

3、讲稿共155页例：下面的图是一棵树例：下面的图是一棵树 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个个互不相交的集合：互不相交的集合：T T1 1=B,E,F=B,E,F，K K，L,TL,T2 2=C,G,T=C,G,T3 3=D,H,I,J=D,H,I,J，MM这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。例如例如例如例如 ：对于对于 T T1 1，B B是根，其余结点可以划分为是根，其余结点可以划分为2 2

4、个个互不相交的集合互不相交的集合 T1111=E，K，L，T1212=F，T1111,T1212 是是B 的子树。的子树。J JI IA AC CB BD DH HG GF FE EK KL LM M第5页，本讲稿共155页从逻辑结构看：从逻辑结构看：1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构）树是一种分枝结构 （除

5、了一个称为根的结点外）每个元素都有且（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。仅有一个直接前趋，有且仅有零个或多个直接后继。J JI IA AC CB BD DH HG GF FE EK KL LM M第6页，本讲稿共155页三树的表示三树的表示 1、图示表示 2、二元组表示 3、嵌套集合表示 4、凹入表示法（类似书的目录）AEDHJIKLMDGCABEKLFCGDHMJI5、广义表表示（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）第7页，本讲稿共155页树的结点：树的结点：树的结点：树的结点：包含一个数据元素及若干指向子树的分支；包

6、含一个数据元素及若干指向子树的分支；孩子结点：孩子结点：孩子结点：孩子结点：结点的子树的根称为该结点的孩子；结点的子树的根称为该结点的孩子；双亲结点：双亲结点：双亲结点：双亲结点：B 结点是结点是A 结点的孩子，则结点的孩子，则A结点是结点是B 结点的双亲结点的双亲；兄弟结点：兄弟结点：兄弟结点：兄弟结点：同一双亲的孩子结点；同一双亲的孩子结点；堂兄结点：堂兄结点：堂兄结点：堂兄结点：同一层上结点；同一层上结点；祖先结点祖先结点祖先结点祖先结点:从根到该结点的所经分支上的所有结点从根到该结点的所经分支上的所有结点;子孙结点：子孙结点：子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点

7、的子孙以某结点为根的子树中任一结点都称为该结点的子孙;结结结结 点点点点 层：层：层：层：根结点的层定义为根结点的层定义为1；根的孩子为第二层结点，依此类推。；根的孩子为第二层结点，依此类推。J JI IA AC CB BD DH HG GF FE EK KL LM M四树的四树的 基本术语基本术语第8页，本讲稿共155页树的深度树的深度树的深度树的深度：树中最大的结点层数；树中最大的结点层数；结点的度结点的度结点的度结点的度：结点子树的个数；结点子树的个数；树树树树 的的的的 度度度度：树中最大的结点度。树中最大的结点度。叶子结点叶子结点叶子结点叶子结点：也叫终端结点，是度为也叫终端结点，是

8、度为 0 的结点；的结点；分枝结点分枝结点分枝结点分枝结点：度不为度不为0的结点；的结点；有有有有 序序序序 树树树树：子树有序的树，如：家族树；子树有序的树，如：家族树；无无无无 序序序序 树树树树：不考虑子树的顺序；不考虑子树的顺序；森森森森 林林林林：互不相交的树集合；森林和树之间的联系是：一棵树去掉互不相交的树集合；森林和树之间的联系是：一棵树去掉 根根，其子树构成一个森林；一个森林增加一个根结点成为树。，其子树构成一个森林；一个森林增加一个根结点成为树。J JI IA AC CB BD DH HG GF FE EK KL LM M第9页，本讲稿共155页 树的应用很广，应用不同基本操

9、作也不同。下面列举了树的一些基本操作：树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1 1、initiate(T);T 树的初始化，包括建树。树的初始化，包括建树。2、root(T);求求T 树的根。树的根。3、parent(T,x):求求T 树中树中 x 结点的双亲结点。结点的双亲结点。4、Child(T,x,i)：求求 T 树中树中 x 结点的第结点的第 i 个孩子结点。个孩子结点。5、right_sibling(T,x):求求T 树中树中 x 结点的右兄弟结点的右兄弟6、insert_Child(y,i,x):将根为将根为 x 的子树置为的子树置为 y 结点的第结点的

10、第 i 个孩子个孩子7、del_child(x,i);删除删除 x 结点的第结点的第i 个孩子个孩子8、traverse(T);遍历遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都树。按某个次序依次访问树中每一个结点，并使每个结点都 被访问且只被访问一次。被访问且只被访问一次。9、clear(T);置空置空T 树树 五五.树的基本操作树的基本操作第10页，本讲稿共155页 树是一种分枝结构，在树的概念中，对每一树是一种分枝结构，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树种多样，本章我们主要

11、讨论一种最简单的树二叉树。二叉树。因为树的每个结点的度不同，存储困难，使对树的因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。处理算法很复杂。所以引出二叉树的讨论。第11页，本讲稿共155页二叉树二叉树7.2 7.2 二叉树二叉树1.二叉树的概念2.二叉树的性质3.二叉树的存储结构第12页，本讲稿共155页一一.二叉树的概念二叉树的概念 1 1、二叉树的定义、二叉树的定义说明说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;A A F F G G E E

12、 D D C C B B6.26.2 二二 叉叉 树树（Binary TreeBinary Tree）二二叉叉树树是是一一种种特特殊殊的的树树型型结结构构，特特点点是是树树中中每每个个结结点点只只有有两两棵子树，且子树有左右之分，次序不能颠倒。棵子树，且子树有左右之分，次序不能颠倒。第13页，本讲稿共155页 A A F F G G E E D D C C B B(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)A A G G E E D D B B C C F F(b)第14页，本讲稿共155页二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态

13、二叉树的五种基本形态 空二叉树空二叉树 仅有仅有根结根结点点 右子右子树为空树为空 左子左子树为空树为空左右子左右子树均非树均非空空 2、二叉树的基本形态、二叉树的基本形态第15页，本讲稿共155页3、应用举例、应用举例例1 可以用二叉树表示表达式 a+b*(c-d)-e/f e e d d c c b b f f a a +*/-第16页，本讲稿共155页性质1 在二叉树的第i 层上最多有2i-1个结点（用归纳法可证明）性质2 深度为k的二叉树最多有 2k-1 个结点性质3 设二叉树叶子结点数为n0，度为2的结点n2，则n0=n2+1二、二、二叉树性质二叉树性质 A A F F G G E

14、E D D C C B B第18页，本讲稿共155页两种特殊的二叉树两种特殊的二叉树v 满二叉树满二叉树：如果深度为：如果深度为k k的二叉树，有的二叉树，有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树；A A G G F F E E D D C C B B B B A A C CK=3的满二叉树K=2的满二叉树第19页，本讲稿共155页v完全二叉树完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；A A E E D D C C B B G G A A E E D D C C B B(a)a)(c)c)(b)b)

15、(a)(a)、(b)b)完全二叉树(c)c)不是完全二叉树 A A G G F F E E D D C C B B第20页，本讲稿共155页下面是两个关于完全二叉树的性质下面是两个关于完全二叉树的性质性质性质性质性质4 4 4 4：具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为：trunc(logtrunc(log2 2 n)+1.n)+1.trunc(x)trunc(x)为为取整函数取整函数。对完全二叉树的结点编号：对完全二叉树的结点编号：从上到下，每一层从左到右按顺序编号。从上到下，每一层从左到右按顺序编号。A A F F E E D D C C B B1 12 23

16、 34 45 56 6性质性质性质性质5 5 5 5：在完全二叉树中编号为在完全二叉树中编号为i i的结点的结点1 1）若有左孩子，则左孩编号为）若有左孩子，则左孩编号为2 2i i2 2）若有右孩子，则右孩子结点编号为）若有右孩子，则右孩子结点编号为2 2i+1i+13 3）若有双亲，则双亲结点编号为）若有双亲，则双亲结点编号为trunc(i/2)trunc(i/2)第21页，本讲稿共155页树与二叉树的区别树与二叉树的区别A 树的结点个数至少为树的结点个数至少为1，而二叉树的结点个数可以为而二叉树的结点个数可以为0。B树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限

17、制，二叉树结点最大度数为2。C树的结点子树无左、右之分，二叉树的结点子树有明确的左、树的结点子树无左、右之分，二叉树的结点子树有明确的左、右之分。右之分。二二叉叉树树树树第22页，本讲稿共155页三、二叉树的存储结构三、二叉树的存储结构l顺序存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中

18、的的相相对对位位置置蕴蕴含含着着结结点之间的关系。点之间的关系。第23页，本讲稿共155页l链式存储结构链式存储结构v二叉链表typedef struct node datatype data;struct node *lchild,*rchild;JD;lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域 AB C D E F G第24页，本讲稿共155页vv三叉链表三叉链表typedef struct node datatype data;struct node *lchild,*rchild,*parent;JD;lchild data pare

19、nt rchildABCDEFG A B C D E F G第25页，本讲稿共155页第一节第一节7.1.实例引入实例引入实例引入实例引入 v【学习任务学习任务学习任务学习任务】通过实例分析，了解树形结构的特通过实例分析，了解树形结构的特通过实例分析，了解树形结构的特通过实例分析，了解树形结构的特点。点。点。点。v【例例例例7.17.1】连锁店结构示意图。连锁店结构示意图。连锁店结构示意图。连锁店结构示意图。假设北京某食品连锁店，为扩大其经销范围，假设北京某食品连锁店，为扩大其经销范围，假设北京某食品连锁店，为扩大其经销范围，假设北京某食品连锁店，为扩大其经销范围，增强其销售能力和竞争实力，在

20、东北地区的哈尔增强其销售能力和竞争实力，在东北地区的哈尔增强其销售能力和竞争实力，在东北地区的哈尔增强其销售能力和竞争实力，在东北地区的哈尔滨、长春、沈阳等城市建立分店，由于经销得当滨、长春、沈阳等城市建立分店，由于经销得当滨、长春、沈阳等城市建立分店，由于经销得当滨、长春、沈阳等城市建立分店，由于经销得当，销售情况良好，在每个城市分店处又可建立了，销售情况良好，在每个城市分店处又可建立了，销售情况良好，在每个城市分店处又可建立了，销售情况良好，在每个城市分店处又可建立了若干分店，其结构图如图若干分店，其结构图如图若干分店，其结构图如图若干分店，其结构图如图7.17.1所示。所示。所示。所示。

21、第26页，本讲稿共155页第一阶段第一阶段北京总店哈尔滨分店长春分店沈阳分店分店1分店1分店m分店n分店1分店p图7.1 北京某食品连锁店结构图第27页，本讲稿共155页第二节第二节7.2 7.2 树树树树vv【学习任务学习任务学习任务学习任务】掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。vv7.2.1 7.2.1 树的定义树的定义树的定义树的定义 树（树（树（树（TreeTree）是由）是由）是由）

22、是由n n（n0n0）个结点构成的有限集合。结点数为）个结点构成的有限集合。结点数为）个结点构成的有限集合。结点数为）个结点构成的有限集合。结点数为0 0的树称为的树称为的树称为的树称为空树，结点数大于空树，结点数大于空树，结点数大于空树，结点数大于0 0的树称为非空树。的树称为非空树。的树称为非空树。的树称为非空树。结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结点的子树的分支。图点的子

23、树的分支。图点的子树的分支。图点的子树的分支。图7.2(a)7.2(a)是一棵只有是一棵只有是一棵只有是一棵只有1 1个结点的树，图个结点的树，图个结点的树，图个结点的树，图7.2(b)7.2(b)是一棵具有是一棵具有是一棵具有是一棵具有1212个结点的树个结点的树个结点的树个结点的树.第28页，本讲稿共155页第二阶段第二阶段AABCDEFIGHJKL(a)只有根结点的树(b)一般的树第29页，本讲稿共155页v叶子结点和分支结点：将度为叶子结点和分支结点：将度为叶子结点和分支结点：将度为叶子结点和分支结点：将度为0 0的结点称为叶子结的结点称为叶子结的结点称为叶子结的结点称为叶子结点，又称

24、为终端结点。将度不为点，又称为终端结点。将度不为点，又称为终端结点。将度不为点，又称为终端结点。将度不为0 0的结点称为分的结点称为分的结点称为分的结点称为分支结点，又称为非终端结点。图支结点，又称为非终端结点。图支结点，又称为非终端结点。图支结点，又称为非终端结点。图7.2(b)7.2(b)中的中的中的中的E E、F F、GG、HH、J J、KK、L L都是叶子结点。都是叶子结点。都是叶子结点。都是叶子结点。AA、BB、C C、DD、I I结点都是分支结点。结点都是分支结点。结点都是分支结点。结点都是分支结点。v孩子结点和双亲结点：某结点子树的根结点称为孩子结点和双亲结点：某结点子树的根结点

25、称为孩子结点和双亲结点：某结点子树的根结点称为孩子结点和双亲结点：某结点子树的根结点称为该结点的孩子结点。该结点称为孩子结点的双亲该结点的孩子结点。该结点称为孩子结点的双亲该结点的孩子结点。该结点称为孩子结点的双亲该结点的孩子结点。该结点称为孩子结点的双亲结点。如图结点。如图结点。如图结点。如图7.2(b)7.2(b)中的中的中的中的BB、C C、DD结点是结点是结点是结点是AA结点的结点的结点的结点的孩子结点，孩子结点，孩子结点，孩子结点，KK结点是结点是结点是结点是I I结点的孩子结点，相对应的结点的孩子结点，相对应的结点的孩子结点，相对应的结点的孩子结点，相对应的AA结点是结点是结点是结

26、点是BB、C C、DD结点的双亲结点。结点的双亲结点。结点的双亲结点。结点的双亲结点。第30页，本讲稿共155页v兄弟结点：具有同一双亲的结点互为兄弟结点。兄弟结点：具有同一双亲的结点互为兄弟结点。兄弟结点：具有同一双亲的结点互为兄弟结点。兄弟结点：具有同一双亲的结点互为兄弟结点。如图如图如图如图7.2(b)7.2(b)中的中的中的中的HH、I I、J J结点具有相同的双亲结结点具有相同的双亲结结点具有相同的双亲结结点具有相同的双亲结点点点点DD，所以称，所以称，所以称，所以称HH、I I、J J结点为兄弟结点。结点为兄弟结点。结点为兄弟结点。结点为兄弟结点。v后裔和祖先：一个结点的所有子树上

27、的任何结点后裔和祖先：一个结点的所有子树上的任何结点后裔和祖先：一个结点的所有子树上的任何结点后裔和祖先：一个结点的所有子树上的任何结点都是该结点的后裔。该结点称为这些后裔结点的都是该结点的后裔。该结点称为这些后裔结点的都是该结点的后裔。该结点称为这些后裔结点的都是该结点的后裔。该结点称为这些后裔结点的祖先。如图祖先。如图祖先。如图祖先。如图7.2(b)7.2(b)中的中的中的中的HH、I I、J J、KK、L L结点都结点都结点都结点都是结点是结点是结点是结点DD后裔，后裔，后裔，后裔，AA、DD、I I结点称为结点称为结点称为结点称为KK结点的祖先。结点的祖先。结点的祖先。结点的祖先。v结

28、点的层次：从根结点到树中某结点所经路径上结点的层次：从根结点到树中某结点所经路径上结点的层次：从根结点到树中某结点所经路径上结点的层次：从根结点到树中某结点所经路径上的边数加的边数加的边数加的边数加1 1称为该结点的层次。根结点的层次规称为该结点的层次。根结点的层次规称为该结点的层次。根结点的层次规称为该结点的层次。根结点的层次规定为定为定为定为1 1，其他结点的层次就是其双亲结点的层次，其他结点的层次就是其双亲结点的层次，其他结点的层次就是其双亲结点的层次，其他结点的层次就是其双亲结点的层次数加数加数加数加1 1。如图。如图。如图。如图7.2(b)7.2(b)中的中的中的中的HH结点层次为结

29、点层次为结点层次为结点层次为3 3。第31页，本讲稿共155页vv树的深度：树中所有结点的层次的最大值称为该树的深度。树的深度：树中所有结点的层次的最大值称为该树的深度。树的深度：树中所有结点的层次的最大值称为该树的深度。树的深度：树中所有结点的层次的最大值称为该树的深度。如图如图如图如图7.2(b)7.2(b)中的树深度为中的树深度为中的树深度为中的树深度为4 4。vv无序树：如果树中任意结点的各孩子结点的排列没有严格次序，无序树：如果树中任意结点的各孩子结点的排列没有严格次序，无序树：如果树中任意结点的各孩子结点的排列没有严格次序，无序树：如果树中任意结点的各孩子结点的排列没有严格次序，可

30、交换位置，则称该树为无序树。可交换位置，则称该树为无序树。可交换位置，则称该树为无序树。可交换位置，则称该树为无序树。vv有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可交换位置，则称该树为有序树。在有序树中，最左边的子树的根结点交换位置，则称该树为有序树。在有序树中，最左边的子树的根结点交换位置，则称该树为有序树。在有序树中，最左边的子树的根结点交换位置，则称该树为有序树。在有序树中，最左边的子树的根结

31、点称为第一个孩子，最右边的称为最后一个孩子。称为第一个孩子，最右边的称为最后一个孩子。称为第一个孩子，最右边的称为最后一个孩子。称为第一个孩子，最右边的称为最后一个孩子。vv森林：森林：森林：森林：n n（n0n0）棵树的集合称为森林。森林和树的概念相近，）棵树的集合称为森林。森林和树的概念相近，）棵树的集合称为森林。森林和树的概念相近，）棵树的集合称为森林。森林和树的概念相近，删除一棵树的根，则所有的子树形成森林；而为森林加上一个根，删除一棵树的根，则所有的子树形成森林；而为森林加上一个根，删除一棵树的根，则所有的子树形成森林；而为森林加上一个根，删除一棵树的根，则所有的子树形成森林；而为森

32、林加上一个根，则森林就变成一棵树。则森林就变成一棵树。则森林就变成一棵树。则森林就变成一棵树。第32页，本讲稿共155页7.2.2 7.2.2 树的表示方法树的表示方法树的表示方法树的表示方法v树的常用表示方法有以下四种：图形表示法、文树的常用表示方法有以下四种：图形表示法、文树的常用表示方法有以下四种：图形表示法、文树的常用表示方法有以下四种：图形表示法、文氏图表示法、广义表表示法和凹入表示法。氏图表示法、广义表表示法和凹入表示法。氏图表示法、广义表表示法和凹入表示法。氏图表示法、广义表表示法和凹入表示法。v1 1图形表示法图形表示法图形表示法图形表示法 图图图图7.27.2给出了图形表示树

33、的直观表示法，其中用给出了图形表示树的直观表示法，其中用给出了图形表示树的直观表示法，其中用给出了图形表示树的直观表示法，其中用圆圈表示结点，连线表示结点间的关系，并把树圆圈表示结点，连线表示结点间的关系，并把树圆圈表示结点，连线表示结点间的关系，并把树圆圈表示结点，连线表示结点间的关系，并把树根画在上面。图形表示法主要用于直观描述树的根画在上面。图形表示法主要用于直观描述树的根画在上面。图形表示法主要用于直观描述树的根画在上面。图形表示法主要用于直观描述树的逻辑结构。逻辑结构。逻辑结构。逻辑结构。v2 2文氏图表示法文氏图表示法文氏图表示法文氏图表示法 文氏图表示法采用集合的包含关系表示树，

34、如图文氏图表示法采用集合的包含关系表示树，如图文氏图表示法采用集合的包含关系表示树，如图文氏图表示法采用集合的包含关系表示树，如图7.37.3所示。所示。所示。所示。第33页，本讲稿共155页vv3 3广义表表示法广义表表示法广义表表示法广义表表示法 以广义表的形式表示树，利用广义表的嵌套区间表示树的结以广义表的形式表示树，利用广义表的嵌套区间表示树的结以广义表的形式表示树，利用广义表的嵌套区间表示树的结以广义表的形式表示树，利用广义表的嵌套区间表示树的结构。如图构。如图构。如图构。如图7.47.4所示。所示。所示。所示。vv4 4凹入表示法（章节目录表示法）凹入表示法（章节目录表示法）凹入表

35、示法（章节目录表示法）凹入表示法（章节目录表示法）采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。图图图图7.57.5所示为横向凹入表示。所示为横向凹入表示。所示为横向凹入表示。所示为横向凹入表示。第34页，本讲稿共155页DABCEFGIH图7.3 文氏图表示法(A(B(D)(E)(F)(C(G)(H(I)图7.4 广义表表示法ABDEFCGHI图7.5 凹入表示法第35页，本讲稿共155页7.2.3 7.2.3 树的

36、抽象数据类型树的抽象数据类型树的抽象数据类型树的抽象数据类型vv1 1数据集合数据集合数据集合数据集合 每个结点由数据元素和构造数据元素之间关系的指针组成。每个结点由数据元素和构造数据元素之间关系的指针组成。每个结点由数据元素和构造数据元素之间关系的指针组成。每个结点由数据元素和构造数据元素之间关系的指针组成。vv2 2操作集合操作集合操作集合操作集合 （1 1）ClearTree(T)ClearTree(T)：设置树：设置树：设置树：设置树T T为空为空为空为空 （2 2）Root(T)Root(T)：求树：求树：求树：求树T T的根结点。的根结点。的根结点。的根结点。（3 3）InitTr

37、ee(T)InitTree(T)：初始化树：初始化树：初始化树：初始化树T T。（4 4）CreateTree(x,R)CreateTree(x,R)：生成以：生成以：生成以：生成以x x为根结点，以森林为根结点，以森林为根结点，以森林为根结点，以森林RR为子树的为子树的为子树的为子树的 树。树。树。树。（5 5）Parent(T,x)Parent(T,x)：求树：求树：求树：求树T T中中中中x x结点的双亲结点。结点的双亲结点。结点的双亲结点。结点的双亲结点。（6 6）SetParent(x,y)SetParent(x,y)：把结点：把结点：把结点：把结点x x置为以结点置为以结点置为以结

38、点置为以结点y y为根结点的树的双亲结点。为根结点的树的双亲结点。为根结点的树的双亲结点。为根结点的树的双亲结点。（7 7）AddChild(y,i,x)AddChild(y,i,x)：把以结点：把以结点：把以结点：把以结点x x为根的树置为结点为根的树置为结点为根的树置为结点为根的树置为结点y y的第的第的第的第i i棵子树。棵子树。棵子树。棵子树。第36页，本讲稿共155页 （8 8）DeleteChild(x,i)DeleteChild(x,i)：删除结点：删除结点：删除结点：删除结点x x的第的第的第的第i i棵棵棵棵子树。子树。子树。子树。（9 9）LeftChild(x,y)Lef

39、tChild(x,y)：把结点：把结点：把结点：把结点x x置为结点置为结点置为结点置为结点y y的的的的最左孩子结点。最左孩子结点。最左孩子结点。最左孩子结点。（1010）RightSibling(x,y)RightSibling(x,y)：把结点：把结点：把结点：把结点x x置为结置为结置为结置为结点点点点y y的右兄弟结点。的右兄弟结点。的右兄弟结点。的右兄弟结点。（1111）Child(T,x,i)Child(T,x,i)：求树：求树：求树：求树T T中中中中x x结点的第结点的第结点的第结点的第i i棵棵棵棵子树。子树。子树。子树。（1212）Traverse(T)Traverse(

40、T)：遍历树：遍历树：遍历树：遍历树T T，即按某种顺，即按某种顺，即按某种顺，即按某种顺序依次访问树中的每个结点，且只访问一次。序依次访问树中的每个结点，且只访问一次。序依次访问树中的每个结点，且只访问一次。序依次访问树中的每个结点，且只访问一次。第37页，本讲稿共155页7.2.4 7.2.4 树的存储结构树的存储结构树的存储结构树的存储结构vv对于树，关心的是树在计算机中如何表示和存储。存储树时，对于树，关心的是树在计算机中如何表示和存储。存储树时，对于树，关心的是树在计算机中如何表示和存储。存储树时，对于树，关心的是树在计算机中如何表示和存储。存储树时，既要存储结点的数据元素，又要存储

41、结点之间的逻辑关系。结既要存储结点的数据元素，又要存储结点之间的逻辑关系。结既要存储结点的数据元素，又要存储结点之间的逻辑关系。结既要存储结点的数据元素，又要存储结点之间的逻辑关系。结点之间的逻辑关系有：双亲孩子关系、兄弟关系。因此，采点之间的逻辑关系有：双亲孩子关系、兄弟关系。因此，采点之间的逻辑关系有：双亲孩子关系、兄弟关系。因此，采点之间的逻辑关系有：双亲孩子关系、兄弟关系。因此，采用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表用树的存储结构主要有双亲表示法、孩子表示法、双

42、亲孩子表示法和孩子兄弟表示法。示法和孩子兄弟表示法。示法和孩子兄弟表示法。示法和孩子兄弟表示法。vv表示结点之间的逻辑关系主要采用指针或仿真指针。表示结点之间的逻辑关系主要采用指针或仿真指针。表示结点之间的逻辑关系主要采用指针或仿真指针。表示结点之间的逻辑关系主要采用指针或仿真指针。vv1 1双亲表示法双亲表示法双亲表示法双亲表示法 使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包含两个域：数据域和指针域。含两个域：数据

43、域和指针域。含两个域：数据域和指针域。含两个域：数据域和指针域。第38页，本讲稿共155页 图图图图7.6(a)7.6(a)是对图是对图是对图是对图7.2(b)7.2(b)采用常规指针表示的存储结构，图采用常规指针表示的存储结构，图采用常规指针表示的存储结构，图采用常规指针表示的存储结构，图7.6(b)7.6(b)是对图是对图是对图是对图7.2(b)7.2(b)采用仿真指针表示的存储结构。采用仿真指针表示的存储结构。采用仿真指针表示的存储结构。采用仿真指针表示的存储结构。第39页，本讲稿共155页v2 2孩子表示法孩子表示法孩子表示法孩子表示法 使用指针表示出每个结点的孩子结点，即孩子表使用指

44、针表示出每个结点的孩子结点，即孩子表使用指针表示出每个结点的孩子结点，即孩子表使用指针表示出每个结点的孩子结点，即孩子表示法。由于每个结点的孩子结点个数不同，为了示法。由于每个结点的孩子结点个数不同，为了示法。由于每个结点的孩子结点个数不同，为了示法。由于每个结点的孩子结点个数不同，为了简便起见，孩子表示法中的每个结点的指针域个简便起见，孩子表示法中的每个结点的指针域个简便起见，孩子表示法中的每个结点的指针域个简便起见，孩子表示法中的每个结点的指针域个数是树的度。数是树的度。数是树的度。数是树的度。图图图图7.77.7是对图是对图是对图是对图7.2(b)7.2(b)采用常规指针表示的存储结采用

45、常规指针表示的存储结采用常规指针表示的存储结采用常规指针表示的存储结构。构。构。构。第40页，本讲稿共155页v孩子表示法与双亲表示法的特点相反。孩子表示孩子表示法与双亲表示法的特点相反。孩子表示孩子表示法与双亲表示法的特点相反。孩子表示孩子表示法与双亲表示法的特点相反。孩子表示法可方便的找到一个结点的孩子及其后裔，并能法可方便的找到一个结点的孩子及其后裔，并能法可方便的找到一个结点的孩子及其后裔，并能法可方便的找到一个结点的孩子及其后裔，并能方便的实现树的遍历。方便的实现树的遍历。方便的实现树的遍历。方便的实现树的遍历。第41页，本讲稿共155页v3 3双亲孩子表示法双亲孩子表示法双亲孩子表

46、示法双亲孩子表示法 采用双亲表示法和孩子表示法的优势，使用指针采用双亲表示法和孩子表示法的优势，使用指针采用双亲表示法和孩子表示法的优势，使用指针采用双亲表示法和孩子表示法的优势，使用指针既表示出每个结点的双亲结点，又表示出每个结既表示出每个结点的双亲结点，又表示出每个结既表示出每个结点的双亲结点，又表示出每个结既表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域既点的孩子结点，就是双亲孩子表示法。指针域既点的孩子结点，就是双亲孩子表示法。指针域既点的孩子结点，就是双亲孩子表示法。指针域既包括指向孩子的指针，也包括指向双亲结点的指包括指向孩子的指针，也包括指向双亲

47、结点的指包括指向孩子的指针，也包括指向双亲结点的指包括指向孩子的指针，也包括指向双亲结点的指针。图针。图针。图针。图7.87.8是对图是对图是对图是对图7.2(b)7.2(b)采用常规指针表示的存采用常规指针表示的存采用常规指针表示的存采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示双亲储结构，其中实线表示孩子指针，虚线表示双亲储结构，其中实线表示孩子指针，虚线表示双亲储结构，其中实线表示孩子指针，虚线表示双亲指针。指针。指针。指针。第42页，本讲稿共155页第43页，本讲稿共155页v4 4孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法 采用指针既指向每个结点的孩子结点，

48、又指向每采用指针既指向每个结点的孩子结点，又指向每采用指针既指向每个结点的孩子结点，又指向每采用指针既指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法。指针个结点的兄弟结点，就是孩子兄弟表示法。指针个结点的兄弟结点，就是孩子兄弟表示法。指针个结点的兄弟结点，就是孩子兄弟表示法。指针域包含两个指针，指向孩子结点的指针和指向兄域包含两个指针，指向孩子结点的指针和指向兄域包含两个指针，指向孩子结点的指针和指向兄域包含两个指针，指向孩子结点的指针和指向兄弟结点的指针。弟结点的指针。弟结点的指针。弟结点的指针。图图图图7.97.9是对图是对图是对图是对图7.2(b)7.2(b)采用常

49、规指针表示的存储结采用常规指针表示的存储结采用常规指针表示的存储结采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示兄弟指针。构，其中实线表示孩子指针，虚线表示兄弟指针。构，其中实线表示孩子指针，虚线表示兄弟指针。构，其中实线表示孩子指针，虚线表示兄弟指针。第44页，本讲稿共155页第45页，本讲稿共155页第三节第三节v7.3 7.3 二叉树二叉树v二叉树是一种重要的数据结构类型，其特点在于二叉树是一种重要的数据结构类型，其特点在于任一结点最多有两个子树分支，二叉树的度为任一结点最多有两个子树分支，二叉树的度为2 2。在二叉树中，左右子树是严格区分的，子树的顺在二叉树中，左右子树是严

50、格区分的，子树的顺序不能随意颠倒。序不能随意颠倒。v【学习任务】掌握二叉树的相关概念和性质，理【学习任务】掌握二叉树的相关概念和性质，理解二叉树的存储结构，注意把握树和二叉树的异解二叉树的存储结构，注意把握树和二叉树的异同。同。返回返回第46页，本讲稿共155页vv7.3.1 7.3.1 二叉树的定义二叉树的定义二叉树的定义二叉树的定义vv定义：二叉树是由定义：二叉树是由定义：二叉树是由定义：二叉树是由n n（n0n0）个结点组成的有限集合、每个结点）个结点组成的有限集合、每个结点）个结点组成的有限集合、每个结点）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个