第四章树和二叉树解读.pptx

第4章 树和二叉树 内容提要 2 F 4.1 树的定义和基本术语 F 4.2 二叉树 F 4.3 遍历二叉树和线索二叉树 F 4.5 树和森林 F 4.6 赫夫曼树及其应用 特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n） 4.1 树的定义和基本术语 3 1.树的定义 注：树的定义具有递归性，即树中还有树。 由一个或多个（n≥ 0）结点组成的有限集合。在任何一棵非空树T中： （1）有且仅有一个结点称为根（root）； （2）当n1时，其余的结点分为m（m≥ 0）个 互不相交的有限集合T1、T2…Tm。每个 集合本身又是棵树，被称作这个根的子树。 4.1 树的定义和基本术语 4 A 只有根结点的树 根 子树 4.1 树的定义和基本术语 5 树的抽象数据类型定义 D是具有相同特性的数据元素的集合。 ADT Tree { }Tree 数据对象D: 数据操作P: 数据关系R: //至少15个 4.1 树的定义和基本术语 6 图形表示法 嵌套集合表示法 广义表表示法 凹入表示法（目录表示法） 树的表示方法 4.1 树的定义和基本术语 7 ①图形表示法： 4.1 树的定义和基本术语 8 ②广义表表示法： 根作为由子树森林组成的表的名字写在表的左边 A（B，C，D） A（B，C（E,F,G,H），D） ③凹入表示法： 4.1 树的定义和基本术语 9 ④嵌套表示法： B D E G F H 4.1 树的定义和基本术语 10 2.若干术语 根----根结点（没有前驱） 森林----指m棵不相交的树的集合 有序树----结点各子树从左至右有序，不能互换（左为第一） 无序树----结点各子树可互换位置 双亲----上层的那个结点（直接前驱） 孩子----下层结点的子树的根（直接后继） 兄弟----同一双亲下的同一层结点（孩子之间互称兄弟） 堂兄弟----双亲位于同一层的结点（但并非同一双亲） 祖先----从根到该结点所经分支的所有结点 子孙----该结点下层子树的任一结点 例如 A 只有根结点的树 有13个结点的树 其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树 树的基本术语 1层 2层 4层 3层 height = 4 A C G B D E F K L H M I J 结点 结点的度 叶结点 分支结点 子女 双亲 兄弟 祖先 子孙 结点层次 树的深度 树的度 森林 4.1 树的定义和基本术语 13 结点----树中的数据元素 结点的度----结点拥有的子树的数目（有几个直接后继度就是几） 结点的层次----从根到该结点的层数（根结点算第一层） 叶子----度为0的点（终端结点） 分支结点----度不为0的点（非终端结点） 树的度----所有结点度中的最大值（Max{各结点的度}） 树的深度----所有结点中最大的层数（ Max{各结点的层次} ） （或高度） 4.2 二叉树 14 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 4.2 二叉树---定义 15 1、二叉树的定义 ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒（有序树）。 基本特征： 基本形态： 具有3个结点的二叉树可能有几种不同形态？普通树呢？ 4.2 二叉树---性质 16 2、二叉树的性质 性质1：在二叉树的第i层上至多有2i-1个结点（i0）。 问：第i层上至少有 个结点？ 性质2：深度为k的二叉树至多有2k-1个结点（k0）。 性质3：对于任何一棵二叉树，若度2的结点数有n2个， 叶子结点数为n0，则n0=n2+1。 4.2 二叉树---性质 17 证明性质3： ∵二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数) 又∵ 二叉树中全部结点数n=B+1(总分支数 + 根结点) （除根结点外，每个结点必有一个直接前驱，即一个分支） 而 总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继) 三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+1 4.2 二叉树---特例 18 满二叉树：深度为k且有 2k-1个结点的二叉树。 特点：每一层上的结点数都是最大结点数。