《第五章二叉树及应用讲课教案》由会员分享，可在线阅读，更多相关《第五章二叉树及应用讲课教案（82页珍藏版）》请在金锄头文库上搜索。
1、第五章 二叉树及应用,一种重要的非线性结构,学习要点：,二叉树的递归概念，这与二叉树各种基本运算具有密切关联。 满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。 二叉树的顺序存储与二叉链表存储结构。 二叉树遍历的基本思想和基于递归与非递归实现算法。 线索二叉树概念，二叉树的线索化和遍历。 Huffman树概念与基本算法；Huffman编码和实现算法。,2,5.1 二叉树及其基本性质,5.1.1 二叉树基本概念 “二叉树”是一个满足下述条件的由结点组成的有限集合E： 当E为空集时，定义其为空二叉树； 当E非空时，分为两种情形。 如果E为单元素集合，定义其为一棵根二叉树； 如果E为多于一个结
2、点的集合，则E中应当具有唯一一个结点r称其为根结点，而集合E=E r也是一棵二叉树，称为r的子二叉树。此时，结点r至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为r的左子树和右子树。,3,其它一些相关概念：,结点的度：结点拥有的子树棵数 结点的深度（层次）：根结点看做第0层，其余结点的层次值为其父结点所在层值加1 树的度：树中所有结点度的最大值 树的深度：树中最大层次数,4,根结点、叶结点、内部结点,子结点、父结点、兄弟结点、堂兄弟结点、 子孙结点、祖先结点；,5.1.2 满二叉树和完全二叉树,1、满二叉树 如果一棵二叉树满足下述条件，就称其为满二叉树（full binar
3、y tree）： 每个结点或是度数为2（具有两个非空子树）的结点，或是度数为0的（叶）结点； 所有叶结点都在同一层。,6,5.1.2 满二叉树和完全二叉树2,2、完全二叉树 若一棵二叉树满足下述条件，就称其为完全二叉树（complete binary tree）： 至多只有最下两层中结点的度数小于2； 最下一层的叶结点都依次排列在该层最左边位置。,7,5.1.2 满二叉树和完全二叉树2,2、完全二叉树2 重点理解： 满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。 空二叉树和根二叉树既是满二叉树，也是完全二叉树。 完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若干个结点后得到
4、二叉树。 完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。,8,练习：,1、完全二叉树某结点若无右子树则定无左子树。 2、完全二叉树某结点若无左子树则定无右子树。,9,5.1.3 二叉树基本性质,性质5-1 一棵二叉树第i（i0）层上至多只能有 个结点。,10,2i,证明：应用数学归纳法。 二叉树第0层有一个结点，即当i=0时，2i=20=1成立。 假设结论对第i层成立，即第i层至多只能有2i个结点。注意到二叉树每个结点的度最多为2，第i+1层结点个数至多只能是第i层结点个数的2倍，即2*2i = 2i+1，归纳完成，命题得证。,5.1.3 二叉树基本性质2,11,性质5-2 树高
5、为k（k0）的二叉树，最多有 个结点。,2k+1-1,证明： 由性质5-1可知在树高为k的二叉树当中，第0层有20个结点，第1层有21个结点，第2层有22个结点，第k层有2k个结点。由此可知，树高为k的二叉树结点个数总数为20 + 21 + 22 + 2k。这是一个公比为p=2的等比数列，前k+1项和Sk+1为： Sk+1 =（a0 akp）/（1p）= (202k2)/(12) = (12k+1)/(12) = 2k+11,5.1.3 二叉树基本性质3,性质5-3 如果二叉树中度为0结点数为n0，度为2结点数为n2， 则 成立。,12,n0=n2+1,证明：设结点总数 n = n0+ n1+
6、 n2 又因为：结点数n = 边数+1 边数 = n1+ 2*n2 即n0 + n1 + n2 = n1 + 2n2 + 1 所以：n0 = n2 + 1,结点数n = 边数+1,练习：,一棵树的度为4，n4=2， n3=3， n2=4，求n0？,13,解： 结点数 = 边数 + 1 n0+ n1+n2 +n3+n4 = n1+ 2*n2 + 3*n3 + 4*n4 + 1 n0 + 2 + 3 + 4 = 8 + 9 + 8 + 1 n0=17,练习：,设完全二叉树有1000个结点，求叶子结点个数？有多少个度为1的结点？度为2的结点呢？,14,解：设二叉树中叶子结点、度为1、度为2的结点数目
7、 分别n0、 n1、n2 ， 其中完全二叉树中n1只能为1或0，则：,n0+ n1+ n2 = 1000 n0 = n2+ 1 n1= 0 或 n1=1,复习两个概念：,（1）满二叉树：深度为k的满二叉树有 个结点。,15,2k+1-1,对满二叉树按层次从上到下，从左到右，不留一个空位进行编号，号码1n。,（2）完全二叉树：结点数为n的完全二叉树上各个结点与同深度的满二叉树前n个相应位置结点编号一一对应。,5.1.3 二叉树基本性质4,16,性质5-4 设BT为具n个结点的完全二叉树，将BT所有结点按照从上到下、从左到右的顺序（二叉树的层序）进行编号。则BT中任意结点N的序号i（1in）具有下
8、述性质。 （1）若i=1，则N为BT根结点，N无父结点； （2）若i1，则N父结点序号为 （即i除以2后向下取整）； （3）若2in，则N无左子树，否则其左子结点（即左子树的根结点）序号为2i； （4）若2i+1n，则N无右子树，否则其右子结点（即右子树的根结点）序号为2i+1。,练习：,1、1000个结点的完全二叉树最大的分支结点编号为 。 2、n个结点的完全二叉树深度为 。,17,500,int（log2n）,5.2 二叉树存储,5.2.1 二叉树顺序存储 预留最大空间 深度为k的二叉树预留2k+1-1个存储单元，按编号顺序存储，遇空结点留空位。,18,5.2.1 二叉树顺序存储2,适合满
9、（完全）二叉树，求双亲、孩子方便 不适合深度较大、结点不多的二叉树,19,5.2.2 二叉树链式存储,1、二叉链表存储 让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。,20,5.2.2 二叉树链式存储,1、二叉链表存储2,21,用C语言定义二叉链表的结构类型如下： struct node DataType data; /* 定义数据域，DataType代表实际需要的类型 */ struct node *lch; /* 定义左孩子域，指向左孩子地址 */ struct node *rch; /* 定义右孩子域，指向右孩子地址 */ ; typedef struct n
10、ode bitree; /* 定义二叉树结点类型为bitree */,1、二叉链表存储3,算法5-1 创建一棵只有根结点的二叉树算法。 创建只有以x为根结点的二叉树Bt，x的数据类型为DataType，相应结点的Lchild和Rchild域均取值NULL，返回指向根结点的指针。,22,00Create_Bt(DataType x) 01 02 bitree *Bt,*ptr; 03 ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点 */ 04 Bt=ptr; 05 ptr-data = x; 06 ptr-lch = NULL; 07 ptr
11、-rch = NULL; 08 return (Bt); 09 ,1、二叉链表存储4,算法5-2 在指定左子结点处插入一个新结点。 已知二叉链表Bt，在指针Parent所指结点左子结点处插入一个数据元素值为x的新结点，使之成为Parnet所指结点新的左子树根结点。,23,bitree *Inl_Bt(bitree *Bt, bitree *Parent, DataType x) if (Parent = NULL) printf (位置错！); return (NULL); ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点空间 */ ptr-
12、data = x; ptr-lch = NULL; ptr-rch = NULL; if (Parent-lch = NULL) /* Parent所指结点左子树为空 */ Parent-lch = ptr; else /* Parent所指结点左子树非空 */ ptr-lch = Parent-lch; Parent-lch = ptr; return(Bt) ,5.2.2 二叉树链式存储2,2、三叉链表存储 同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。,24,5.2.2 二叉树链式存储2,2、三叉链表存储2,25,5.3 二叉树的遍历,按照某种确定方式对二叉树进行访
13、问，但要求二叉树中每个结点被访问一次且只被访问一次。 1、先序、中序和后序遍历 对左、右子树，限定“先访左后访右”，那么访问结点的顺序有三种不同的组合形式：TLR、LTR、LRT。 通常，称TLR为二叉树的先序（先根）遍历， LTR为中序（中根）遍历， LRT为后序（后根）遍历。,26,例子：,以三种遍历方式访问如图所示的二叉树。,27,解：先序遍历序列 A-B-D-H-E-C-F-I-G-J-K 中序遍历序列 D-H-B-E-A-I-F-C-J-G-K 后序遍历序列 H-D-E-B-I-F-J-K-G-C-A,例子：,已知二叉树先序遍历序列是A-B-C-D-E-F-G，中序遍历序列是C-B-
14、D-A-E-G-F。由这两个序列可唯一确定一棵二叉树。,28,解：从先序遍历序列第一个结点可知二叉树根结点是A。由结点A在中序遍历序列里位置可知该根结点左子树包含结点C-B-D，右子树包含结点E-G-F，如图5-22所示。由中序序列片段C-B-D可知，B是A左子树根结点，再结合先序序列片段B-C-D可知，C和D分别是B的左右子结点。由先序序列片段E-F-G可知，E是A的右子结点，再由先序序列片段F-G和中序序列片段G-F可知，F不能是E的左子结点，故只能是E的右子结点，并且G是F的左子结点。,29,练习：,1、已知二叉树先序遍历序列为ABCDEFGH，中序遍历序列为CDBAFEHG，试画出此二
15、叉树。 2、已知二叉树后序遍历序列为DCBFHGEA，中序遍历序列为CDBAFEHG，求先序遍历序列。,30,5.3 二叉树的遍历2,2、基于递归遍历算法 递归步骤（先序遍历）： 访问根结点； 先序遍历访问左子二叉树； 先序遍历访问右子二叉树。,31,2、基于递归遍历算法2,算法5-4 二叉树先序遍历递归算法。 已知二叉树Bt，对其进行先序遍历，若二叉树为空，则为空操作；否则进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。,32,00 Pret_Bt(bitree *Bt) 01 02 if (Bt != NULL) 03 04 printf (%c, Bt-d
16、ata); /* 访问根结点 */ 05 Pret_Bt(Bt-lch); /* 先序遍历左子树 */ 06 Pret_Bt(Bt-rch); /* 先序遍历右子树 */ 07 08 ,2、基于递归遍历算法2,基于递归调用先序遍历:,33,2、基于递归遍历算法2,先序递归算法应用实例:先序建立二叉树 bitree *creat() bitree *t; int x; scanf(“%d”, ,2、基于递归遍历算法2,先序递归算法应用实例:先序建立二叉树(续) 主程序调用: main() bitree *root; root=creat(); 例：建立如图二叉树应该如何输入？ 练习： 测试用例：1 2 3 0 0
