数据结构2-第7章1-算法与数据结构.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,树,二叉树,树、森林与二叉树的转换,树的应用,第七章 树和二叉树,树和森林的概念,树的定义,树是由,n,(,n,0),个结点组成的有限集合。如果,n,=0，称为空树；如果,n,0，则,有一个特定的称之为,根(root),的结点，它只有直接后继，但没有直接前驱；,除根以外的其它结点划分为,m,(,m,0)个互不相交的有限集合,T,0,T,1,T,m,-1,，每个集合又是一棵树，并且称之为根的,子树(subTree),。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,结点(,node),结点的度(,degree),结点的子树个数,分支(,branch),结点 度不为0的结点,叶(,leaf),结点 度为0的结点,子女(,child),结点 某结点子树的根结点,双亲(,parent),结点,某个结点是其子树之根的,双亲,兄弟(,sibling),结点 具有同一双亲的所有结点,祖先(,ancestor),结点,若树中结点,k,到,k,s,存在一条路径，,则称,k,是,k,s,的祖先,子孙(,descendant),结点,若树中结点,k,到,k,s,存在一条路径，,则称,k,s,是,k,的子孙,结点所处层次(,level),根结点的层数为0，其余结点的层,数为双亲结点的层数加1,树的高度(,depth),树中结点的最大层数,树的度(,degree,),树中所有结点度的最大值,有序树 子树的次序不能互换,无序树 子树的次序可以互换,森林 互不相交的树的集合,凹入表表示,a,b,d,e,i,j,f,c,g,h,嵌套集合表示,嵌套括号表示,i,j,d,f,g,h,a,b,c,e,a(b(d,e(i,j),c(g,h),树的抽象数据类型,数据集合:,操作集合,MAKETREE（*T）；,初始条件：给出树,T,的定义。,操作结果：按树,T,的定义构造树,T。,DESTROYTREE（*T）；,初始条件：树,T,存在。,操作结果：销毁树,T。,树的存储结构,1 双亲的表示法,2 孩子表示法,3 双亲孩子表示法,4 孩子兄弟表示法 树转二叉树的方法,双亲表示法,实现：定义结构数组存放树的结点，每个结点含两个域：,数据域：存放结点本身信息,双亲域：指示本结点的双亲结点在数组中位置,特点：找双亲容易，找孩子难,typedef struct node,datatype data;,int parent;,bnode;,bnode tM;,孩子表示法,多重链表：每个结点有多个指针域，分别指向其子树的根,结点同构：结点的指针个数相等，为树的度,D,结点不同构：结点指针个数不等，为该结点的度,d,data child1 child2 .childD,data degree child1 child2 .childd,孩子链表：每个结点的孩子结点用单链表存储，再用含n,个元素的结构数组指向每个孩子链表,孩子结点：typedef struct node,int child;/,该结点在表头数组中下标,struct node *next;/指向下一孩子结点,bnode;,表头结点：typedef struct tnode,datatype data;/数据域,struct node *fc;/指向第一个孩子结点,TD;,TD tM;/t0不用,带双亲的孩子链表,6,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,0,1,2,2,3,5,5,5,1,parent,a,b,c,d,e,f,h,g,i,孩子兄弟表示法（二叉树表示法）,实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点,特点,操作容易,破坏了树的层次,typedef struct node,datatype data;,struct node *fch,*nsib;,bnode;,a,b,c,d,e,f,h,g,i,a,b,c,d,e,f,g,h,i,定义1,满二叉树(Full Binary Tree),一棵深度为k 且有2,k+1,-1个结点的二叉树。,2,4,5,3,6,7,1,定义2,完全二叉树(Complete Binary Tree),若设二叉树的高度为,h,，则共有,h,+1层。除第,h,层外，其它各层(0,h,-1,)的结点数都达到最大个数，第,h,层从右向左连续缺若干结点，这就是完全二叉树。,1,2,3,11,4,5,8,9,12,13,6,7,10,14,15,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,二叉树的抽象数据类型,数据集合:二叉树结点的集合,每个结点由数据元素和构造数据元素之间的,关系的指针组成.,操作集合:,创建:MakeTree(T),撤消:DestroyTree(T),左插入结点:InsertLeftNode(curr,x),右插入结点:InsertRightNode(curr,x),左删除子树:DeleteLeftNode(curr,x),右删除子树:DeletInsertRightNode(curr,x),遍历二叉树:Traverse(T,Visit(),性质1,若二叉树的层次从1开始,则在二叉树的,第,i,层最多有 2,i-1,个结点。(,i,0),二叉树的性质,证明：i=1 时，有2,i-1,=,2,0,=1，成立,假定,：,i=k 时性质成立；,当 i=k+1 时，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为22,k-1,=,2,k,故命题成立,性质3,具有,n,个结点的完全二叉树的深度,为不超过log,2,(n+1),-,1的最大整数,证明,：设所求完全二叉树的深度为k。由完全二叉树定义可得：深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2,k,-1个结点。由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：n2,k+1,-1。另一方面，由性质2可得：n2,k+1,-1，即：2,k,-ln2,k+1,-1,2,h,=,n+1,2,h+1,取对数,h,log,2,(,n+1,)2,k+1,-1。另一方面，由性质2可得：n2,k+1,-1，即：2,k,-ln2,k+1,-1,由此可推出：2,k-1,n2,k,，取对数后有：klgn,0,则,i,的双亲为,i,/,2,若2*,i+1,n/2,的结点必定是页结点,若2*,i,+,2,n，,即不存在结点1，此是，结点,i,无孩子。结点,i,的右孩子也只能是结点2，若结点2不存在，即2,n，,此时结点,i,无右孩子。,性质,对任何一棵二叉树,如果其叶结点个数为,n,0,度为2的非叶结点个数为,n,2,则有,n,0,n,2,1,证明：,1、结点总数等于度为0的结点加上度为1的结点再加上度,为2的结点：,n=n,0,+n,1,+n,2,2、另一方面，二叉树中一度结点有一个孩子，二 度结,点有二个孩子，根结点不是任何结点的孩子，因此，,结点总数为：,n=n,1,+2n,2,+1,3、两式相减，得到：,n,0,=n,2,+1,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,链表表示,二叉树链表表示的示例,二叉链表的静态结构,树结点的描述,typedef int datatype;,typedef struct node,datatype data;,struct node*lchild,*rchild;,btnode;,void initiate(btnode*root),*root=(btnode*)malloc(sizeof(btnode);,(*root)-lchild=NULL;,(*root)-rchild=NULL;,btnode*insertLnode(btnode*curr,datatype x),btnode*s,*t;,if(curr=NULL)return NULL;,t=curr-lchild;,s=(btnode*)malloc(sizeof(btnode);,s-data=x;s-lchild=t;s-rchild=NULL;,curr-lchild=s;,return curr-lchild;,btnode*insertRnode(btnode*curr,datatype x),btnode*s,*t;,if(curr=NULL)return NULL;,t=curr-rchild;,s=(btnode*)malloc(sizeof(btnode);,s-data=x;s-rchild=t;s-rchild=NULL;,curr-rchild=s;,return curr-rchild;,btnode*deleteLtree(btnode*curr),if(curr=NULL|curr-lchild=NULL)return NULL;,destroy(&curr-lchild),curr-lchild=NULL;,return curr;,btnode*deleteRtree(btnode*curr),if(curr=NULL|curr-rchild=NULL)return NULL;,destroy(&curr-rchild),curr-rchild=NULL;,return curr;,前序遍历,前序遍历二叉树算法的框架是,若二叉树为空，则空操作；,否则,访问根结点(,V)；,前序遍历左子树(,L)；,前序遍历右子树(,R)。,遍历结果,-,+,a,*,b,-,c d,/,e f,二叉树的遍历,前序遍历算法,PreORDER(btree*t),if(t!=null),printf(“t%cn”,t-data);,PreORDER(t-lchild);,PreORDER(t-rchild);,中序遍历二叉树算法的框架是：,若二叉树为空，则空操作；,否则,中序遍历左子树(,L)；,访问根结点(,V)；,中序遍历右子树(,R)。,遍历结果,a,+,b,*,c,-,d,-,e,/,f,中序遍历,表达式语法树,中序遍历算法,INORDER(bitree*t),if(t!=null),INORDER(t-lch);,printf(“t%cn”,t-data);,INORDER(t-rch);,中序遍历二叉树的递归过程图解,后序遍历,后序遍历二叉树算法的框架是,若二叉树为空，则空操作；,否则,后序遍历左子树(,L)；,后序遍历右子树(,R)；,访问根结点(,V)。,遍历结果,a b c d,-,*+,e f,/,-,中序遍历算法,PostORDER(btree*t),if(t!=null),PostORDER(t-lchild);,PostORDER(t-rchild);,printf(“t%cn”,t-data);,层序遍历,层序遍历二叉树算法的框架是,(1)初始化一个队列,(2)或树非空,则将根结点入队,(3)当队列非空时,循环:,a.,一个结点出队,并访问该结点,b.,若该结点左子树非空,该结点左子树指针入队,c.,若该结点右子树非空,该结点右子树指针入队,(4)结束,遍历结果,-+/,a,*,e f,b,-,c d,二叉树撤消操作:,void destroy(btree*node),if(*root)!=null&(*root)-lchild!=null),destroy(,if(*root)!=null&(*root)-rchild!=null),destroy(,free(*root);,二叉树的应用,1.打印二叉树,void pribtree(btree*bt,int n),int i;,if(bt=null)return;,pribtree(bt-rchild,n+1);,for(i=0,i0),printf(-);,printf(%cn,bt-data);,pribtree(bt-lchild,n+1);,2.在二叉树中查找具有给定值的结点,biter findnode(biter*t,datatype x),if(t=NULL)return(NULL);,else if(t-data=x)return(t);,else return(findnode(t-lchild)|,findnode(t-rchild),例：求二叉树的深度,int depth(biter*t),int dep1,dep2;,if(t=NULL)return(-1);,else,dep1=depth(t-lchild);,dep2=depth(t-rchild);,if(dep1 dep2)return(dep1+1);,else return(dep2+1);printf(“n”);,应用举例,#include,#include,type char datatype;,void pribtree(btree*bt,int n),int i;,if(bt=null)return;,pribtree(bt-rchild,n+1);,for(i=0,i0),printf(-);,printf(%cn,bt-data);,pribtree(bt-lchild,n+1);,void main(),btree*root,*p,*pp;,initiate(,p=insertLnode(root,a);,p=insertLnode(p,b);,p=insertLnode(p,d);,p=insertRnode(p,g);,p=insertRnode(root-lchild,c);,pp=p,p=insertLnode(p,e);,p=insertRnode(pp,f);,printbtree(root,0);,preorder(root-lchild);,destroy(,非递归的二叉树遍历算法,(1)初始化一个堆栈,(2)把根结点入栈,(3)当堆栈非空时,循环:,A.出栈取一个结点指针,访问该结点;,B.若该 结点右子树非空,右子树指针入栈,C.若该 结点左子树非空,左子树指针入栈,非递归算法,A,B,C,D,E,F,G,p,i,P-A,(1),A,B,C,D,E,F,G,p,i,P-B,(2),A,B,C,D,E,F,G,p,i,P-D,P-C,(3),p=NULL,A,B,C,D,E,F,G,i,P-D,访问：ABC,(4),访问：AB,访问：A,p,A,B,C,D,E,F,G,i,P-F,P-E,访问：ABCD,(5),A,B,C,D,E,F,G,i,P-F,P-G,访问：ABCDE,p,(6),A,B,C,D,E,F,G,i,P-F,访问：ABCDEG,p,(7),A,B,C,D,E,F,G,i,访问：ABCDEGF,p,(8),遍历算法应用,按先序遍历序列建立二叉树的二叉链表，已知先序序列为：,A B C,D E G F ,求二叉树深度算法,Ch5_5.c,ch5_6.c,A,B,C,D,E,F,G,A ,B,C ,D,E,F ,G ,Ch5_1.c,统计二叉树中叶子结点个数算法,线索二叉树,定义：,前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为,线索：指向前驱或后继结点的指针称为,线索二叉树：加上线索的二叉链表表示的二叉树叫,线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫,实现,在有n,个结点的二叉链表中必定有n+1个空链域,在线索二叉树的结点中增加两个标志域,ltag :若 ltag=0,lchild 域指向左孩子；若 ltag=1,lcild域指向其前驱,rtag :若 rtag=0,rchild 域指向右孩子；若 rtag=1,rchild域指向其后继,线索二叉树结点的描述,typedef int datatype;,typedef struct node,int ltag,rtag;,datatype data;,struct node*lchild,*rchild;,bithptr;,bithptr*pre;,lchild,ltag,rtag,data,rchild,标志位如果为0，表示指针指向孩子结点，为1表示指针为线索,A,B,C,D,E,0 A 0,1 B 0,0 D 1,1 C 1,1 E 1,T,中序序列：BCAED,带头结点的中序线索二叉树,0,1,头结点：,lt=0,lc,指向根结点,rt=1,rc指向遍历序列中最后一个结点,遍历序列中第一个结点的lc域和最后,一个结点的rc域都指向头结点,A,B,D,C,E,T,中序序列：BCAED,中序线索二叉树,0,0,0,0,1,1,1,1,1,1,中序线索化算法,INTHREAD(bithptr*p),if(p!=NULL),INTHREAD(p-lchild);,if(p-lchild=NULL)p-ltag1;,if(p-rchild=NULL)p-rtag1;,if(pre!=NULL),if(pre-rtag=1)pre-rchildp;,if(pre-ltag=1)pre-lchildpre;,prep;INTHREAD(p-rchild);,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,t,0,1,pr,p,i,P-A,A,B,D,C,E,bt,0,0,0,0,0,0,0,0,0,0,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,p,i,P-A,P-B,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-A,P-B,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,P-A,输出:,B,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,0,0,0,0,0,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,输出:,B,i,P-A,P-C,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-A,P-C,输出:,B,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,P-A,输出:,B C,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,0,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P=NULL,i,P-A,输出:,B C,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,pr,P,i,输出:,B C A,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,0,0,1,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A,pr,P-D,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A,pr,P-D,P-E,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P=NULL,i,输出:,B C A,pr,P-D,P-E,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A E,pr,P-D,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,0,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P=NULL,i,输出:,B C A E,pr,P-D,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P,i,输出:,B C A E D,pr,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,0,1,1,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,A,B,D,C,E,bt,t,0,1,P=NULL,i,输出:,B C A E D,pr,bnode*zxxsh(bnode*bt),bnode*p,*pr,*sM,*t;,int i=0;,t=(bnode*)malloc(sizeof(bnode);,t-lt=0;t-rt=1;t-rc=t;,if(bt=NULL)t-lc=t;,else,t-lc=bt;pr=t;p=bt;,do,while(p!=NULL),si+=p;p=p-lc;,if(i0),p=s-i;,printf(%c ,p-data);,if(p-lc=NULL),p-lt=1;p-lc=pr;,if(pr-rc=NULL),pr-rt=1;pr-rc=p;,pr=p;p=p-rc;,while(i0|p!=NULL);,pr-rc=t;pr-rt=1;t-rc=pr;,return(t);,0,0,0,0,1,0,1,1,1,1,1,算法,按中序线索化二叉树,Ch5_20.c,A,B,C,D,E,输出:B C A E D,A,B,D,C,E,t,0 1,1,1,1,1,1,1,0,0,0,0,算法,按中序线索化二叉树,遍历中序线索二叉树,Ch5_20.c,在中序线索二叉树中找结点后继的方法：,（1）若rt=1,则rc域直接指向其后继,（2）若rt=0,则结点的后继应是其右子树的左链尾（lt=1)的结点,在中序线索二叉树中找结点前驱的方法：,（1）若lt=1,则lc域直接指向其前驱,（2）若lt=0,则结点的前驱应是其左子树的右链尾（rt=1)的结点,A,B,C,D,E,0 A 0,1 B 0,0 D 1,1 C 1,1 E 1,T,中序序列：BCAED,带头结点的中序线索二叉树,0 1,哈夫曼树(,Huffman),带权路径长度最短的树,定义,路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的,路径长度：路径上的分支数,树的路径长度：从树根到每一个结点的路径长度之和,树的带权路径长度：树中所有带权结点的路径长度之和,Huffman,树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫,具有不同带权路径长度的扩充二叉树,霍夫曼树,带权路径长度达到最小的扩充二叉树即为霍夫曼树。在霍夫曼树中，权值大的结点离根最近。,构造,Huffman,树的方法,Huffman,算法,构造,Huffman,树步骤,根据给定的,n,个权值,w1,w2,wn,，,构造,n,棵只有根结点的二叉树，令起权值为,wj,在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和,在森林中删除这两棵树，同时将新得到的二叉树加入森林中,重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树,例,a,7,b,5,c