课程资源-数据结构与算法chapter4.0tree

Chapter4TwokindsofdataLinear:list,stack,queue,Non-linear:tree,4.1AtreeTisacollectionofThecollectioncanbeotherwise,atreeconsistsofadistinguishednoder,calledtheroot,andzeroormorenonempty(sub)treesT1,T2,……,Tk Degreeofanelememts(nodes):thenumberchildrenitDegreeofatree: umofitsLeaf:elementwhosedegreeis0Branch:elementwhosedegreeisnot0thelevelofrootis0 thelevelofanelement=thelevelofitsDepthofa umlevelofitsBinaryDefinition:Abinarytreetisafinite(possiblyempty)collectionofelements.WhenthebinarytreeisnotIthasarootTheremainingelements(ifany)arepartitionedintotwobinarytrees,whicharecalledtheleftandrightsubtreesoft.BinaryTheessentialdifferencesbetweenabinarytreeandatreeare:Eachelementinabinarytreehasexactlysubtrees(oneorbothofthesesubtreesmaybeEachelementinatreecanhaveanynumberofThesubtreesofeachelementinabinarytreeareThatis,wedistinguishbetweentheleftandtheThesubtreesinatreeareBinaryExampleofabinary++*/abcdPropertiesofbinaryProperty1.Thedrawingofeverybinarytreewithnelements(n>0)hasexactlyn-1edges.Property2.Thenumberofelementsatleveliisatmost2i(i>=0).PropertiesofbinaryProperty3.Abinarytreeofheighth,h>=0,hasatleasth+1andatmost2h+1–1elementsinofofproperty

PropertiesofbinaryProperty4.Ifnumberofleavesisn0,andthenumberofthe2degreeelementsisn2,thenn0=n2+1. 度为1的结点数是n1个n=n0+n1+n2n 这里B为分支n0+n1+n2=1*n1+2*n2+n0=n2+PropertiesofbinaryProperty5.Theheightofabinarytreethatcontainsn(n>=0)elementisatmostn-1andatleastproof:Sincetheremustbeatleastoneelementateachlevel,theheightcannotexceedn-1.Fromproperty3,weknown<=2h+1-1,so,h>=log2(n+1)-1,sincehisaninteger,wegetPropertiesofbinaryDefinitionofafullbinarytreeAbinarytreeofheighththatcontainsexactly2h+1-1elementsiscalledafullbinarytree.PropertiesofbinaryDefinitionofacompletebinarySupposewenumbertheelementsinafullbinarytreeofheighthusingthenumber1throughWebeganatlevel0andgodowntolevelh.WithinlevelstheelementsarenumberedlefttoSupposewedeletethekelementsnumbered2h+1-i,1<=i<=k,theresultingbinarytreeiscalledacompletebinarytree.65Propertiesofbinary653Exampleofcompletebinary3123123412412PropertiesofbinaryProperty6.Leti,0<=i<=n-1,bethenumberassignedtoelementofacompletebinarytree.Thefollowingareifi=0,thenthiselementistherootofthebinaryifi>0,thentheparentofthiselementhasbeenassignedthenumber(i-1)/2if2*i+1>=n,thenthiselementhasnoleftchild.leftchildhasbeenassignedthenumber4.3Propertiesofbinaryif2*i+2>=n,thenthiselementhasnorightchild,Otherwiseitsrightchildhasbeenassignedthenumber4.4RepresentationofbinaryFormula-BasedRepresentation(arrayThebinarytreetoberepresentedisregardedasacompletebinarytreewithsomemissingelements.RepresentationofbinaryExampleofacompletebinarytree(array RepresentationofbinaryExampleofacommonbinarytree(array

910113123126 RepresentationofbinaryLinkedrepresentation(alsocalledL-RlinkedThenode Representationofbinary ABCDABCDEFGBDF^

^C^^^C^^E^^G^RepresentationofbinaryA1-A1-B23C--D45E-6F--G--01234564.4RepresentationofbinaryNodeclassforlinkedbinarytreesclassBianryNode{BinaryNode(Objecte){element=e;Left=Right=0;}BinaryNode(Objecte,BinaryNodel,BinaryNoder){element=e;Left=l;Right=r;ObjectBinaryNodeleft; //leftsubtreeBinaryNoderight; //rightsubtree4.5Commonbinarytree datatypebinaryMakeTree(root,left,BreakTree(root,left,CommonbinarytreeTheClassBinarytreetemplate<classT>class{bool{returnboolRoot(T&voidMakeTree(constT&BinaryTree<T>&leftch,BinaryTree<T>&CommonbinarytreevoidBreakTree(T&data,BinaryTree<T>&leftch,BinaryTree<T>&rightch);void{PreOrder(visit,void{InOrder(visit,voidPostOrder{PostOrder(visit,root);}voidLevelOrder(void(*visit)(BinaryNode<T>CommonbinarytreeBinaryNode<T>*voidPreOrder(void(*visit)(BinaryNode<T>voidInOrder(void(*visit)(BinaryNode<T>voidPostOrder(void(*visit)(BinaryNode<T>CommonbinarytreeInthisclass,weemployalinkedrepresentationforbinarytrees.Thefunctionvisitisusedasparametertothetraversalmethods,sothatdifferentoperationscanbeimplementedeasily4.5CommonbinarytreeImplementationofsomememberfunctionsTemplate<classT>voidBinaryTree<T>::MakeTree(constT&data,BinaryTree<T>&leftch, {root=newBinaryNode<T>(data,}4.5Commonbinarytreetemplate<classvoidBinaryTree<T>::BreakTree(T&data,BinaryTree<T>&leftch,BinaryTree<T>&rightch){if(!root)throwBadInput();//treedata=root.element;leftch.root=root.Left;rightch.root=root.Right;deleteroot;}4.5CommonbinarytreeApplicationofclassBinaryTree(Create#include“binary.h”int template<classvoidvoid{}4.6BinaryTreeEachelementisvisitedexactlyV-----表 一个结L------表 V的R------表 V的

LVRLRVVRLRVLLevel4.6BinaryTreeExampleofbinarytreeABCDEABCDEFGHILevelorder:4.6BinaryTreePreorder{//preordertraversalof*t. }}BinaryTreeInorder{if(t){}}BinaryTreePostordertraversal{}}4.6BinaryTreeInorderBinaryTreeLevelitisanon-recursivefunctionandaqueueisABABCDEFGHIIHGFEDCBABinaryTreeLeveltemplate<classvoidLevelOrder(BinaryNode<T>*{LinkedQueue<BinaryNode<T>*> //visitif(t→Left)Q.Add(t→Left);}}Inorder,Postordernon-recursiveInordernon-recursiveABABCDEFGHIInordernon-recursivevoidInorder(BinaryNode<T>*{Stack<BinaryNode<T>*>BinaryNode<T>*p=for(;;{1){ p=p->Left;if(!s.IsEmpty({p=s.pop(cout<<p-p=p-}else}}Inorder,Postordernon-recursivePostordernon-recursiveA struct

{BinaryNode<T>*int}Postordernon-recursivevoidPostorder(BinaryNode<T>*{Stack<StkNode<T>>s(10);StkNode<T>Cnode;BinaryNode<T>*p=t;for(;;){1)while{Cnode.ptr=p;p=p->Left;

Cnode.tag=0;}2)Cnode=s.pop( p=while(Cnode.tag== //从 {cout<<p-if(!s.IsEmpty({Cnode=s.pop(); p=Cnode.ptr;}elsereturn;}4)Cnode.tag=1;}

p=p- //从 回建立一棵二叉树的方利用MakeTree函利用先序、中序唯一的构造一棵二叉先序 中序 G 利用二叉树的广义表表示来构造一棵二A(B(D),C(E(,G), G 利用二叉树的后缀表示来构造一棵二叉 建立一棵二叉树的方 利用二叉树的后缀表示来构造一棵二叉树(习题(a+b)* ab+(¬a+b)* a¬b+cd+(-a+b)* da¬b+c*利用先序、中序字符串的有关串的定义、术语、基本字符串的类部分成员函数的实利用前序、中序序列建立字符串（简称串）的定义以及一些*串：是n（n>=0）个字符的一个有限序列，开头结 引号“”起来例如B=structure（B为串名*串的长度：串中所包含的字符个数n（不包括分界符‘“’，也不括串的结束符*空串：长度为0的串。或者说只包含串结束符‘\0’的注意\0等于\0空串不等于空*子串：串中任一连续子序的子pk”不是B的子两个串的连接（并置取子求一个子串在串中第一次出现的位置等Java与C/C++的不Javatr[1]=‖来进行操作。intlength(booleanequals(ObjectobjcharcharAt(intindexStringsubstring(intbeginIndexStringsubstring(intbeginIndex,intendIndexconstintmaxlen=128;classString{String(constString&ob);String(constchar*init);String();~String(){delete[]intLength()const{returnString&operator(intposint //取子intoperator==(constString&ob)returnstrcmp(ch,ob.ch //判别相等否intoperator!=(constString&ob){returnstrcmp(ch,intoperator!()const{returncurlen=String&operator=(constString&ob);//串赋值String&operatorconstString&ob);//并置运算char&operator[](inti);intFind(Stringpat)intchar*}部分成员函数的实TakingString&String::operator()(intpos,int String*temp=new temp->curLen=0;temp-else{if(pos+len-1>=curLen)len=curLen-temp-for(inti=0,j=pos;i<len;i++,temp-temp-}return}Assigning

String&String::operator=(constString{if{delete[]ch=newstrcpy(ch,ob.ch);}\n‖;return*}4.CreateBinaryTreerecursiveinorder:DBAEGCHFIA CreateBinaryTreerecursivealgorithmvoidCreateBT(Stringpres,ins;BinaryNode<Type>*& intStringprestemp,instempif(pres.length()==0)else{t=newt- while(ins.ch[inpos]!=t->element)CreateBT(prestemp,instemp,t->left);prestemp=pres(inpos+1,pres.length()-instemp=ins(inpos+1,pres.length()-}}CreateBinaryTreerecursivealgorithmBinaryTree(stringpre,stringIn createBT(pre,In,root)}main() HBDFAEKCG‖}CreateBinaryTreerecursivealgorithmBinaryNode<Type>*voidCreateBT(Stringpres,ins{int BinaryNode<Type>*Stringprestemp,instempif(pres.length()==0)returnelse temp=newtemp- while(ins.ch[inpos]!=temp->element)instemp=ins(0,inpos-temp->left=CreateBT(prestemp,prestemp=pres(inpos+1,pres.length()-instemp=ins(inpos+1,pres.length()-temp->right=CreateBT(prestemp,instemp);returntemp;}}CreateBinaryTreerecursivealgorithmpublicBinaryTree(stringpre,string{root=createBT(pre,}main({strings1(―ABHFDECKG‖);BinaryTreet1(s1,s2);preorder(t1);Inorder(t1);}如果已知后序与中序,能否唯一构造一棵二叉树呢后序 中序 如果已知先序与后序呢ADTandClassPreOutput():outputthedatafieldsinInOutput():outputthedatafieldsinPostOutput():outputthedatafieldsinLevelOutput():outputthedatafieldsinlevelDelete():deleteabinarytree,freeingupitsHeight():returnthetreeSize():returnthenumberofnodesintheADTandClassTheheightofthetreeisdeterminedas:max{hl,hr}+1template<classintBinaryTree<T>::Height(BinaryNode<T>{if(!t)returninthl=Height(t→Left);if(hl>hr)return++hl;elsereturn++hr;}Binary-TreeRepresentationofa树 方式：三广义表表示abfgabfg0122 —右兄弟表示Takeatreeasabinaryaa

c ijclassTreeNode:Tdata;TreeNode*firstchild,*nextsibling;classTree:TreeNode*root,4.8insertnewnodeintemplate<classT>voidTree<T>::Insertchild(T{TreeNode<T>*newnode=newTreeNode<T>(value);if(current->firstchild==NULL)current->firstchild={TreeNode<T>*p=current-while(p->nextsibling!=NULL)p=p->nextsibling;p->nextsibling=newnode;}}4.8 BinaryFGABCDEHIFGABCDEHIJK每棵树转为二ABCABCDEFGHIKJ把每棵二叉树根用右链AABFCGHDIERJBinary AABFCGHDIERJ4.8树的遍历：深度优先遍历，广度优先遍深度优先遍先序次序遍历（先序树的根 按先序遍历根的第一 ，第二 ……等后序次序遍历（后序 A先根：ABEFCGKLDHIJM 对应的二叉树的先序

后根：EFBKLGCHIMJDA对应的二叉树的中序一广度优先遍A

4.8D 分 森林的遍深度优先遍*先根次序遍F的第一棵树的按先根遍历第一棵树 森按先根遍历其它树组成的*中根次序遍按中根遍历第一棵树 森F的第一棵树的按中根遍历其它树组成的*后根次序遍按后根遍历第一棵树 森按后根遍历其它树组成的F的第一棵树的

二叉树的先二叉树的中二叉树的后K 中根：EFBAIJHKA J后序广度优先遍历（层次遍历

ThreadThreadTreeleftThread andrightThreadThreadTreen个结点的二叉树有2n个链域其中真正有用的是n1个，其它n1个都是空前驱或后继等运算。

ThreadAABCDEFGHJThread

Inorder:^J^JAABCBC^DEF^DEFGHGH机内如一个结点增加两个标记leftThread=rightThread=

leftchild指向 leftchild指向前驱（某线性序列 rightchild指向 rightchild指向后线索化二叉树的 template<classType>class{friendclassintleftThread,rightThread;ThreadNode<Type>*leftchild,*rightchild;Typedata;ThreadNode(constTypeitem):data(item),leftchild(0),rihgtchild(0),leftThread(0),rihgtThread(0){}template<classType>class{//线索二叉树的公共ThreadNode<Type>*root;讨论线索化二叉树的几个按中序遍历中序线遍历算法（以中序为例递归，非递归（需用工作栈）这里前提是中序线索树，所以既不要递归，也不要栈遍历算法*找到中序下的第一个结点*不断找后继如何找后继p指结点没有 则p=p（p

p有（p->rightThread=则(1)p=ptemplate<classThreadNode<Type>*ThreadInorderIterator<Type>::First({while(current->leftThread==0)current=current->leftchild;returncurrent;}template<classThreadNode<Type>*ThreadInorderIterator<Type>::Next({ThreadNode<Type>*p=current-if(current->rightThread=while(p->leftThread==0)p=p-}template<classvoidThreadInorderIterator<Type>::Inorder({ThreadNode<Type>for(p=Frist();p!=NULL;p=Next())cout<<p->data<<endl;}构造中序线索对已存在的一棵二叉树建立中序线索右空域的前驱、后继指针。所以除了流动指针p外还要加一个p例如

F F 即p为pre的中序下的后 若pre的右链为空，则可填ThreadCreateinorderVoidInthread(threadNode<T>*{stack<threadNode<T>*>sThreadNode<T>*p=T;ThreadNode<T>*pre=NULL;for(;;){1.while{s.push(p);p=p->leftchild;2.if(!s.IsEmpty({1)p=if(pre!={if(pre->rightchild=={pre->rightchild=p;pre->rightthread=1;}if(p->leftchild==NULL){p->leftchild=pre;p->leftthread=1;}pre=p;p=p->rightchild}else}4.8树(Huffman增长树的增长对原二叉树中度为1的结点，增加一个空对原二叉树中的树叶，增加两个空树外通路长度（外路径）E：根到每个外结点（增长树的叶子）内通路长度（内路径）I：根到每个内结点（非叶子）的路径长度的总和（边结点的带权路径长一个结点的权值与结点的路径乘积带权的外路径长叶结点的带权带权的内路径长度：各非叶结点的带权路径长树给出m个实数W1，W2，…，Wm（m>=2）作为m个外点的权构造一棵增长树，使得带权mWili最小 为wi的外结点的通路长例子：外结点2，3，4，11则可构423 42323234算法：从m个权值中找出两个最小值W1，W2构wW=W1+W2表通过该w的频度然后对m-1个权值W，W3，W4，…Wm经由小到大排序，求解这问题例子：23571113171923293137注意:当内结点的权值与外结点的权值相等的情况下，内结点应外结点之后。除了保证Wili最小外，还保证maxIj,Ij也有最小例如:789编 树在数据编码中一种应用。具体的讲用于通信的二进制编码中。设一电文出现的字符为D={M，S，T，A，Q，个字符出现的频率为W={10，29，4，8，15，7}何对上面的诸字符进行二进制编码，使得该电文的总长度最短为了译码，任一字符的编码不应是另一字符的编码的算法：利用Huffman算法，把{10，29，4，8，15，7}作为外部 的边标上0，右 01 001AM1748编码

已知二进制编码，方法是从根结点开始确定一条到达叶结点的路1001100101

111

11010 MS S2009年统考题(单项选择

Chapter给定二叉树如下图所示设N代表二叉树的根,L代表二叉树,R代表根结点的 .若遍历后的结点序列为3,1,7,624则其遍历方A. B. C. D.1 2009年统考题(单项选择

Chapter,全二叉树的结点个数最A. C. D.将森林转换为对应的二叉树,若在二叉树中结点u是结点v点的父结点,则在原来的森林中,u和v可能具有的关系父子关 2)兄弟关 3)u的父结点与v的父结点兄弟关A.只有 B.1)和 1)和 1),2)和Chapter2010 考研3、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是 Chapter5、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个为2的结点，10个度为1的结点，则树T的叶节点个数是 6、对n(n大于等于2)个权值均不相同的字符构 树，关于该树的叙中，错误的是A：该树一定是一棵完全二叉 ：树中一定没有度为1的结 树中两个权值最小的结点一定是兄弟结D：树中任一非叶结点的权值一定不小于下一任一结点的权Chapter给出如下各表达式的二叉1）(a+b)/(c--x-((a+b)>(c-d))||a<f&&(x<y||如果一棵树有1个度为1的结点，有2个度为2的结点，……，个度为0分别找出满足以下条件的所有二叉树二叉树的前序序列与中序序列相二叉树的中序序列与后序序列相二叉树的前序序列与后序若用二叉链表作为二叉树 表示，试对以下问题编写递归算法统计二叉树中叶结点的个数以二叉树为参数，交换每个结点的 和Chapter已知一棵二叉树的先序遍列结果是中序遍列结果是试画出这棵二叉树示。设每个操作符有一个或两个操给定权值{15,03,14,02,06,09,16,17},构造相应 树，计算它的带权外路径长c1c2c3c4c5c6c7c8这八个字母的出现频率{5,25,3,6,10,11,36,4,}为这八个字母设计不等长的Huffman编码,给出该电文的总码数实习题建立一棵二叉树，并输出前序、中序、后序遍历结果**General广义表 结广义表的概念

**General*定义为n(n>=0)个表元素a0a1a2,……an-1组成的有限序列,记作:LS=(a0,a1,a2,……an-1)其中每个表元素ai可以是原子,也可以是子表原子:某种类型的对象,在结构上不可分(用小写字母表示).子表:有结构的.(用大写字母表示)*广义表的长度:表中元素的个**General*广义表的表头(head),表尾tail=(a1,a2,……an-*广义表的深度A=(B=(6,

表中所含括号的最大层C=(„a5,3,„x‟))表头为‘a‟,表尾为((5,3,D=(B,C,E=(B,F=(4,F)递归的广义表的性质(特点有序有长度,有深可递归,如上面例可共享,如E中B为E,D所共

表示表元素 2626353DBCAEBDC3DBCAEBDCF3562A52644**GeneralGeneralListshead3)first5)next7)pushsetinfosethead

tail4)info6)nodetype8)addonsetnextsettail**GeneralGeneralLists

L=(3,(utyperef01333013333^00^2 2c00^03^03^03^03^2020**General广义表的#defineHEAD#defineINTGR#defineCH#defineLST3classGenList;{friendclassintGenListNode*union{intintcharcharinfo;GenListNode*hlink;}

**GeneralGenListNode&info(GenListNode*intnodetype(GenListNode*elem){returnelem-voidsetinfo(GenListNode*elem,GenListNode&class{GenListNode*GenListNode*Copy(GenListNode*intdepth(GenListnode*intequal(GenlistNode*s,Genlistnode*voidRemove(GenlistNode*GenList(~GenList(

**GeneralGenListNode&Head();GenListNode*Tail();GenlistNode*First();GenlistNode*Next(GenListNode*voidPush(GenListNode&GenList&Addon(GenList&list,GenListNode&voidsetHead(GenListNode&voidsetNext(GenlistNode*elem1,GenlistNode*voidsetTail(GenList&list);voidCopy(constGenList&l);intdepth();int ist(GenListNode*ls,char*} 2)递归函数的内部调 私有函求广义表的深

LS==(a0a1a2,……an-1),其中ai(0<=I<=n-1)0

intGenList::depth({return}私有函数int if