数据结构-树、二叉树及性质.pptVIP

基本操作—查找类 PreOrderTraverse(T, Visit()) InOrderTraverse(T, Visit()) PostOrderTraverse(T, Visit()) LevelOrderTraverse(T, Visit()) 基本操作—插入类 InitBiTree(T) Assign(T, e, value) CreateBiTree(T, definition) InsertChild(T, p, LR, c) 基本操作—删除类 ClearBiTree(T) DestroyBiTree(T) DeleteChild(T, p, LR) 二叉树的重要特性 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。(i≥1) 二叉树具有以下五条重要性质： 二叉树的重要特性 A C G B D E F K L H J I M N O 1 2 3 4 层号 二叉树的重要特性 用归纳法证明： 归纳基础： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点， 2i-1 = 20 = 1； 假设第i-1层上至多有2i-2个结点; 二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 × 2 = 2i-1 。 二叉树的重要特性 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1） 二叉树的重要特性 证明： ≤ 20+21+ ? ? ? ? ? ? +2k-1 = 2k-1 第1层: ≤20 第2层: ≤21 …… 第i层: ≤2i-1 二叉树的重要特性 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 式1 二叉树的重要特性 1 2 3 4 5 6 7 8 9 10 设二叉树上分支总数(边数)为b ，由树的性质： n =b+1， 二叉树的重要特性 又因为度为1的点引出一条边 度为2的点引出2条边 所以：b=n1 + 2n2 1 2 3 4 5 6 7 8 9 10 所以：n=n1 + 2n2 + 1 式2 由式1和2得到： n0 + n1 + n2= n1 + 2n2+1 整理后 n0 = n2 + 1 二叉树的重要特性 * 二叉树的类型定义 树的类型定义 小结和作业 树（Tree)和二叉树（Binary Tree） 基本操作 树的抽象数据类型定义 树的表示方法 树的基本术语 树型结构和线性结构结构特点的对比 树的类型定义 二叉树的五种基本形态 二叉树的定义 主要基本操作 二叉树的重要特性 二叉树的类型定义 树的抽象数据类型定义 树的示例： A A C G B D E F K L H M I J 只有根结点的树 有13个结点的树 树的抽象数据类型定义 A C G B D E F K L H M I J A是根； 其余结点分成三个互不相交的子集，T1={B,E,F,K,L}； T2={C,G}；T3={D,H,I,J,M}； T1,T2,T3都是根A的子树，且本身也是一棵树。 树的抽象数据类型定义 数据对象 D ： D是具有相同特性的数据元素的集合。 树的抽象数据类型定义 数据关系： 若|D|=0，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, …, Tm,其中Ti本身是一棵符合本定义的树，称为根root的子树。 树的基本操作 2）插入类 1）查找类 3）删除类 树的基本操作--查找类 Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) //求当前结点的双 亲结点 LeftChild(T, cur_e)// 求当前结点的 最左孩子 树的基本操作--查找类 RightSibling(T, cur_e) // 求当前结点 的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历 树的基本操作—插入类 InitTree(T) // 初始化置空树 CreateTree(T, definition) // 按定义构造树 Assign(T, cur_e, v