課程資源-數(shù)據(jù)結構與算法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的結點數(shù)是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*利用先序、中序字符串的有關串的定義、術語、基本字符串的類部分成員函數(shù)的實利用前序、中序序列建立字符串（簡稱串）的定義以及一些*串：是n（n>=0）個字符的一個有限序列，開頭結 引號“”起來例如B=structure（B為串名*串的長度：串中所包含的字符個數(shù)n（不包括分界符‘“’，也不括串的結束符*空串：長度為0的串。或者說只包含串結束符‘\0’的注意\0等于\0空串不等于空*子串：串中任一連續(xù)子序的子pk”不是B的子兩個串的連接（并置取子求一個子串在串中第一次出現(xiàn)的位置等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*}部分成員函數(shù)的實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每棵樹轉(zhuǎn)為二ABCABCDEFGHIKJ把每棵二叉樹根用右鏈AABFCGHDIERJBinary AABFCGHDIERJ4.8樹的遍歷：深度優(yōu)先遍歷，廣度優(yōu)先遍深度優(yōu)先遍先序次序遍歷（先序樹的根 按先序遍歷根的第一 ，第二 ……等后序次序遍歷（后序 A先根：ABEFCGKLDHIJM 對應的二叉樹的先序

后根：EFBKLGCHIMJDA對應的二叉樹的中序一廣度優(yōu)先遍A

4.8D 分 森林的遍深度優(yōu)先遍*先根次序遍F的第一棵樹的按先根遍歷第一棵樹 森按先根遍歷其它樹組成的*中根次序遍按中根遍歷第一棵樹 森F的第一棵樹的按中根遍歷其它樹組成的*后根次序遍按后根遍歷第一棵樹 森按后根遍歷其它樹組成的F的第一棵樹的

二叉樹的先二叉樹的中二叉樹的后K 中根：EFBAIJHKA J后序廣度優(yōu)先遍歷（層次遍歷

ThreadThreadTreeleftThread andrightThreadThreadTreen個結點的二叉樹有2n個鏈域其中真正有用的是n1個，其它n1個都是空前驅(qū)或后繼等運算。

ThreadAABCDEFGHJThread

Inorder:^J^JAABCBC^DEF^DEFGHGH機內(nèi)如一個結點增加兩個標記leftThread=rightThread=

leftchild指向 leftchild指向前驅(qū)（某線性序列 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;}構造中序線索對已存在的一棵二叉樹建立中序線索右空域的前驅(qū)、后繼指針。所以除了流動指針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：根到每個外結點（增長樹的葉子）內(nèi)通路長度（內(nèi)路徑）I：根到每個內(nèi)結點（非葉子）的路徑長度的總和（邊結點的帶權路徑長一個結點的權值與結點的路徑乘積帶權的外路徑長葉結點的帶權帶權的內(nèi)路徑長度：各非葉結點的帶權路徑長樹給出m個實數(shù)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經(jīng)由小到大排序，求解這問題例子：23571113171923293137注意:當內(nèi)結點的權值與外結點的權值相等的情況下，內(nèi)結點應外結點之后。除了保證Wili最小外，還保證maxIj,Ij也有最小例如:789編 樹在數(shù)據(jù)編碼中一種應用。具體的講用于通信的二進制編碼中。設一電文出現(xiàn)的字符為D={M，S，T，A，Q，個字符出現(xiàn)的頻率為W={10，29，4，8，15，7}何對上面的諸字符進行二進制編碼，使得該電文的總長度最短為了譯碼，任一字符的編碼不應是另一字符的編碼的算法：利用Huffman算法，把{10，29，4，8，15，7}作為外部 的邊標上0，右 01 001AM1748編碼

已知二進制編碼，方法是從根結點開始確定一條到達葉結點的路1001100101

111

11010 MS S2009年統(tǒng)考題(單項選擇

Chapter給定二叉樹如下圖所示設N代表二叉樹的根,L代表二叉樹,R代表根結點的 .若遍歷后的結點序列為3,1,7,624則其遍歷方A. B. C. D.1 2009年統(tǒng)考題(單項選擇

Chapter,全二叉樹的結點個數(shù)最A. C. D.將森林轉(zhuǎn)換為對應的二叉樹,若在二叉樹中結點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的葉節(jié)點個數(shù)是 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分別找出滿足以下條件的所有二叉樹二叉樹的前序序列與中序序列相二叉樹的中序序列與后序序列相二叉樹的前序序列與后序若用二叉鏈表作為二叉樹 表示，試對以下問題編寫遞歸算法統(tǒng)計二叉樹中葉結點的個數(shù)以二叉樹為參數(shù)，交換每個結點的 和Chapter已知一棵二叉樹的先序遍列結果是中序遍列結果是試畫出這棵二叉樹示。設每個操作符有一個或兩個操給定權值{15,03,14,02,06,09,16,17},構造相應 樹，計算它的帶權外路徑長c1c2c3c4c5c6c7c8這八個字母的出現(xiàn)頻率{5,25,3,6,10,11,36,4,}為這八個字母設計不等長的Huffman編碼,給出該電文的總碼數(shù)實習題建立一棵二叉樹，并輸出前序、中序、后序遍歷結果**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(chǎn)?,表尾為((5,3,D=(B,C,E=(B,F=(4,F)遞歸的廣義表的性質(zhì)(特點有序有長度,有深可遞歸,如上面例可共享,如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)遞歸函數(shù)的內(nèi)部調(diào) 私有函求廣義表的深

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

intGenList::depth({return}私有函數(shù)int if