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

国家级精品课程—《数据结构与算法》 第6章树 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:王腾蛟 版权所有,转载或翻印必究

国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：王腾蛟 ©版权所有，转载或翻印必究 第6章 树

主要内容 61树的定义和基本术语 62树的链式存储结构 6.3树的顺序存储结构 64K叉树 65树知识点总结 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 6.1 树的定义和基本术语 ◼ 6.2 树的链式存储结构 ◼ 6.3 树的顺序存储结构 ◼ 6.4 K叉树 ◼ 6.5 树知识点总结

6.1树的定义和基本术语 611树和森林 612森林与二叉树的等价转换 613树的抽象数据类型 614树的周游 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 6.1.1 树和森林 ◼ 6.1.2 森林与二叉树的等价转换 ◼ 6.1.3 树的抽象数据类型 ◼ 6.1.4 树的周游 6.1 树的定义和基本术语

611树和森林 树(tre是包括n个结点的有限集合 T(n≥1),使得: 口有且仅有一个特定的称为根(ot)的结点。 口除根以外的其它结点被分成m个(m≥0)不 相交的有限集合T1,T2,…,Tm,而每一 个集合又都是树。其中树T,T2,…,Tm 称作这个根的子树( subtree “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 ◼ 树(tree)是包括n个结点的有限集合 T（n ≥ 1），使得： ❑ 有且仅有一个特定的称为根(root)的结点。 ❑ 除根以外的其它结点被分成m个(m ≥ 0)不 相交的有限集合T1，T2，…，Tm，而每一 个集合又都是树。其中树T1，T2，…，Tm 称作这个根的子树(subtree)

611树和森林 B 图61树形表示法 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 图6.1 树形表示法 A B C D E F G H I J K L

611树和森林 树的逻辑结构可以这样描述:树是包含n个结点的有 穷集合K(n>0),且在K上定义了一个满足以下条件 的二元关系R={r}: 口有且仅有一个结点k∈K,它对于关系r来说没 有前驱。结点k称作树的根。 口除结点k外,K中的每个结点对于关系r来说都有 且仅有一个前驱。 口除结点k外的任何结点k∈K,都存在一个结点 序列k,k1,…,k,使得k就是树根,且k=k ,其中有序对∈R(1≤i≤s)。这样 的结点序列称为从根k到结点k的一条路径。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6.1.1 树和森林 ◼ 树的逻辑结构可以这样描述：树是包含n个结点的有 穷集合K(n > 0)，且在K上定义了一个满足以下条件 的二元关系R = {r}： ❑ 有且仅有一个结点k0∈ K，它对于关系r来说没 有前驱。结点k0称作树的根。 ❑ 除结点k0外，K中的每个结点对于关系r来说都有 且仅有一个前驱。 ❑ 除结点k0外的任何结点k ∈ K，都存在一个结点 序列k0，k1，…，ks，使得k0就是树根，且ks = k ，其中有序对 ∈ R（1 ≤ i ≤ s）。这样 的结点序列称为从根k0到结点k的一条路径

树形结构的各种表示法 树的逻辑结构是 结点集合K={A,B,C,D,E,F,G,H,I,乃 K上的关系N={,,, ,,, ,,<E,J “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树形结构的各种表示法 树的逻辑结构是： 结点集合K={A，B，C，D，E，F，G，H，I，J} K上的关系N={，，， ，，， ，，}

树结构中的概念 在一棵树中,若存在结点k指向结点k的连线,则 称k是k的父结点,而k则是k的子结点,有向连 线称作边 同一个父结点的子结点之间互称兄弟。树中没有 父结点的结点称为根。没有子结点的结点称为树 叶 ■结点的子树数目称为结点的度,树的度是树中各 结点度的最大值,二叉树的度是2。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 在一棵树中，若存在结点k指向结点k’的连线，则 称k是k’的父结点，而k’则是k的子结点，有向连 线称作边。 ◼ 同一个父结点的子结点之间互称兄弟。树中没有 父结点的结点称为根。没有子结点的结点称为树 叶。 ◼ 结点的子树数目称为结点的度，树的度是树中各 结点度的最大值，二叉树的度是2

树结构中的概念 若树中存在结点序列k,k1,…,k,使得,,…,都是树中的边 则称从结点k到结点k存在一条路径 若有一条由k到达ks的路径,则称k是ks的祖先, ks是k的子孙。 结点的层数同样由树根开始定义的,根结点为第 0层,非根结点的层数是其父结点的层数加1。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 若树中存在结点序列k0，k1，…，ks，使得，，…，都是树中的边， 则称从结点k0到结点ks存在一条路径。 ◼ 若有一条由 k到达ks的路径，则称k是ks的祖先， ks是k的子孙。 ◼ 结点的层数同样由树根开始定义的，根结点为第 0层，非根结点的层数是其父结点的层数加1

树结构中的概念 有序树:计算机的存储是有序的,为方便计算机处理 ,往往把子结点按从左到右的次序顺序编号,即把树 作为有序树( ordered tree看待。 度为2的有序树并不是二叉树,因为在第一子结点被删 除后,第二子结点自然顶替成为第一子结点。因此, 度为2并且严格区分左右两个子结点的有序树才是二叉 树 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树结构中的概念 ◼ 有序树：计算机的存储是有序的，为方便计算机处理 ，往往把子结点按从左到右的次序顺序编号，即把树 作为有序树(ordered tree)看待。 ◼ 度为2的有序树并不是二叉树，因为在第一子结点被删 除后，第二子结点自然顶替成为第一子结点。因此， 度为2并且严格区分左右两个子结点的有序树才是二叉 树