第五章树 任课教员:张铭 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,其中有序对 <k;1,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，其中有序对 <ki-1，ki>∈N(1≤i≤s)。这样的结点序列称为从根到 结点k的一条路径
树形结构的各种表示法 树的逻辑结构是: 结点集合K={A,B,C,D,E,F,G,H,I,} K上的关系N={<A,B>,<A,C>,<B,D>, <B,E> <B,F>,<C,G> <C,H>,<E,I>,<E,]>} 北京大学信息学院 版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 树形结构的各种表示法 树的逻辑结构是： 结点集合K={A，B，C，D，E，F，G，H，I，J} K上的关系N={<A，B>，<A，C>，<B，D>， <B，E>，<B，F>，<C，G>， <C，H>，<E，I>，<E，J>}