数据结构.ppt

单击此处编辑母版标题样式,.,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 树和二叉树,定义：,树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：,（1）有且仅有一个特定的称为根(Root)的结点；,（2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。,6.1 树的定义和基本术语,.,树定义,T,1,T,2,T,3,A,C,B,G,F,E,H,I,J,D,M,K,L,A,.,ADT Tree,数据对象 D：,D是具有相同特性的数据元素的集合。,数据关系 R若D为空集，则称为空树；,若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系：,（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；,（2）若D-root,则存在D-root的一个划分D1，D2Dm（m0）,对任意j,k(1,j,k,m)有DJ,DK=,且对任意的i(1,i,m),存在唯一数据元素xi,Di,H;,（3）对应于D-root的划分，H-,有唯一的一个划分H1,H2,Hm(m0),对任意j,k(1,j,k,m)有Hj,Hk=,且对任意i(1,i,m)，Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。,基本操作P：,ADT Tree,.,基本操作：,查 找,插 入,删 除,.,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),/按定义构造树,AssignT,cur_e,value),/给当前结点赋值,InsertChild(&T,&p,i,c),/将以c为根的树插入为结点p的第i棵子树,.,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i),/删除结点p的第i棵子树,.,树的其它表示方式,凹入表示,嵌套集合,广义表,.,基本术语,1.结点,指树中的一个数据元素，一般用一个字母表示。,2.度,一个结点包含子树的数目，称为该结点的度。,3.树叶（叶子）,度为0的结点，称为叶子结点或树叶，也叫,终端结点。4.孩子结点,若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。,5.双亲结点,若结点X有子女Y，则X为Y的双亲结点。,.,6.祖先结点,从根结点到该结点所经过分支上的所有结点为该结点的祖先。,7.子孙结点,某一结点的子女及子女的子女都为该结点子孙。,8.兄弟结点,具有同一个双亲的结点，称为兄弟结点。,9.分支结点,除叶子结点外的所有结点，为分枝结点，也叫非终端结点。,10层数,根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,.,11.树的高度（深度）,树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。,12.树的度,树中结点度的最大值称为树的度。,13.有序树,若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。,14.无序树,若一棵树中所有子树的次序无关紧要，则称为无序树。,15森林（树林）,若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,.,线性结构,树型结构,第一个数据元素,(无前驱),根结点,(无前驱),最后一个数据元素,(无后继),多个叶子结点,(无后继),其它数据元素,(一个前驱、,一个后继),其它数据元素,(一个前驱、,多个后继),对比树型结构和线性结构的结构特点,.,二叉树或为空树，或是由一个根结点加上两棵分别称为,左子树,和,右子树,的、,互不交的,二叉树组成A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2 二叉树,6.2.1 二叉树的定义,.,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,.,二叉树的抽象数据类型,ADT BinaryTree,数据对象D：,D是具有相同特性的数据元素的集合。,数据关系R：,若D=,，则R=,，称二叉树为空二叉树；,若D,，则R=H，H是如下二元关系：,（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；,（2）若D-root,则存在D-root=D,1,D,r,且,D,1,D,r,；,（3）若D,1,则D,1,中存在唯一的元素x,1,H,且存在D,1,上的关系H,1,H；若D,r,则D,r,中存在唯一的元素x,r,H,且存在D,r,上的关系H,r,H；H=,H,1,H,r,;,（4）（D,1,，H,1,）是一棵符合本定义的二叉树，称为根的左子树，（D,r,，H,r,）是一棵符合本定义的二叉树，称为根的右子树。,基本操作：,ADT BinaryTree,.,性质 1：,在二叉树的第,i,层上至多有,2,i-1,个结点。(i,1),用归纳法证明：,归纳基：,归纳假设：,归纳证明：,i,=,1,层时，只有一个根结点：,2,i-1,=,2,0,=,1,；,假设对 j，1=ji，命题成立2,j-1证明j=i时命题也成立，,由归纳假设，第i-1层至多有2,i-2,个结点，,二叉树上每个结点至多有两棵子树，,故第,i层时,结点数最多=,2,i-2,2,=,2,i-1,。,6.2.2 二叉树的性质,.,性质 2：,深度为,k,的二叉树上至多含,2,k,-1,个结点（k,1）。,证明：,基于上一条性质，深度为,k,的二叉树上的结点数至多为,2,0,+2,1,+,+2,k-1,=2,k,-1,。,.,性质 3：,对任何一棵二叉树，若它含有,n,0,个叶子结点、,n,2,个度为,2,的结点，则必存在关系式：,n,0,=n,2,+1,。,证明：,设,二叉树上结点总数,n=n,0,+n,1,+n2,又,二叉树上分支总数,b=n,1,+2n,2,而,b=n-1=n,0,+n,1,+n,2,-1,由此，,n,0,=n,2,+1,。,.,两类,特殊,的二叉树：,满二叉树,：,指的是深度为,k,且含有,2,k,-1,个结点的二叉树。,完全二叉树,：,树中所含的,n,个结点和满二叉树中,编号为,1,至,n,的结点,一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,.,性质 4：,具有,n,个结点的完全二叉树的,深度,为,log,2,n,+1,。,证明：,设,完全二叉树的深度为,k,则根据第二条性质得,2,k-1,n,2k,即,k-1 log,2,n,n,，则该结点无左孩子，否则，编号为,2i,的结点为其,左孩子,结点；(3)若,2i+1n,，则该结点无右孩子结点，否则，编号为,2i+1,的结点为其,右孩子,结点。,.,示意图,2i,2i+1,i,2i+2,2i+3,i+1,i/2,j层,j+1层,2,j-1,2,j,2,j,+1,.,示意图,2i+2,2i+3,i+1,2i,2i+1,i,.,.,2,i,2i+1,i,2i+2,2i+,3,i+1,LCHILD(i),LCHILD(i+1),RCHILD(i),RCHILD(i+1),.,6.2.3 二叉树的存储结构,二、二叉树的链式存储表示,一、二叉树的顺序存储表示,.,一、二叉树的顺序存储结构,整个二叉树可以按照从上到下，从左到右的顺序排序，做标号；,对于满/完全二叉树，可以从根结点开始按序号存放,对于一般的二叉树，可以参照满二叉树的编码方法进行编码，位置空的结点空置。,.,#define MAX_TREE_SIZE 100,/二叉树的最大结点数,typedef TElemType SqBiTreeMAX_TREE_SIZE;,/0号单元存储根结点,SqBiTree bt;,二叉树的顺序存储表示,.,1,2,3,4,5,6,7,8,9,10,1,8,9,10,4,5,2,6,7,3,完全二叉树,.,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,.,A,B,C,非完全二叉树,A,B,C,A B C,.,二、二叉树的链式存储表示,1.二叉链表,2三叉链表,3线索链表,.,A,D,E,B,C,F,root,l,child data,r,child,1.二叉链表,data,lchild rchild,.,typedef struct,BiTNode,/,结点结构,TElemType data;,struct,BiTNode,*l,child,*r,child;,/左右孩子指针,BiTNode,*,BiTree;,l,child data,r,child,结点结构:,C,语言的类型描述如下:,.,2,三叉链表,A,B,C,D,E,F,lchild,data,rchild,parent,data,lchild rchild,parent,.,typedef struct,TriTNode,/,结点结构,TElemType data;,struct,TriTNode,*l,child,*r,child;,/,左右孩子指针,struct,TriTNode,*parent;/,双亲指针,TriTNode,*,TriTree;,lchild data parent rchild,结点结构:,C,语言的类型描述如下:,.,假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有：,DLR、LDR、LRD、,DRL、RDL、RLD,六种遍历方案。,6.3遍历二叉树和线索二叉树,6.3.1 遍历二叉树,.,前序遍历二叉树,中序遍历二叉树,后序遍历二叉树,访问根结点；,前序遍历左子树；,前序遍历右子树；,中序遍历左子树；,访问根结点；,中序遍历右子树；,后序遍历左子树；,后序遍历右子树；,访问根结点；,.,遍历图例,A,C,F,E,D,B,中序序列为：,前序序列为：,后序序列为：,DBEACF,ABDECF,DEBFCA,.,二叉树表达式,(a+b*(c-d)-e/f),遍历此二叉树,其先序序列为：,-+a*b-cd/ef,按中序遍历,其中序序列为：,a+b*c-d-e/f,按后序遍历,其后序序列为：,abcd-*+ef/-,*,a,/,b,-,d,c,f,e,.,图例,a,b,*,c,-,b,a,*,-,c,a,b,*,c,-,a,b,c,a,c,b,-,-*abc,a*b-c,ab*c-,.,先（根）序的遍历算法,的递归描述,void PreorderTraverse(BiTree T,status(*visit)(TElemType&e),/先序遍历二叉树,if(T),if(,Visit(T-data),),if(,PreOrderTraverse(T-lchild，Visit),),if(,PreOrderTraverse(T-rchild，Visit),),return OK;,return ERROR；,else return OK；,p129,.,Status InOrderTraverse(BiTreeT，Status(*Visit)(TElemType e),InitStack(S)；Push(S，T)；/根指针进栈,while(!StackEmpty(S),while(GetTop(S，p)&p)Push(S，p-lchild)；Pop(S，p)；/空指针退栈 if(!StackEmpty(s)/访问结点，向右Pop(S，p)；if(!,Visit(p-data),)return ERROR；Push(S，p-rchild)；,/Whilereturn OK；,p130,a,c,b,-,.,Status InOrderTraverse(BiTreeT，Status(*Visit)(TElemType e),InitStack(S)；p=T；while(p|!StackEmpty(S)if(p)Push(S，p)；p=p-lchild；else,Pop(S，p)；if(!Visit(p-data)return ERROR；p=p-rchild；/else/Whilereturn OK；,P131了解,.,Status CreateBiTree(BiTree,&T,),scanf(,if(ch=),T,=NULL;,else,if(!(,T,=(BiTNode*)malloc(sizeof(BiTNode),exit(OVERFLOW);,T,-data=ch;/生成根结点,CreateBiTree(,T-lchild,);/构造左子树,CreateBiTree(,T-rchild,);/构造右子树,return OK;,/CreateBiTree,建立二叉树,p131,.,A ,ABC DE ,.,6.3.2 线索二叉树,n个结点的二叉链表中含有n+1个空指针域，,可以利用这些空指针域来存放某结点的前驱和后继的信息。这些附加的指针称为,“线索”,，加上了线索的二叉链表称为,线索链表,，加上线索的二叉树就是,线索二叉树,（Threaded Binary Tree）,。将二叉树变为线索二叉树的过程称为,线索化,。,lchild,ltag,data,rtag,rchild,ltag=,rtag=,指向结点前驱,指向结点的左孩子,lchild,lchild,:,1,:,0,指向结点后继,指向结点的右孩子,rchild,rchild,:,1,:,0,.,中序线索二叉树,NULL,A,C,F,E,D,B,NULL,A,0,0,E,1,1,C,0,1,D,1,1,F,1,1,B,0,0,NULL,NULL,.,类型定义,typedef struct BinhrNode,TelemType data;,struct BinhrNode,*,lchild,*,rchild;,左、右孩子指针,int,ltag,rtag;,BinhrNode,，,*,BinhrTree,.,对中序线索化链表的遍历算法,中序遍历的第一个结点？,在中序线索化链表中结点的后继？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,.,.,Status InorderTraverse_Thr(BiThrTree T,status(*visit)(TElemType),P=Tlchild;,whilep!=T,),while(p LTag=Link)p=p lchild;,if(!visit(p data)return error;,while(p RTag =Thread&,p,rchild!=T,),p=p rchild;Visit(p data);,p=prchild;,return OK;,P134,.,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,如何建立线索链表？,.,Status InorderThreading(BiThrTree&Thrt,BiThrTree T),if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode),exit(OVERFLOW);,Thrt LTag =Link;Thrt RTag =Thread;,Thrt rchild=Thrt;,if(!T)Thrt lchild=Thrt;,else,Thrt lchild=T;pre=Thrt;,InThrTreading(T);,pre rchild=Thrt;pre RTag =Thread;,Thrt rchild=pre;,return OK;,/InorderThreading,P134,.,Void InThreadingBiThrTree p),if(p),InThreading(p lchild);,if(!p lchild)p LTag =Thread;p lchild=pre;,if(!pre rchild),pre rchild)pre RTag =Thread;pre rchild=p;,pre=p;,InThreading(p rchild);,P135,.,6.6 树和森林,树的三种存储结构,一、双亲表示法,二、孩子表示法,三、树的二叉链表(孩子-兄弟）,存储表示法,.,A,B,C,D,E,F,G,0,A,-1,1,B,0,2,C,0,3,D,0,4,E,2,5,F,2,6,G,5,r=0,n7,data parent,一、双亲表示法,.,typedef struct,PTNode,Elem data;,int,parent;/双亲位置域,PTNode;,data parent,#define,MAX_TREE_SIZE 100,结点结构:,C,语言的类型描述:,.,typedef struct,PTNode,nodesMAX_TREE_SIZE;,int r,n;/根结点的位置和结点个数,PTree;,树结构:,.,二、孩子表示法,.,.,typedef struct CTNode,int child;,struct CTNode*next;,*,ChildPtr,;,孩子结点结构:,child next,C,语言的类型描述:,.,typedef struct,Elem data;,ChildPtr,firstchild;/孩子链的头指针,CTBox;,data firstchild,树结构:,typedef struct,CTBox,nodesMAX_TREE_SIZE;,int n,r;/结点数和根结点的位置,CTree;,.,A,B,C,D,E,F,G,0,A,1,B,2,C,3,D,4,E,5,F,6,G,r=0,n=7,data firstchild,1 2 3,4 5,6,-1,0,0,0,2,2,5,.,A,B,C,D,E,F,G,A,B,C,E D,F,G,root,A,B,C,E D,F,G,三、孩子-兄弟表示法(树的二叉链表表示法),.,typedef struct,CSNode,Elem data;,struct,CSNode,*,firstchild,*,nextsibling;,CSNode,*,CSTree;,C,语言的类型描述:,结点结构:,firstchild data nextsibling,.,6.4.2 森林和二叉树的转换,.,若,树采用孩子兄弟表示法,，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。因此，在使用该存储结构下，树可以转化为二叉树。,树和二叉树转化,步骤,（,1,）,连线,：,在所有的兄弟结点之间加一条连线。,（,2,）,切线,：,对于每个结点，除了保留与其最左孩子的连线外，去掉该结点与其它孩子之间的连线。,（,3,）,旋转,：,将按（,1,）、（,2,）的方法形成的二叉树，沿顺时针方向旋转,45,0,就可以得到一棵形式上更为清楚的二叉树。,.,应当注意的是，,和树对应的二叉树，其左、右子树的概念,已改变为：,左是孩子，右是兄弟。,.,树和二叉树转化例,F,G,H,A,B,C,E,D,F,G,H,A,B,C,E,D,F,G,H,A,B,C,E,D,F,H,A,B,G,C,E,D,.,森林到二叉树的转换,若,树采用孩子兄弟表示法,，二叉树采用,二叉链表,表示，则：,任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树(因此一棵二叉树，不一定保证能转换为一棵树),若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点,，则这两棵树可以转换为一棵二叉树。,依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则,.,转换示例,A,B,C,D,F,G,H,I,E,A,B,C,D,F,G,H,I,E,C,A,B,D,F,G,H,I,E,.,二叉树到森林的转换例,I,A,B,D,F,G,H,K,C,E,J,I,A,B,D,J,H,C,E,F,G,K,.,6.4.3 树和森林的遍历,一、树的遍历,二、森林的遍历,.,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,.,A,B C D,E F G,H,I J K,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,.,B C D,E F G,H,I J K,1,森林中第一棵树的根结点；,2,森林中第一棵树的子树森林；,3,森林中其它树构成的森林。,森林由三部分构成：,.,1.先序遍历,森林的遍历,若森林不空，则,访问,森林中第一棵树的根结点；,先序遍历,森林中第一棵树的子树森林；,先序遍历,森林中(除第一棵树之外)其余树构成的森林。,即：,依次从左至右,对森林中的每一棵,树,进行,先根遍历,。,.,中序遍历,若森林不空，则,中序遍历,森林中第一棵树的子树森林；,访问,森林中第一棵树的根结点；,中序遍历,森林中(除第一棵树之外)其余树构成的森林。,.,6.6 哈夫曼树及其应用,最优树的定义,如何构造最优树,前缀编码,.,一、最优树的定义,树的路径长度,定义为：,树中每个结点的路径长度之和。,结点的路径长度,定义为：,从根结点到该结点的路径上,分支的数目。,.,结点的带权的路径长度,：该结点到根结点之间的路程长度与该结点上权的乘积,树的带权路径长度,定义为：,树中所有叶子结点的带权路径长度之和,WPL(T)=,w,k,l,k,(对所有叶子结点)。,由n个带权值的叶子结点构成的二叉树中，,WPL,最小的二叉树称为,最优二叉树，或Huffman树,.,2,7 9,7,5,4,9,2,WPL(T)=7,2+52+23+43+92 =60,WPL(T)=7,4+94+53+42+21 =89,5,4,.,if(a60)b=“bad”;,else if(a70)b=“pass”;,else if(a80)b=“general”;,else,分数,0-59,60-69,70-79,80-89,90-100,比例数,0.05,0.15,0.40,0.30,0.10,1*0.05+2*0.15+3*0.4+4*0.3+4*0.1=3.15,10000个数据需比较31500次,.,分数,0-59,60-69,70-79,80-89,90-100,比例数,0.05,0.15,0.40,0.30,0.10,2*0.1+2*0.3+2*0.4+3*0.15+3*0.05=2.2,.,例如:已知权值,W=5,6,2,9,7,9,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,二、如何构造最优树,.,6,713,9,5,2,7,9,5,2,7,16,6,7,13,29,.,d,c,b,a,9,6,5,3,b,a,9,6,3,5,8,a,9,6,14,3,5,8,9,6,23,14,5,3,8,a,b,c,d,c,b,d,哈夫曼树,.,三、哈夫曼编码,数据通讯中，经常采用,0,、,1,序列来表示不同的字符。在发送端需要将待发送的字符转化成二进制的,0,、,1,序列（编码），在接受端又要把接受的,0,、,1,序列转化成对应的字符序列（译码）。,字符串：“ABACCDA”,每个字符采用2比特表示，共14比特；,考虑到出现频率，A：0,C：1,B：00,D：01，则编码为：“000011010”，共9比特。,译码有困难：“0000”有多种译法：ABA,AAAA,BB,BAA,.,指的是，,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,。,前缀编码,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种,最优前缀编码,，即使所传电文的总长度最短。,.,A,C,B,D,E,F,16,0,0,0,0,1,1,1,3,6,4,1,2,5,7,3,6,9,12,G,0,1,1,28,0,1,A：100,B：11,C：001,D：1011,E：1010,F：000,G：01,1、利用二叉树编码得到的是二进制前缀编码？,2、得到,电文总长,最短？,.,哈夫曼编码,设有n种字符，在一个电文中，第i种字符出现的次数为W,i,编码长度为l,i,，,使,L,最小，可以看作是已知,n,个结点的权,wi,，,求一棵,Huffman,树的问题。由此得到的二进制编码，称为,Huffman,编码。,一段电文的总长度为：,L=w,1,l,1,+w,2,l,2,+w,n,l,n,=w,i,l,i,.,哈夫曼编码,Huffman树中，有没有度为的结点？,有n个叶结点的Huffman树，有多少个结点？,一定没有（严格或正则二叉树）,一定有,2n-1,个结点,.,/赫夫曼树和赫夫曼编码的存储表示typedef struct unsigned int weight；unsigned int parent，lchild，rchild；HTNode，*HuffmanTree；/动态分配数组存储赫夫曼树typedef chat*HuffmanCode；/动态分配数组存储赫夫曼编码表,.,void HuffmanCoding(HuffmanTree /0号单元未用for(p+=HT，i=1；i=n；+i，+p，+w)*p=*w,0,0,0 for(；i=m；+i，+p)*p=0，0，0，0；for(i=n+1；i=m；+i)Select(HT，i-1，s1，s2)；HTs1.parent=i；HTs2.parent=i；HTi.lchild=s1；HTi.rchild=s2；HTi.veiqht=HTs1.weight+HTs2.weight；,/从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间 cdn1=“0”;/编码结束符for(i=1;i=n;+i)/逐个字符求赫大曼编码start=n1;/编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f，f=HTf.parent)/从叶子到根逆向求编码if(HTf.1child=c)cd-start=“0”;else cd-start=“1”;HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(HCi，,free(cd);,.,已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计赫夫曼编码。,w,=(5，29，7，8，14，23，3，11),n=8，则m=15,计算带权路径长度WPL值？,.,课外作业,已知一棵二叉树的中序遍历序列为DBEHAFCIG，后序遍历序列为DHEBFIGCA，画出该二叉树，并写出该二叉树的前序序列,.,