五章节二叉树及应用课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 二叉树及应用,一种重要的非线性结构,第五章 二叉树及应用一种重要的非线性结构,学习要点：,二叉树的递归概念，这与二叉树各种基本运算具有密切关联。,满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。,二叉树的顺序存储与二叉链表存储结构。,二叉树遍历的基本思想和基于递归与非递归实现算法。,线索二叉树概念，二叉树的线索化和遍历。,Huffman,树概念与基本算法；,Huffman,编码和实现算法。,2,学习要点：二叉树的递归概念，这与二叉树各种基本运算具有密切关,5.1,二叉树及其基本性质,5.1.1,二叉树基本概念,“二叉树”是一个满足下述条件的由结点组成的有限集合,E,：,当,E,为空集时，定义其为空二叉树；,当,E,非空时，分为两种情形。,如果,E,为单元素集合，定义其为一棵,根二叉树,；,如果,E,为多于一个结点的集合，则,E,中应当具有唯一一个结点,r,称其为根结点，而集合,E=E r,也是一棵二叉树，称为,r,的子二叉树。此时，结点,r,至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为,r,的,左子树,和,右子树,。,3,5.1 二叉树及其基本性质5.1.1 二叉树基本概念3,其它一些相关概念：,结点的,度：,结点拥有的子树棵数,结点的,深度,（,层次,）：,根结点看做第,0,层，其余结点的层次值为其父结点所在层值加,1,树的度：,树中所有结点度的最大值,树的深度：,树中最大层次数,4,根结点、叶结点、内部结点,子结点、父结点、兄弟结点、堂兄弟结点、,子孙结点、祖先结点；,其它一些相关概念：结点的度：结点拥有的子树棵数 4根结点、叶,5.1.1,二叉树基本概念,2,1,、二叉树的特征,二叉树可以没有任何结点，即是一个空二叉树。,二叉树中每个结点至多只有两棵子树，而这两棵子树作为结点集合互不相交；,二叉树中结点的两棵子树有左、右之分，次序不能颠倒。,2,、二叉树基本类型,5,5.1.1 二叉树基本概念21、二叉树的特征5,5.1.2,满二叉树和完全二叉树,1,、满二叉树,如果一棵二叉树满足下述条件，就称其为满二叉树（,full binary tree,）：,每个结点或是度数为,2,（具有两个非空子树）的结点，或是度数为,0,的（叶）结点；,所有叶结点都在同一层。,6,5.1.2 满二叉树和完全二叉树1、满二叉树6,5.1.2,满二叉树和完全二叉树,2,2,、完全二叉树,若一棵二叉树满足下述条件，就称其为完全二叉树（,complete binary tree,）：,至多只有最下两层中结点的度数小于,2,；,最下一层的叶结点都依次排列在该层最左边位置。,7,5.1.2 满二叉树和完全二叉树22、完全二叉树7,5.1.2,满二叉树和完全二叉树,2,2,、完全二叉树,2,重点理解：,满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。,空二叉树和根二叉树既是满二叉树，也是完全二叉树。,完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若干个结点后得到二叉树。,完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。,8,5.1.2 满二叉树和完全二叉树22、完全二叉树28,练习：,1,、完全二叉树某结点若无右子树则定无左子树。,2,、完全二叉树某结点若无左子树则定无右子树。,9,练习：1、完全二叉树某结点若无右子树则定无左子树。9,5.1.3,二叉树基本性质,性质,5-1,一棵二叉树第,i,（,i0,）层上至多只能有,个结点。,10,2,i,证明：应用数学归纳法。,二叉树第,0,层有一个结点，即当,i=0,时，,2,i,=2,0,=1,成立。,假设结论对第,i,层成立，即第,i,层至多只能有,2,i,个结点。注意到二叉树每个结点的度最多为,2,，第,i+1,层结点个数至多只能是第,i,层结点个数的,2,倍，即,2*2,i,= 2,i+1,，归纳完成，命题得证。,5.1.3 二叉树基本性质性质5-1 一棵二叉树第i（i0,5.1.3,二叉树基本性质,2,11,性质,5-2,树高为,k,（,k0,）的二叉树，最多有,个结点。,2,k+1,-1,证明,：,由性质,5-1,可知在树高为,k,的二叉树当中，第,0,层有,2,0,个结点，第,1,层有,2,1,个结点，第,2,层有,2,2,个结点，第,k,层有,2,k,个结点。由此可知，树高为,k,的二叉树结点个数总数为,2,0,+ 2,1,+ 2,2,+,+ 2,k,。这是一个公比为,p=2,的等比数列，前,k,+1,项和,S,k,+1,为：,S,k,+1,=,（,a,0,a,k,p,）,/,（,1,p,）,= (2,0,2,k,2)/(12) = (12,k,+1,)/(12) = 2,k+1,1,5.1.3 二叉树基本性质211性质5-2 树高为k（k0,5.1.3,二叉树基本性质,3,性质,5-3,如果二叉树中度为,0,结点数为,n0,，度为,2,结点数为,n2,，,则,成立。,12,n,0,=n,2,+1,证明：设结点总数,n = n,0,+ n,1,+ n,2,又因为：结点数,n =,边数,+1,边数,= n,1,+ 2*n,2,即,n,0,+ n,1,+ n,2,= n,1,+ 2n,2,+ 1,所以：,n,0,= n,2,+ 1,结点数,n =,边数,+1,5.1.3 二叉树基本性质3性质5-3 如果二叉树中度为0结,练习：,一棵树的度为,4,，,n4=2,，,n3=3,，,n2=4,，求,n0,？,13,解： 结点数,=,边数,+ 1,n,0,+ n,1,+n,2,+n,3,+n,4,= n,1,+ 2*n,2,+ 3*n,3,+ 4*n,4,+ 1,n,0,+ 2 + 3 + 4 = 8 + 9 + 8 + 1,n,0,=17,练习：一棵树的度为4，n4=2， n3=3， n2=4，求n,练习：,设完全二叉树有,1000,个结点，求叶子结点个数？有多少个度为,1,的结点？度为,2,的结点呢？,14,解：设二叉树中叶子结点、度为,1,、度为,2,的结点数目,分别,n,0,、,n,1,、,n,2,，,其中完全二叉树中,n,1,只能为,1,或,0,，则：,n,0,+ n,1,+ n,2,= 1000,n,0,= n,2,+ 1,n,1,= 0,或,n,1,=1,n,0,= 500,n,1,= 1,n,2,=499,练习： 设完全二叉树有1000个结点，求叶,复习两个概念：,（,1,）,满二叉树,：深度为,k,的满二叉树有,个结点。,15,2,k+1,-1,对满二叉树按层次从上到下，从左到右，不留一个空位进行编号，号码,1n,。,（,2,）,完全二叉树,：结点数为,n,的完全二叉树上各个结点与同深度的满二叉树前,n,个相应位置结点编号一一对应。,复习两个概念：（1）满二叉树：深度为k的满二叉树有,5.1.3,二叉树基本性质,4,16,性质,5-4,设,BT,为具,n,个结点的完全二叉树，将,BT,所有结点按照从上到下、从左到右的顺序（二叉树的层序）进行编号。则,BT,中任意结点,N,的序号,i,（,1in,）具有下述性质。,（,1,）若,i=1,，则,N,为,BT,根结点，,N,无父结点；,（,2,）若,i1,，则,N,父结点序号为 （即,i,除以,2,后向下取整）；,（,3,）若,2in,，则,N,无左子树，否则其左子结点（即左子树的根结点）序号为,2i,；,（,4,）若,2i+1n,，则,N,无右子树，否则其右子结点（即右子树的根结点）序号为,2i+1,。,5.1.3 二叉树基本性质416性质5-4 设BT为具n个结,练习：,1,、,1000,个结点的完全二叉树最大的分支结点编号为,。,2,、,n,个结点的完全二叉树深度为,。,17,500,int,（,log,2,n,）,练习：1、1000个结点的完全二叉树最大的分支结点编号为,5.2,二叉树存储,5.2.1,二叉树顺序存储,预留最大空间,深度为,k,的二叉树预留,2,k+1,-1,个存储单元，按编号顺序存储，遇空结点留空位。,18,5.2 二叉树存储5.2.1 二叉树顺序存储18,5.2.1,二叉树顺序存储,2,适合满（完全）二叉树，求双亲、孩子方便,不适合深度较大、结点不多的二叉树,19,5.2.1 二叉树顺序存储2适合满（完全）二叉树，求双亲、孩,5.2.2,二叉树链式存储,1,、二叉链表存储,让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。,20,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 node,bitree;,/*,定义二叉树结点类型为,bitree */,5.2.2 二叉树链式存储1、二叉链表存储221用C语言定义,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-rch = NULL;,08 return (Bt);,09 ,1、二叉链表存储3算法5-1 创建一棵只有根结点的二叉树算,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-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) ,1、二叉链表存储4算法5-2 在指定左子结点处插入一个新结,5.2.2,二叉树链式存储,2,2,、三叉链表存储,同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。,24,5.2.2 二叉树链式存储22、三叉链表存储24,5.2.2,二叉树链式存储,2,2,、三叉链表存储,2,25,5.2.2 二叉树链式存储22、三叉链表存储225,5.3,二叉树的遍历,按照某种确定方式对二叉树进行访问，但要求二叉树中每个结点被访问一次且只被访问一次。,1,、先序、中序和后序遍历,对左、右子树，限定“先访左后访右”，那么访问结点的顺序,有,三种不同的组合形式：,TLR,、,LTR,、,LRT,。,通常，称,TLR,为二叉树的先序（先根）遍历，,LTR,为中序（中根）遍历，,LRT,为后序（后根）遍历。,26,5.3 二叉树的遍历按照某种确定方式对二叉树进行访问，但要,例子：,以三种遍历方式访问如图所示的二叉树。,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,例子：以三种遍历方式访问如图所示的二叉树。27解：先序遍历序,例子：,已知二叉树,先,序遍历序列是,A-B-C-D-E-F-G,，中序遍历序列是,C-B-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,的左子结点。,例子：已知二叉树先序遍历序列是A-B-C-D-E-F-G，中,29,29,练习：,1,、已知二叉树先序遍历序列为,ABCDEFGH,，中序遍历序列为,CDBAFEHG,，试画出此二叉树。,2,、已知二叉树后序遍历序列为,DCBFHGEA,，中序遍历序列为,CDBAFEHG,，求先序遍历序列。,30,练习：1、已知二叉树先序遍历序列为ABCDEFGH，中序遍历,5.3,二叉树的遍历,2,2,、基于递归遍历算法,递归步骤,（,先序遍历,）：,访问根结点；,先序遍历访问左子二叉树；,先序遍历访问右子二叉树。,31,5.3 二叉树的遍历22、基于递归遍历算法31,2,、基于递归遍历算法,2,算法,5-4,二叉树先序遍历递归算法。,已知二叉树,Bt,，对其进行先序遍历，若二叉树为空，则为空操作；否则进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。,32,00 Pret_Bt(bitree *Bt),01 ,02 if (Bt != NULL),03 ,04 printf (%c, Bt-data); /*,访问根结点 *,/,05 Pret_Bt(Bt-lch); /*,先序遍历左子树 *,/,06 Pret_Bt(Bt-rch); /*,先序遍历右子树 *,/,07 ,08 ,2、基于递归遍历算法2算法5-4 二叉树先序遍历递归算法。,2,、基于递归遍历算法,2,基于递归调用先序遍历,:,33,2、基于递归遍历算法2基于递归调用先序遍历:33,2,、基于递归遍历算法,2,先序递归算法应用实例,:,先序建立二叉树,bitree *creat(), bitree *t; int x;,scanf(“%d”,if (x=0) t=NULL;,else, t=(bitree *) malloc (sizeof(bitree);,t-data=x;,t-lch=creat(); t-rch=creat();,return t;,2、基于递归遍历算法2先序递归算法应用实例:先序建立二叉树,2,、基于递归遍历算法,2,先序递归算法应用实例,:,先序建立二叉树,(,续,),主程序调用,:,main(), bitree *root;,root=creat();,例：,建立如图二叉树应该如何输入？,练习：,测试用例：,1 2 3 0 0 4 0 5 0 0 6 0 0,问：画出建立的二叉树？,2、基于递归遍历算法2先序递归算法应用实例:先序建立二叉树(,2,、基于递归遍历算法,3,算法,5-5,二叉树中序遍历递归算法。,已知二叉树,Bt,，对其进行中序遍历，若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树的右子树。,36,00 Indt_Bt(bitree *Bt),01 ,02 if (Bt != NULL),03 ,04 Indt_Bt(Bt-lch);/*,中序遍历左子树 *,/,05 printf (%c, Bt-data);/*,访问根结点 *,/,06 Indt_Bt(Bt-rch);/*,中序遍历右子树 *,/,07 ,08 ,2、基于递归遍历算法3算法5-5 二叉树中序遍历递归算法。,2,、基于递归遍历算法,3,基于递归调用,中,序遍历,:,37,2、基于递归遍历算法3基于递归调用中序遍历:37,2,、基于递归遍历算法,4,算法,5-6,二叉树后序遍历递归算法。,已知二叉树,Bt,，对其进行后序遍历，若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉树根结点。,38,00 Postv_Bt(bitree *Bt),01 ,02 if (Bt != NULL),03 ,04 Postv_Bt(Bt-lch); /*,后序遍历左子树 *,/,05 Postv_Bt(Bt-rch); /*,后序遍历右子树 *,/,06 printf (%c, Bt-data); /*,访问根结点 *,/,07 ,08 ,2、基于递归遍历算法4算法5-6 二叉树后序遍历递归算法。,2,、基于递归遍历算法,4,基于递归调用,后,序遍历,:,39,2、基于递归遍历算法4基于递归调用后序遍历:39,5.3,二叉树的遍历,3,3,、基于非递归遍历算法,非递归遍历算法中，需要做出三条假设：, 设置一个一维数组,Ss,作为顺序栈以临时保存遍历时遇到的结点信息，其栈顶指针为,Ss-top,，初始时为,0,。, 采用二叉链表结构保存需要遍历的二叉树，起始指针为,Bt,，每个结点包含,Data,、,Lchild,和,Rchild,等三个域。, 对结点进行的“访问”理解为将该结点的,Data,域的值打印出来。,40,5.3 二叉树的遍历33、基于非递归遍历算法40,3,、基于非递归遍历算法,2,算法,5-7,先序遍历二叉树的非递归算法。,已知二叉树,Bt,，顺序栈,Ss,，要求打印出该二叉树的先序遍历序列。,41,00 Pre_Bt(bitree *Bt),01 ,02 bitree *p;,03 bitree *stack10; /*,定义栈数组 *,/,04 int top=-1; /*,定义栈顶下标,top,并赋初值,-1 */,05 printf(nOutput preorder:);,06 p= Bt;,07 while(p!=NULL | top!=-1),08 if (p!=NULL),09 ,10 printf(%d ,p-data); /*,访问该结点 *,/,11 top=top+1;stacktop=p; /*,访问后入栈 *,/,12 p=p-lch; /*,继续深入左孩子 *,/,13 ,14 else,15 ,16 p=stacktop;top=top-1; /*,遇空出栈，栈顶给,p */,17 p=p-rch; /*,转向右孩子 *,/,18 ,19 ,3、基于非递归遍历算法2算法5-7 先序遍历二叉树的非递归,3,、基于非递归遍历算法,2,基于非递归二叉树先序遍历：,42,3、基于非递归遍历算法2基于非递归二叉树先序遍历：42,3,、基于非递归遍历算法,3,中序非递归遍历算法流程,:,bitree *p;,定义及初始化栈,;,p=root;,while(p!=NULL |,栈不空,),if (p!=NULL),p,进栈；,p=p-lch;,else,栈顶给,p,并出栈；,输出,p,；,p=p-rch;,3、基于非递归遍历算法3中序非递归遍历算法流程:,3,、基于非递归遍历算法,3,算法,5-8,中序遍历二叉树的非递归算法。,已知二叉树,Bt,，顺序栈,Ss,，要求打印出该二叉树的中序遍历序列。,44,00 In_Bt(bitree *Bt),01 ,02 bitree *stack10; /*,定义栈数组 *,/,03 int top=-1; /*,定义栈顶下标,top,并赋初值,-1 */,04 bitree *ptr;,05 ptr = Bt;/* ptr,是工作指针 *,/,06 do,07 ,08 while (ptr != NULL) /*,一直朝左子树深入下去 *,/,09 ,10 top+; /*,调整栈顶指针 *,/,11 stacktop = ptr; /* ptr,所指结点进栈 *,/,12 ptr = ptr-lch;,13,14 if (Ss_top !=-1 ),15 ,16 ptr = stacktop ; /*,栈顶元素赋值给,ptr */,17 top - ; /*,出栈 *,/,18 printf (%d , ptr-data); /*,访问该结点 *,/,19 ptr = ptr-rch; /*,进入右子树访问 *,/,20 ,21 while(ptr !=NULL)|(top!=-1);,22 ,3、基于非递归遍历算法3算法5-8 中序遍历二叉树的非递归,3,、基于非递归遍历算法,3,基于非递归二叉树中序遍历（,1-4,趟）：,45,3、基于非递归遍历算法3基于非递归二叉树中序遍历（1-4趟）,3,、基于非递归遍历算法,3,基于非递归二叉树中序遍历（,1-4,趟）：,46,3、基于非递归遍历算法3基于非递归二叉树中序遍历（1-4趟）,3,、基于非递归遍历算法,4,算法,5-9,后序遍历二叉树的非递归算法（略）。,已知二叉树,Bt,，顺序栈,Ss,，要求打印出该二叉树的后序遍历序列。,47,算法要点：,由于后序遍历是“左、右、根”，因此在后序遍历过程中搜索到某个结点时，不是马上访问它，而是将其作为相应子树根结点保存在工作栈中，然后沿着其左子树继续深入直到“最左下”结点。完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍然不能马上进行访问，而是在工作栈中对其进行,第二次保存,，同时对其右子树进行遍历。在访问完右子树后，从工作栈中得到根结点信息，由此实现对相应根结点访问。,3、基于非递归遍历算法4算法5-9 后序遍历二叉树的非递归,3,、基于非递归遍历算法,4,基于非递归二叉树后序遍历第,1-3,趟运算变化：,48,3、基于非递归遍历算法4基于非递归二叉树后序遍历第1-3趟运,3,、基于非递归遍历算法,4,基于非递归二叉树后序遍历第,4,趟运算变化：,49,3、基于非递归遍历算法4基于非递归二叉树后序遍历第4趟运算变,3,、基于非递归遍历算法,4,基于非递归二叉树后序遍历第,5-7,趟运算变化：,50,3、基于非递归遍历算法4基于非递归二叉树后序遍历第5-7趟运,上机：,1,、用先序,递归方法,建立一棵二叉树；,2,、用中序,非递归,方法遍历该二叉树。,51,上机：1、用先序递归方法建立一棵二叉树；51,5.4,线索二叉树,5.4.1,线索与线索二叉树,结合遍历方式特点使用这些空链域来存放相应前驱或后继信息即前驱或后继的地址。, 当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，添加该结点在相应历序列中前驱结点地址。, 当前结点右孩子域非空时，保留原指针不变；当右孩子域为空时，添加该结点在相应遍历序列中后继结点地址。,52,5.4 线索二叉树5.4.1 线索与线索二叉树52,5.4.1,线索与线索二叉树,2,一个中序线索二叉树的例子：,53,5.4.1 线索与线索二叉树2一个中序线索二叉树的例子：53,5.4.2,创建线索二叉树,1,、创建线索二叉树结点,54,算法,5-10,（线索二叉树结点结构）,01 struct ThreadNode,/*,线索二叉树结点的定义,*/,02 ,03 DataType info;,04struct ThreadNode llink, rlink;,05 int ltag, rtag;,06 ;,07 typedef struct ThreadNode ThreadTree;,/*,线索二叉树类型的定义,*/,5.4.2 创建线索二叉树1、创建线索二叉树结点54算法5-,5.4.2,创建线索二叉树,2,2,、二叉树的线索化,55,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针,pre,，并始终保持指针,pre,指向当前访问的、指针,p,所指结点的前驱。将给定二叉树扩充为线索二叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。,线索化实际上就是在遍历过程中,在当前结点的空链域中添加前驱或后继指针,。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个工作指针,pre,始终指向刚访问过的结点，也就是说，当指针,p,指向当前访问结点时，,pre,就指向,p,的前驱结点。,5.4.2 创建线索二叉树22、二叉树的线索化55在中序遍历,5.4.2,创建线索二叉树,3,3,、线索二叉树遍历,56,以下以对中序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二：, 怎样获取中序遍历的首结点？,从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于“最左下”的结点，结点是“最左下”的含义是该结点再无左子结点，亦即该结点的左指针域为空。, 怎样获取在中序线索化链表中当前结点的后继结点？,如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树“最左下”结点，此即为当前结点的后继。,5.4.2 创建线索二叉树33、线索二叉树遍历56以下以对中,5.4.2,创建线索二叉树,3,3,、线索二叉树遍历,2,57,算法,5-12,基于中序线索二叉树中序遍历算法,00 void thrInOrder(ThreadTree *root ),01 ,02 ThreadTree *p;,03 p = root-llink;,04 if (p=NULL),05 return ;,06 while ( p-llink!=NULL & p-ltag=0 ),07 p = p-llink; /*,一直到“最左下” *,/,08 while (p!=root),09 ,10 printf(%d ,p-info);,11 if ( p-rlink!=NULL & p-rtag=0 ) /*,右子树不是线索时 *,/,12 ,13 p = p-rlink;,14 while (p-llink!=NULL&p-ltag=0),15 p = p-llink; /*,顺右子树的左子树一直向下 *,/,16 ,17 else,18 p = p-rlink;,19 ,20 ,5.4.2 创建线索二叉树33、线索二叉树遍历257算法5-,5.5 Huffman,编码,5.5.1,等长与非等长编码,所谓编码（,code,），就是用一组不同的代码表示一个数据对象集合中的每个元素的过程。,1,、两种基本编码类型,编码三要素：, 唯一性：,发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同；, 简洁性：,发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。, 前缀性：,两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有“前缀性”（,Prefix Property,）；,58,5.5 Huffman编码5.5.1 等长与非等长编码58,5.5.1,等长与非等长编码,2,2,、最优二叉树与,Huffman,树,二叉树路径长度,：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的“路径长度”。,叶结点的权,：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的“权”。,二叉树带权路径长度,：设二叉树具有,n,个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的“带权路径长度”，记为：,59,WPL=,w,k,l,k,（,w,k,是第,k,个叶结点权值，,l,k,是第,k,个叶结点路径长度,）,“,Huffman,树”,：,由,带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是“最优二叉树”。,5.5.1 等长与非等长编码22、最优二叉树与Huffman,5.5.2 Huffman,树构建思想,设有,n,个权值,w1,、,w2,、,w3,、,、,wn,，则可按照下述步骤构造,Huffman,树：,Step 1.,构造,n,棵只有一个根结点的二叉树森林,HT = T1,，,T2,，,T3,，,，,Tn,，它们分别以,w1,、,w2,、,w3,、,、,wn,作为权值。,Step 2.,在,HT,集合中，选取权值最小和次小的两个根结点作为一棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子树根结点权值之和；,Step 3.,在,HT,集合中，删除已经取为左、右子树的原两棵二叉（根）树，并将新构成二叉树添加到,HT,中；,Step 4.,重复,Step 2,和,Step 2,至,HT,只剩下一棵二叉树，此即是所求,Huffman,树。,60,5.5.2 Huffman树构建思想设有n个权值w1、w2、,5.5.2 Huffman,树构建思想,2,构造具有四个分别带有权值,1,、,3,、,5,、,7,的,Huffman,树如下图所示：,61,5.5.2 Huffman树构建思想2构造具有四个分别带有权,练习：,已知有,6,个叶子，值分别为,A,、,B,、,C,、,D,、,E,、,F,，它们的权值分别为,4,，,9,，,1,，,3,，,2,，,1,，试构造哈夫曼树（左权右权）。,62,练习： 已知有6个叶子，值分别为A、B、,5.5.3,基于顺序存储,Huffman,树构造,1,、,Huffman,树结点结构,问题：若哈夫曼树有,n,0,个叶子结点，则所有结点,个。,63,2n,0,-1,解：因为树中无度为,1,的结点，,由二叉树的性质,3,知：,n,0,=n,2,+1,所以：,n,=n,0,+n,2,=n,0,+n,0,-1,=2n,0,-1,由于最终结果中结点个数已经确定，因此可采用顺序结构存储存放所建,Huffman,树,5.5.3基于顺序存储Huffman树构造1、Huffman,5.5.3,基于顺序存储,Huffman,树构造,1,、,Huffman,树结点结构,2,问题：结点结构如何构造？,64,00 struct node,01 ,02 int weight;,03 int parent,lch,rch;,04 ;,05 struct node HtreeMAX;,5.5.3基于顺序存储Huffman树构造1、Huffman,5.5.3,基于顺序存储,Huffman,树构造,2,2,、,Huffman,树构造算法,问题：算法如何构造,Huffman,树？,65,原理：,找两,无双亲,且,权值最小,结点合并，生成新结点，填写相关信息（,两结点双亲，新结点权值，新结点左、右孩子,）。,5.5.3基于顺序存储Huffman树构造22、Huffma,算法,5-13,基于顺序存储,Huffman,树构造算法,00 creat_huff(struct node Htree),01 ,02 int i,j,min1,min11,min2,min22;,03 printf(nInput the count of leaves(10):);,04 scanf(%d,/*,读取叶子结点个数,n */,05 for (i=0;i2*n-1;i+),/*,数组,Htree,初始化 *,/,06 ,07 Htreei.parent=-1;,08 Htreei.lch=-1;,09 Htreei.rch=-1;,10 ,11 printf(nInput the leavess weight:);,12 for (i=0;in;i+),/*,读取各个叶子的权值并赋值到,Htree,数组 *,/,13 scanf(%d,66,算法5-13 基于顺序存储Huffman树构造算法 00,算法,5-13,基于顺序存储,Huffman,树构造算法,2,14 for (i=n;i2*n-1;i+),/*,控制,n-1,次二叉树的合并 *,/,15 ,16 min2=min1=MAX;,/* min1,、,min2,记录当前最小、次小权值 *,/,17 min11=min22=0;,/* min11,、,min22,记录当前最小、次小权值结点位置 *,/,18 for (j=0;ji;j+),/*,在,j,的范围内，找最小、次小结点 *,/,19 ,20 if (Htreej.parent=-1),21 if (Htreej.weightmin1),/*,如当前权值比最小结点还小 *,/,22 ,23 min22=min11;,24 min2=min1;,/*,最小结点信息赋给次小 *,/,25 min11=j;,26 min1=Htreej.weight;,/*,当前权值信息赋给最小 *,/,27 ,28 else,67,算法5-13 基于顺序存储Huffman树构造算法2 14,算法,5-13,基于顺序存储,Huffman,树构造算法,3,29 if (Htreej.weightmin2),/*,如当前权值比次小结点小 *,/,30 ,31 min22=j;,32 min2=Htreej.weight;,/*,当前权值信息赋给次小 *,/,33 ,34 ,35 Htreemin11.parent=i;,/*,设置最小权值结点的,parent,域 *,/,36 Htreemin22.parent=i;,/*,设置次小权值结点的,parent,域 *,/,37 Htreei.weight=Htreemin11.weight+Htreemin22.weight;,/*,设置新结点的权值域 *,/,38 Htreei.lch=min11;,/*,设置新结点的,lch,域为最小结点 *,/,39 Htreei.rch=min22;,/*,设置新结点的,rch,域为次小结点 *,/,40 ,41 Htree2*n-2.parent=-1;,/*,最后一个结点为根结点，,parent,域为,-1 */,42 ;,68,算法5-13 基于顺序存储Huffman树构造算法3 29,5.5.3,基于顺序存储,Huffman,树构造,3,3,、,Huffman,树算法分析,69,设有叶结点相应权值分别为,1,，,3,，,5,，,7,。按照算法构建,Huffman,树过程如,下,图所示,：,5.5.3基于顺序存储Huffman树构造33、Huffma,5.5.3,基于顺序存储,Huffman,树构造,3,3,、,Huffman,树算法分析,70,设有,叶结点相应权值分别为,1,，,3,，,5,，,7,。,按照算法构建,Huffman,树过程如,下,图所示,（续）：,5.5.3基于顺序存储Huffman树构造33、Huffma,5.5.4 Huffman,编码,1,、,Huffman,编码概念,基于具体,Huffman,树的不等长编码就称为,Huffman,编码,。,首先得到需要编码的字符,c,1,、,c,2,、,c,n,在相应数据信息中出现的频率为,p,1,、,p,2,、,p,n,；再以,c,1,、,c,2,、,c,n,作为叶结点，,p,1,、,p,2,、,p,n,作为相应权值，按照,Huffman,算法构造一棵,Huffman,树。,其次，由构造的,Huffman,树的根结点开始，在每个左分支上标注,0,，右分支上标注,1,。这样，从根结点到每个叶结点的路径上由,0,、,1,组成的序列，就是该结点对应字符的编码。,71,5.5.4 Huffman编码1、Huffman编码概念71,5.5.4 Huffman,编码,1,、,Huffman,编码概念,2,编码,步骤,1,：,先建,Huffman,树,72,5.5.4 Huffman编码1、Huffman编码概念27,5.5.4 Huffman,编码,1,、,Huffman,编码概念,2,编码,步骤,1,：,先建,Huffman,树,（续）,73,5.5.4 Huffman编码1、Huffman编码概念27,5.5.4 Huffman,编码,1,、,Huffman,编码概念,2,编码,步骤,2,：,再编码,74,5.5.4 Huffman编码1、Huffman编码概念27,5.5.4 Huffman,编码,2,2,、,Huffman,编码算法,问题：如何编码？,原理：,从叶子结点到根结点顺着路径分支为其编码。,75,5.5.4 Huffman编码22、Huffman编码算法7,算法,5-14 Huffman,编码算法,00 code_huff(struct node Htree),01 ,02 int i,j,k,pr,start;,03 for (i=0;in;i+),04 ,05 j=n-2;,06 k=i;,/* k,记录当前编码结点，初始为叶结点位置 *,/,07 while(Htreek.parent!=-1),08 ,09 pr=Htreek.parent;,/*,记录,k,的父结点 *,/,10 if(k=Htreepr.lch),11 codeij=0;,/*,左分支编码为,0 */,12 else,13 codeij=1;,/*,右分支编码为,1 */,14 j=j-1;,15 k=pr;,/*,进到路径的上一个结点，直至根结点 *,/,16 ,17 codein-1=j+1;,/*,存放编码的起始位置是,j+1 */,18 ,76,算法5-14 Huffman编码算法00 code_hu,算法,5-14 Huffman,编码算法,2,19 printf(n The code are:n);,20 for (i=0;in;i+),21 ,22 start=codein-1;,/*,取出编码的起始位置 *,/,23 for (j=start;jn-1;j+),/*,逐个输出编码 *,/,24 printf( %-3d,codeij);,25 printf(n);,26 ,27 ,77,算法5-14 Huffman编码算法219 prin,5.5.4 Huffman,编码,3,3,、,Huffman,编码算法分析,Huffman,编码过程如,下,图所示,：,78,5.5.4 Huffman编码33、Huffman编码算法分,练习：,设有,7,个带权结点,A,，,B,，,C,，,D,，,E,，,F,，,G,，其权值分别为,3,，,7,，,8,，,2,，,5,，,8,，,4,，试以这,7,带权结点为叶子结点，构造一棵哈夫曼树（左权右权）。,79,练习： 设有7个带权结点A，B，C，D，E，F，G，,练习：,在一份报文中有五种字符，,A,，,B,，,C,，,D,，,E,，它们在报文中出现的频率比例为,4,，,7,，,5,，,2,，,9,，试通过构造最优二叉树来确定每种字符的哈夫曼编码（左权右权）。,80,练习： 在一份报文中有五种字符，A，B，C，D，E，,上 机：,81,理解建立,huffman,树的过程及编码过程。,1.,结点定义（需要至少,4,个域：,weight,，,parent,，,lch,，,rch,）,2.,定义数组,3.,输入叶子的个数,n,4.,数组初始化,5.,输入叶子的权值,6.,循环,n,1,次做：,（,1,）找两个最小权值及其下标,（,2,）合并，填写相关信息,7.,输出数组,8.,编码并输出,上 机：81理解建立huffman树的过程及编码过程。,本章小结,本章基本内容,本章小结本章基本内容,