数据结构-使用C语言 朱战立 第7章树和二叉树1.ppt

4、具有10个叶结点的二叉树中有（ ）个度为2的结点。 A．8 B．9 C．10 D．11 5、一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 * * * * * 第7章 树和二叉树（Tree Binary Tree） 7.1 树 7.2 二叉树 7.3 二叉树的设计与实现 7.4 遍历二叉树和线索二叉树 7.5 赫夫曼树及其应用 7.6 树与二叉树的转换 特点：非线性结构，一个直接前驱，但可能有多个直接后继。 （一对多或1:n） * 数据结构 * 数据结构课程的内容 * 7.1 树7.1.1 树的定义 注1：树的定义具有递归性，即“树中还有树”。 树是由n(n≥0)个结点组成的有限集合T。 n=0的树称为空树； 对n0的树，有: (1)仅有一个特殊的结点称为根结点，根结点没有前驱结点； (2)当n1时，除根结点外其余的结点分为m(m0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。 过去许多书籍中都定义树为n≥1， 曾经有“空树不是树”的说法， 但现在树的定义已修改。 * 7.1.2 树的表示方法 ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点 A B C G E I D H F J F L K 根 叶子结点 森林 有序树 无序树 ——即根结点(没有前驱) ——即终端结点(没有后继) ——指m棵不相交的树的集合(例如删除A后的子树个数) 双亲结点 孩子结点 兄弟结点 祖先结点 子孙结点 ——结点各子树从左至右有序，不能互换（左为第一） ——结点各子树可互换位置。 图7.1 * ——即树的数据元素 ——结点挂接的子树数 结点 结点的度 结点的层次 终端结点 分支结点 树的度 树的深度 (或高度) A B C G E I D H F J F L K ——从根到该结点的层数（根结点算第0层） ——即度为0的结点，即叶子 ——即度不为0的结点（也称为内部结点） ——所有结点度中的最大值（Max{各结点的度}） ——指所有结点中最大的层数（Max{各结点的层次}） 问：右上图中的结点数＝ ；树的度＝ ；树的深度＝ 13 3 3 （有几个直接后继就是几度，亦称“次数”） * 数据结构 * 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。 特点： 树的5种表示法： 图形表示法 嵌套集合表示法 广义表表示法 凹入表示法 左孩子－右兄弟表示法 * 数据结构 * 图形表示法 教师 学生 其他人员 2010级 2011级 2012级 2013级 …… 江西农业大学 电气系 软件学院 外语系 …… 叶子 根 子树 * 数据结构 * 嵌套集合表示法 * 数据结构 * ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 约定： 根作为由子树森林组成的表的名字，写在表的左边 广义表表示法 * 数据结构 * 凹入表示法 又称目录表示法 * 7.1.3 树的抽象数据类型 数据集合: 树的结点集合，每个结点由数据元素和构造数　　　　　据元素之间关系的指针组成。 操作集合: (1)创建树　MakeTree(T) 　 (2)撤消树　DestroyTree(T) (3)查找树中当前结点的双亲结点　Parent(T,curr) (4)查找树中当前结点的左孩子结点　LeftChild(T,curr) (5)查找树中当前结点的右兄弟结点　RightSibling(T,curr) (6)遍历树　　Traverse(T,Visit( )) * 7.1.4　树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 * A B C G E D H F 1、双亲表示法 (a)一棵树