第六章树和二叉树1.ppt

几种特殊形式的二叉树 满二叉树 定义： 6.2.2　二叉树的性质 (3+2) 求二叉树的深度 void BiTreeDepth(BiTree T, int level, int depth) {// T指向二叉树的根，level 为 T 所指结点所在层次，其初值为1，depth 为当前求得的最大层次,其初值为0　　if(T){　　　if(leveldepth) depth=level; 　　　BiTreeDepth(T-Lchild, level+1, depth);　　　BiTreeDepth(T-Rchild, level+1, depth);　　}　} 在二叉树上查询某个结点 void locate(BiTree T,ElemType x,BiTree p){　// 若二叉树 T 中存在和 x 相同的元素，则 p 指向该结点，否则 p 的值不变，p 的初值为 NULL　if (T)　{ if (T-data==x) p=T;　　locate(T-lchild, x, p);　　locate(T-rchild, x, p);　}} 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。 可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝?（n＋1）/2 ?，就可根据完全二叉树的结点总数计算出叶子结点数。 * 6.2.1　二叉树的定义 定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。 问：具有3个结点的二叉树可能有几种不同形态？ 有5种 基本形态： * 二叉树的抽象数据类型定义（见教材P121-122） ADT BinaryTree{ 数据对象D: 数据关系R: 基本操作 P： }ADT BinaryTree D是具有相同特性的数据元素的集合。 若D=Φ，则R= Φ ； 若D≠Φ，则R= {H}；存在二元关系： ① root 唯一 //关于根的说明 ② Dj∩Dk= Φ //关于子树不相交的说明 ③ …… //关于数据元素的说明 ④ …… //关于左子树和右子树的说明 //至少有20个，如返回某结点的左孩子，或中序遍历，等等 特点：每一层上的结点数都是最大结点数 完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L 或L+1 A B C K D E H I L F G J 1 2 3 4 5 6 7 8 9 10 11 12 A B C K D E H I L M F G J N O 1 2 3 4 5 6 7 8 9 10 11 13 14 15 A B C D E J K 1 2 3 4 5 6 7 A B C D E G 1 2 3 4 5 6 * 讨论1：第i层的结点数最多是多少？ （利用二进制性质可轻松求出） 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k0）。 再提问：第i层上至少有 个结点？ 1 讨论2：深度为k的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出） 2i-1个 2k-1个 * 6.2.2　二叉树的性质 (3+2) 性质1: 在二叉树的第i层上至多有2i-1个结点（i0） 性质2: 深度为k的二叉树至多有2k-1个结点（k0） 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 性质4: 具有n个结点的完全二叉树的深度必为?log2n?＋1 性质5: 对完全二叉树，