課程資源-數(shù)據(jù)結(jié)構(gòu)與算法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的結(jié)點(diǎn)數(shù)是n1個(gè)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-----表 一個(gè)結(jié)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òu)造一棵二叉先序 中序 G 利用二叉樹的廣義表表示來構(gòu)造一棵二A(B(D),C(E(,G), G 利用二叉樹的后綴表示來構(gòu)造一棵二叉 建立一棵二叉樹的方 利用二叉樹的后綴表示來構(gòu)造一棵二叉樹(習(xí)題(a+b)* ab+(?a+b)* a?b+cd+(-a+b)* da?b+c*利用先序、中序字符串的有關(guān)串的定義、術(shù)語、基本字符串的類部分成員函數(shù)的實(shí)利用前序、中序序列建立字符串（簡(jiǎn)稱串）的定義以及一些*串：是n（n>=0）個(gè)字符的一個(gè)有限序列，開頭結(jié) 引號(hào)“”起來例如B=structure（B為串名*串的長(zhǎng)度：串中所包含的字符個(gè)數(shù)n（不包括分界符‘“’，也不括串的結(jié)束符*空串：長(zhǎng)度為0的串?；蛘哒f只包含串結(jié)束符‘\0’的注意\0等于\0空串不等于空*子串：串中任一連續(xù)子序的子pk”不是B的子兩個(gè)串的連接（并置取子求一個(gè)子串在串中第一次出現(xiàn)的位置等Java與C/C++的不Javatr[1]=‖來進(jìn)行操作。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);//并置運(yùn)算char&operator[](inti);intFind(Stringpat)intchar*}部分成員函數(shù)的實(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);}如果已知后序與中序,能否唯一構(gòu)造一棵二叉樹呢后序 中序 如果已知先序與后序呢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 對(duì)應(yīng)的二叉樹的先序

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

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

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

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

ThreadAABCDEFGHJThread

Inorder:^J^JAABCBC^DEF^DEFGHGH機(jī)內(nèi)如一個(gè)結(jié)點(diǎn)增加兩個(gè)標(biāo)記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;討論線索化二叉樹的幾個(gè)按中序遍歷中序線遍歷算法（以中序?yàn)槔f歸，非遞歸（需用工作棧）這里前提是中序線索樹，所以既不要遞歸，也不要棧遍歷算法*找到中序下的第一個(gè)結(jié)點(diǎn)*不斷找后繼如何找后繼p指結(jié)點(diǎn)沒有 則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;}構(gòu)造中序線索對(duì)已存在的一棵二叉樹建立中序線索右空域的前驅(qū)、后繼指針。所以除了流動(dòng)指針p外還要加一個(gè)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增長(zhǎng)樹的增長(zhǎng)對(duì)原二叉樹中度為1的結(jié)點(diǎn)，增加一個(gè)空對(duì)原二叉樹中的樹葉，增加兩個(gè)空樹外通路長(zhǎng)度（外路徑）E：根到每個(gè)外結(jié)點(diǎn)（增長(zhǎng)樹的葉子）內(nèi)通路長(zhǎng)度（內(nèi)路徑）I：根到每個(gè)內(nèi)結(jié)點(diǎn)（非葉子）的路徑長(zhǎng)度的總和（邊結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)一個(gè)結(jié)點(diǎn)的權(quán)值與結(jié)點(diǎn)的路徑乘積帶權(quán)的外路徑長(zhǎng)葉結(jié)點(diǎn)的帶權(quán)帶權(quán)的內(nèi)路徑長(zhǎng)度：各非葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)樹給出m個(gè)實(shí)數(shù)W1，W2，…，Wm（m>=2）作為m個(gè)外點(diǎn)的權(quán)構(gòu)造一棵增長(zhǎng)樹，使得帶權(quán)mWili最小 為wi的外結(jié)點(diǎn)的通路長(zhǎng)例子：外結(jié)點(diǎn)2，3，4，11則可構(gòu)423 42323234算法：從m個(gè)權(quán)值中找出兩個(gè)最小值W1，W2構(gòu)wW=W1+W2表通過該w的頻度然后對(duì)m-1個(gè)權(quán)值W，W3，W4，…Wm經(jīng)由小到大排序，求解這問題例子：23571113171923293137注意:當(dāng)內(nèi)結(jié)點(diǎn)的權(quán)值與外結(jié)點(diǎn)的權(quán)值相等的情況下，內(nèi)結(jié)點(diǎn)應(yīng)外結(jié)點(diǎn)之后。除了保證Wili最小外，還保證maxIj,Ij也有最小例如:789編 樹在數(shù)據(jù)編碼中一種應(yīng)用。具體的講用于通信的二進(jìn)制編碼中。設(shè)一電文出現(xiàn)的字符為D={M，S，T，A，Q，個(gè)字符出現(xiàn)的頻率為W={10，29，4，8，15，7}何對(duì)上面的諸字符進(jìn)行二進(jìn)制編碼，使得該電文的總長(zhǎng)度最短為了譯碼，任一字符的編碼不應(yīng)是另一字符的編碼的算法：利用Huffman算法，把{10，29，4，8，15，7}作為外部 的邊標(biāo)上0，右 01 001AM1748編碼

已知二進(jìn)制編碼，方法是從根結(jié)點(diǎn)開始確定一條到達(dá)葉結(jié)點(diǎn)的路1001100101

111

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

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

Chapter,全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最A(yù). C. D.將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹,若在二叉樹中結(jié)點(diǎn)u是結(jié)點(diǎn)v點(diǎn)的父結(jié)點(diǎn),則在原來的森林中,u和v可能具有的關(guān)系父子關(guān) 2)兄弟關(guān) 3)u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)兄弟關(guān)A.只有 B.1)和 1)和 1),2)和Chapter2010 考研3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是 Chapter5、在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個(gè)數(shù)是 6、對(duì)n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu) 樹，關(guān)于該樹的敘中，錯(cuò)誤的是A：該樹一定是一棵完全二叉 ：樹中一定沒有度為1的結(jié) 樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)D：樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)Chapter給出如下各表達(dá)式的二叉1）(a+b)/(c--x-((a+b)>(c-d))||a<f&&(x<y||如果一棵樹有1個(gè)度為1的結(jié)點(diǎn)，有2個(gè)度為2的結(jié)點(diǎn)，……，個(gè)度為0分別找出滿足以下條件的所有二叉樹二叉樹的前序序列與中序序列相二叉樹的中序序列與后序序列相二叉樹的前序序列與后序若用二叉鏈表作為二叉樹 表示，試對(duì)以下問題編寫遞歸算法統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的 和Chapter已知一棵二叉樹的先序遍列結(jié)果是中序遍列結(jié)果是試畫出這棵二叉樹示。設(shè)每個(gè)操作符有一個(gè)或兩個(gè)操給定權(quán)值{15,03,14,02,06,09,16,17},構(gòu)造相應(yīng) 樹，計(jì)算它的帶權(quán)外路徑長(zhǎng)c1c2c3c4c5c6c7c8這八個(gè)字母的出現(xiàn)頻率{5,25,3,6,10,11,36,4,}為這八個(gè)字母設(shè)計(jì)不等長(zhǎng)的Huffman編碼,給出該電文的總碼數(shù)實(shí)習(xí)題建立一棵二叉樹，并輸出前序、中序、后序遍歷結(jié)果**General廣義表 結(jié)廣義表的概念

**General*定義為n(n>=0)個(gè)表元素a0a1a2,……an-1組成的有限序列,記作:LS=(a0,a1,a2,……an-1)其中每個(gè)表元素ai可以是原子,也可以是子表原子:某種類型的對(duì)象,在結(jié)構(gòu)上不可分(用小寫字母表示).子表:有結(jié)構(gòu)的.(用大寫字母表示)*廣義表的長(zhǎng)度:表中元素的個(gè)**General*廣義表的表頭(head),表尾tail=(a1,a2,……an-*廣義表的深度A=(B=(6,

表中所含括號(hào)的最大層C=(?a5,3,?x?))表頭為‘a(chǎn)?,表尾為((5,3,D=(B,C,E=(B,F=(4,F)遞歸的廣義表的性質(zhì)(特點(diǎn)有序有長(zhǎng)度,有深可遞歸,如上面例可共享,如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