北京大学：《数据结构与算法》课程教学资源（实验班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 主要内容 „ 5.1 树的概念 „ 5.2 树的链式存储 „ 5.3 树的顺序存储 „ 5.4 K叉树 „ 补充 树计数

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

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

511树和森林 A 令树的逻辑结构 令树形结构的各种B C 表示法 命树的定义和概念0 BOOF OOH 令森林的定义 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 5.1.1 树和森林 „ 树的逻辑结构 „ 树形结构的各种 表示法 „ 树的定义和概念 „ 森林的定义 I J F E G A B C D H

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

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 树的逻辑结构 „ 包含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的 一条路径

树形结构的各种表示法 令树形表示法 令形式语言表示法 令文氏图表示法 凹入表表示法 令嵌套括号表示法 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 Page 6

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 树形结构的各种表示法 „ 树形表示法 „ 形式语言表示法 „ 文氏图表示法 „ 凹入表表示法 „ 嵌套括号表示法

树形表示法 Q C BO D○○○ F GO OH (a)树形表示法 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 树形表示法 I J F E G A B C D H （a）树形表示法

形式语言表示法 树的逻辑结构是: 结点集合K={A,B,C,D,E,F,G,H,I,]} K上的关系N={,,, ,,} 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 age 8

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

文氏图表示法 B C E (b)文氏图表示法 北京大学信息学院 张铭编写 @版权所有,转载或翻印必究 age 9

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 文氏图表示法 A B C D I J F E G H （b）文氏图表示法

凹入表表示法 A B D E F H (c)凹入表表示法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 凹入表表示法 B A D E I J F G H C （c）凹入表表示法