北京大学：《数据结构与算法》课程教学资源（实验班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,其中有序对<k 1k>∈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，其中有序对<ki- 1，ki>∈N(1≤i≤s)。这样的结点序列称为从根到结点k的 一条路径