北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）树与森林

第五章树 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究

第五章 树 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

主要内容 51树的概念 52树的链式存储 53树的顺序存储 54K叉树 北京大学信息学院 版权所有,转载或翻印必究 Page 2

北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 5.1 树的概念 ◼ 5.2 树的链式存储 ◼ 5.3 树的顺序存储 ◼ 5.4 K叉树

51树的概念 511树和森林 512森林与二叉树的等价转换 513树的抽象数据类型 514树的周游 北京大学信息学院 版权所有,转载或翻印必究 Page 3

北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 5.1 树的概念 ◼ 5.1.1 树和森林 ◼ 5.1.2 森林与二叉树的等价转换 ◼ 5.1.3 树的抽象数据类型 ◼ 5.1.4 树的周游

树的逻辑结构 包含n个结点的有穷集合K(n>0),且在K上定义 了一个关系N,关系N满足以下条件: 有且仅有一个结点k∈K,它对于关系N来说没有前驱 结点k称作树的根 除结点k外,K中的每个结点对于关系N来说都有且仅有 个前驱 除结点k外的任何结点k∈K,都存在一个结点序列k0, k1,…,k,使得k0就是树根,且k=k,其中有序对 ∈N(1≤i≤s)。这样的结点序列称为从根到 结点k的一条路径 北京大学信息学院 版权所有,转载或翻印必究 Page 4

北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 树的逻辑结构 ◼ 包含n个结点的有穷集合K (n>0)，且在K上定义 了一个关系N，关系N满足以下条件： ◼ 有且仅有一个结点k0∈K，它对于关系N来说没有前驱。 结点k0称作树的根 ◼ 除结点k0外，K中的每个结点对于关系N来说都有且仅有 一个前驱 ◼ 除结点k0外的任何结点k∈K，都存在一个结点序列k0， k1，…，ks，使得k0就是树根，且ks=k，其中有序对 ∈N(1≤i≤s)。这样的结点序列称为从根到 结点k的一条路径

树形结构的各种表示法 树的逻辑结构是: 结点集合K={A,B,C,D,E,F,G,H,I,} K上的关系N={,,, , ,,} 北京大学信息学院 版权所有,转载或翻印必究 Page 5

北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 树形结构的各种表示法 树的逻辑结构是： 结点集合K={A，B，C，D，E，F，G，H，I，J} K上的关系N={，，， ，，， ，，}

树形结构的各种表示法 C B D○○○Fc○○m (a)树形表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 6

北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 树形结构的各种表示法 （a）树形表示法

树形结构的各种表示法 A B E (b)文氏图表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 7

北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 树形结构的各种表示法 （b）文氏图表示法

树形结构的各种表示法 A B D E FGH (c)凹入表表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 8

北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 树形结构的各种表示法 （c）凹入表表示法

树形结构的各种表示法 (A(BOCEOOFDCCOGODI (d)嵌套括号表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 9

北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 树形结构的各种表示法 (A(B(D)(E(I)(J)(F))(C(G)(H))) （d）嵌套括号表示法

树的定义 ■树是包括n个结点的有限集合T(n≥1),使得 有一个特别标出的称作根的结点 除根以外的其它结点被分成m个(m≥0)不相交的集合T1, 2 而且这些集合的每一个又都是树。树T T2,…,Tm称作这个根的子树 ■这个定义是递归的,我们用子树来定义树:只包 含一个结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北京大学信息学院 版权所有,转载或翻印必究 Page 10

北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 树的定义 ◼ 树是包括n个结点的有限集合T（n≥1），使得： ◼ 有一个特别标出的称作根的结点 ◼ 除根以外的其它结点被分成m个(m≥0)不相交的集合T1， T2，…，Tm，而且这些集合的每一个又都是树。 树T1， T2，…，Tm称作这个根的子树 ◼ 这个定义是递归的，我们用子树来定义树：只包 含一个结点的树必然仅由根组成，包含n>1个结 点的树借助于少于n个结点的树来定义