彩色PDF讲义(5)

《彩色PDF讲义(5)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第五章树任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究主要内容¢5.1树的概念¢5.2树的链式存储¢5.3树的顺序存储¢5.4K叉树¢补充树计数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25.1树的概念¢5.1.1树和森林¢5.1.2森林与二叉树的等价转换¢5.1.3树的抽象数据类型¢5.1.4树的周游北京大学信息学院张铭编写©版权所有，转载或

2、翻印必究Page35.1.1树和森林A¢树的逻辑结构C¢树形结构的各种B表示法EGH¢树的定义和概念DF¢森林的定义IJ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4树的逻辑结构¢包含n个结点的有穷集合K(n>0)，且在K上定义了一个关系N，关系N满足以下条件：¢有且仅有一个结点k0∈K，它对于关系N来说没有前驱。结点k称作树的根0¢除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱¢除结点k0外的任何结点k∈K，都存在一个结点序列k0，k，…，k，使得k就是树根，且k=k，其中有序对

3、1s0si-，k>∈N(1≤i≤s)。这样的结点序列称为从根到结点k的1i一条路径北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5树形结构的各种表示法¢树形表示法¢形式语言表示法¢文氏图表示法¢凹入表表示法¢嵌套括号表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6树形表示法ACBEGHDFIJ（a）树形表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7形式语言表示法树的逻辑结构是：结点集合K={A，B，C，D，E，F，G，H，I，J}K上的关系N={，

4、C>，，，，，，，}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8文氏图表示法ABCEDIJFGH（b）文氏图表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9凹入表表示法ABDEIJFCGH（c）凹入表表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page105树5.1树的概念5.1.1树和森林5.1.2森林与二叉树的等价转换凹入表表示法(例子)5.1.3树的抽象数据类型5.1.4树的周游5.2树的链式

5、存储5.2.1子结点表表示法5.2.2左子结点/右兄弟结点表示法5.2.3动态结点表示法5.2.4动态“左子结点/右兄弟结点”二叉链表表示法5.2.5父指针表示法及等价类的并查算法5.3树的顺序存储5.3.1带右链的先根次序表示法5.3.2带双标记位的先根次序表示法5.3.3带左链的层次次序表示法5.3.4带度数的后根次序表示法5.4K叉树¢图书目录，杜威表示法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11嵌套括号表示法(A(B(D)(E(I)(J))(F))(C(G)(H)))（d）嵌套括号表示

6、法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12文氏图到嵌套括号表示的转化从最外层依次将表示集合的方框转化成括号对ABCEDIJFGH(A(B(D)(E(I)(J))((F))C(G)(H)))北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13树的定义¢树是包括n个结点的有限集合T（n≥1），使得：¢有一个特别标出的称作根的结点¢除根以外的其它结点被分成m个(m≥0)不相交的集合T1，T，…，T，而且这些集合的每一个又都是树。树T，2m1T，…，T称作这个根的子树2m¢这个定义是递归的

7、，我们用子树来定义树：只包含一个结点的树必然仅由根组成，包含n>1个结点的树借助于少于n个结点的树来定义北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14树结构中的概念(1)¢若∈N，则称k是k′的父结点（或称“父母”），而k′则是k的子结点(或“儿子”、“子女”)¢若有序对及∈N，则称k′和k″互为兄弟¢若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙¢树形结构中，两个结点的有序对，称作连接这两结点的一条边北京大学信息学院张铭编写©版权所有，转载或翻

8、印必究Page15树结构中的概念(2)¢没有子树的结点称作树叶或终端结点¢非终端结点称为分支结点¢一个结点的子树的个数称为度数¢根结点的层数为0，其它任何结点的层数等于它的父结点的层数加1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16树结构中的概念(3)¢有序树在树T中如果子树T1，T2，…，T的相对次序是重要的，则称树T为有向m有序树，简称有序树。¢在有