樹和森林的概二叉樹(Binary二叉樹的表二叉樹遍(BinaryTreeTraversal)線索化二叉(ThreadedBinaryTree)堆(Heap)樹與森林(Tree&二叉樹的計(Huffman樹和森林的概樹的定樹是由n(n0)個結點組成的有限集合。如果0，稱為空樹；如果n0，mm0個互不0,1,…,-1，每個集合又是一(subee)。每棵子樹0個或多個直接后繼。(child)

子孫(descendant)

森林樹的抽象數據類template<classType>classTree{Tree(~Tree(positionRoot(BuildRoot(constType&valuepositionFirstChild(positionppositionNextSibling(positionp,positionvpositionParent(positionp);TypeRetrieve(positionp);positionInsertChild(constpositionconstType&valuepositionDeleteChild(positionp,inti);voidDeleteSubTree(positiont);intIsEmpty(}(Binary二叉樹的五種不同形性質1若二叉樹的層次從0開始則在二叉樹的i層最多有2i個結點。(i0)[證明用數學歸納法性質2高度為k的二叉樹最多有2k+1-1個結點。(k-1)[證明用求等比級數前k項和的公式性質3對任何一棵二叉樹如果其葉結點個數n0,度為2的非葉結點個數為n2則數為n，總邊數為en=n0+n1+ e=2n2+n1=n-因此2n2n1n0n1n2-n2=n0- n0=n2+定義1滿二叉樹(FullBinary定義2完全二叉樹(CompleteBinary性質4具有nlog2(n+1)-2h1n2h+112hn+12h+1取對h<log2(n+1)h+1性質5如果將一棵有n個結點的完全二叉樹自頂 0,1,2,…, 放于一個一維數組中,并簡稱 點i(0in-1。則有以下關系：若i0i無雙若i0i的雙親為(i-若2*i+1<n,則i的左 若2*i+2<n,則i的 為i為偶數,且i!=0,則其左兄弟為i-1i為奇數且in-1則其右兄弟為i+1i所在層次為log2二叉樹的抽象數據類BinaryTree(BinTreeNode<Type>*lch,BinTreeNode<Type>*rch,Typeitem);intIsEmpty();BinTreeNode<Type>*Parent();BinTreeNode<Type>*LeftChild();BinTreeNode<Type>*RightChild();intInsert(constType&item);intFind(constType&item)const;TypeGetData()const;BinTreeNode<Type>*GetRoot()const;}二叉樹的表數組表完全二叉樹的數組表 一般二叉樹的數組表全二叉樹那樣，可能會浪費很多空間，單支樹就是一個情況。鏈表表

單支二叉樹鏈表表示的示二叉鏈表的靜二叉樹的類定template<classType>classtemplate<classType>ClassBinTreeNode{friendclassBinaryTree;BinTreeNode():leftChildrightChild(NULL){BinTreeNode(Typeitem,BinTreeNode<Type>*left=NULL,BinTreeNode<Type>*right=NULL):data(item),leftChild(left),rightChild(right){}Type&GetData()const{returndata;{returnleftChild;{returnrightChild;}voidSetData(constType&item){data=item;voidSetLeft(BinTreeNode<Type>*L{leftChild=L;voidSetRight(BinTreeNode<Type>*R{rightChild=R;BinTreeNode<Type>*leftChild,*rightChild;Typedata;template<classType>classBinaryTree{BinaryTree():root(NULL){BinaryTree(Typevalue):RefValueroot(NULL){virtual~BinaryTree(){destroy(root);}virtualintIsEmpty(){returnroot==NULL?1:0;}virtualBinTreeNode<Type>*Parent({returnroot==NULL||root==current？NULL:Parent(root,current);}{returnroot!=NULLcurrent→leftChild:NULL;{returnroot!=NULLcurrent→rightChild:NULL;}virtualintInsert(constType&item);virtualintFind(constType&item)BinTreeNode<Type>*GetRoot(){returnroot;friendistream&operator>>(istream&in,BinaryTree<Type>&Tree)friendostream&operator<<(ostream&out,BinaryTree<Type>&Tree)TypeRefValue;BinTreeNode<Type>*Parent(BinTreeNode<Type>*start,intInsert(BinTreeNode<Type>*¤t,constType&item)ostream&out)constType&item)voiddestroy(BinTreeNode<Type>二叉二叉樹部分成員函數的實destroy(BinTreeNode<Type>*current){if(current!=NULL)destroy(current→leftChild);destroy(current→rightChild);deletecurrent;}}*start,BinTreeNode<Type>*cuurent){if(start==NULL)returnNULL;if(start→leftChild==current||==current)returnstart;BinTreeNode<Type>*p;if((p=Parent(start→leftChild,current)!=NULL)returnelsereturnParent(start→rightChild,current}Traverse(BinTreeNode<Type>*current,ostream&out)const{if(current!=NULL)out<<current→data<<‘’;Traverse(current→leftChild,out);Traverse(current→rightChild,out);}}Template<classType>istream&operator>>(istream&in,BinaryTree<Type>&Tree){cout構造二叉樹:\ncout輸入數(Tree.RefValue<<"結束):";in>>while(item!=Tree.RefValue)Tree.Insert(itemcout輸入數(Tree.RefValue<<"結束):";in>>}return}Template<classType>ostream&operator<<(ostream&out,BinaryTree<Type>&Tree){out二叉樹的前序遍歷out<<endl;returnout;} 根結點記作遍歷根的左子樹記作遍歷根的右子樹記作則可能的遍歷次序前序VLR鏡像VRL中序LVR鏡像RVL后序LRV鏡像RLV(Inorder中序遍歷左子(L)；根結(V)；中序遍歷右子樹(R)遍歷結a+b*c-d-e/

表達式語法二叉樹遞歸的二叉樹遞歸的中序遍歷算InOrder(root}InOrder(BinTreeNode<Type>*current){if(current!=NULL){InOrder(current→leftChild);cout<<current→data;InOrder(current→rightChild}}中序遍歷二叉樹的遞歸過程圖(Preorder前序遍歷左子樹(L)；(R)-+a*b-cd/e二叉樹遞歸的二叉樹遞歸的前序遍歷算PreOrder(root}PreOrder(BinTreeNode<Type>*current){if(current!=NULL){cout<<current→data;PreOrder(current→leftChild);}}(Postorder后序遍歷左子樹(L)；(R)；根結點(V)。abcd-*+ef/二叉樹遞歸的后序遍歷算template<classType>voidBinaryTree<Type>::PostOrder(){PostOrder(root);}PostOrder(BinTreeNode<Type>*current){if(current!=NULL)PostOrder(current→leftChild);PostOrder(current→rightChild);cout<<current→data;}}利用二叉樹后序遍歷計算二叉樹結點個數及二叉樹的高度Size(constBinTreeNode<Type>*t)const{if(t==NULL)returnelsereturn1+Size(t→leftChild+Size(t→rightChild}Depth(constBinTreeNode<Type>*t)const{if(t==NULL)return-elsereturn1+Max(Depth(t→leftChildDepth(t→rightChild)}template<classType>classTreeIterator{TreeIterator(constBinaryTree<Type>&BT)T(BT),current(NULL){}virtual~TreeIterator(){}virtualvoidFirst()=virtualvoidoperator++()=intoperator+()const{returncurrent!=NULL;}constType&operator()()const;constBinTreeNode<Type>*current;TreeIterator(constTreeIterator&){}constTreeIterator&operator=(constTreeIterator&template<classType>constType<Type>::operator()()const{if(current==NULL){cout<<" "<<endl;exit(1);}returncurrent→GetData();} 走過的結點，設置一個工作棧退退棧次結點PopTim0,1或2，表示第幾次退棧，用以 后序遍歷游標類的定template<classType>structstkNodeconstBinTreeNode<Type>*Node; int //退棧次stkNode(constBinTreeNode<Type>*NNULLNode(NPopTim(0) //構造}template<classType>classPostOrder:publicTreeIterator<Type>{PostOrder(constBinaryTree<Type>&BT~PostOrder(){voidFirst(); voidoperator++();//定位到后序次序下的下一個結StackStkNode<Type //工作}后序游標類成員函數的PostOrder(constBinaryTree<Type>&BT)st.Push(StkNode<Type>(BT.GetRoot())}template<classType>voidPostOrderFirst()st.MakeEmpty(if(BT.GetRoot()!=NULLst.Push(StkNode<Type>(BT.GetRoot()));operator++();}template<classType>voidPostOrder<Type>::operator++(){if(st.IsEmpty())if(current==NULL)cout已經遍歷結束endl;exit}currentNULL; //遍歷}for(;;) //循環,找后序下的下一個結Cnode=st.Pop(if ode.PopTim3//從右子樹退{current=Cnode.Node;return;st.Push(Cnode); //否則加一進棧if(Cnode.PopTim==1){ //=1,左 if(Cnode.Node→GetLeft()!=NULLst.Push(StkNode<Type>Cnode.Node→GetLeft())}else //=2, 進if(Cnode.Node→GetRight()!=NULLst.Push(StkNode<Type>Cnode.Node→GetRight())}}} 中序遍歷也要使用一個遞歸工作棧st中序游標類的template<classType>classInOrder:publicPostOrder<Type>{InOrder(BinaryTree<Type>&BT)PostOrder<Type>(BT){}voidFirst();voidoperator++(中序游標類operator++()操作的實現template<classTypevoidInOrder<Type>::operator++(){if(st.IsEmpty())if(current==NULLcout已經遍歷完成endl;exit(1)current=NULL;}StkNode<Type>for(;; //循環,找中序下的下一個結Cnodest.Pop //退if(ode.TimPop==2){//從左子樹退出current=Cnode.Node; if(Cnode.Node→GetRight()!=NULL)st.PushStkNode<Type(//右node.Node→GetRight())}st.Push(Cnode); if(Cnode.Node→GetLeft()!=NULL)st.Push(StkNode<Type> // 進Cnode.Node→GetLeft())}}從根開始逐 用FIFO隊列實現遍歷順層次序游標類的定template<classType>classLevelOrder:publicTreeIterator<Type>{LevelOrder(constBinaryTree<Type>&BT~LevelOrder(){}voidFirst();voidoperator++();Queue<constBinTreeNode<Type>*>層次序游標類的operator操template<classType>LevelOrderLevelOrder(constBinaryTree<Type>&BT)TreeIterator<Type>(BT{qu.EnQueue(BT.GetRoot());template<classType>viodLevelOrder<Type>::First(){//初始化：只有根結點在qu.MakeEmpty(if(BT.GetRoot())qu.EnQueue(BT.GetRoot());operator++();}template<classType>LevelOrder<Type>::operator++(){if(qu.IsEmpty()){if(current==NULL)cout已經遍歷完成endl;exit}current=NULL;}current=qu.DeQueue();//當前結點是退隊結點if(current→GetLeft()!=NULL) qu.EnQueue(current→GetLeft());//進隊列if(current→GetRight()!=NULL) qu.EnQueuecurrent→GetRight//進隊}(ThreadedBinary線索增加Pred指針和Succ指針的二叉線索化二叉樹及其二叉鏈表表LeftThread=0, LeftThread=1, RightThread=0, RightThread=1, 中序線索化二叉樹的類定template<class中序線索化二叉樹的類定friendclassThreadInorderIterator;intleftThread,rightThread;ThreadNode<Type>*leftChild,*rightChild;Typedata;ThreadNode(constTypeitem):data(item),leftChild(NULL),rightChild(NULL),leftThread(0),rightThread(0){}template<classType>classThreadTree{friendclassThreadInorderIterator;ThreadNode<Type>template<classType>classThreadInorderIterator{&Tree):T(Tree){current=T.root;}ThreadNode<Type>*First(ThreadNode<Type>*Last(ThreadNode<Type>*Next(ThreadNode<Type>*Prior();ThreadTree<Type>ThreadNode<Type> 帶表頭結點的中序穿線鏈在中序下的后A

if(currentrightChild后繼為else無后 else//currentrightThreadif(currentrightChild

的中序下的第一個結else出錯情 LAGCHGCHL

if(currentleftChild前驅為else無前if(currentleftChild!=T.root) else出錯情 在中序線索化二叉樹中的部分成員函數的實template<classType>*ThreadInorderIterator<Type>::First(){while(current→leftThread==0)current=current→leftChild;returncurrent;}template<classType>*ThreadInorderIterator<Type>::Next(){ThreadNode<Type>*p=current→rightChild;if(current→rightThread==0)while(p→leftThread==0)p=current=if(current==T.root)returnNULL;elsereturncurrent;}template<classType>ThreadNode<Type>*p;for(p=First();p!=NULL;p=Next()cout<<p→data<<}通過中序遍歷建立中序線索化二叉InThread(ThreadNode<Type>*current,ThreadNode<Type>*pre){if(current!=NULL){InThread(current→leftChild,pre);if(current→leftChild==NULL){current→leftChild=pre;current→leftThread=1;}if(pre→rightChild==NULL){pre→rightChild=current;pre→rightThread=1;}pre=InThread(current→rightChild,pre}}template<classType>ThreadNode<Type>root=newThreadNode<Type>;root→leftThread=1;root→rightThread=0;if(this==NULL){root→leftChild=root;root→rightChild=root;}elsecurrent=root→leftChild=pre=InThread(current,prepre→rightChild= }}前序線索化二前序序ABDC

DBEC在后序線索化二叉樹尋找當前結點的后堆堆Heaptemplate<classType>classMinPQ{VirtualvoidInsert(constType&)=0;VirtualType*RemoveMin(Type&)=0;}最小優先級隊列類堆的定完全二叉樹的數組表Ki Ki

完全二叉樹的數組表Ki Ki最小堆的類定template<classType>classMinHeap:publicMinPQ<Type>{MinHeap(intmaxSize)MinHeap(Typearr[],intn~MinHeap(){delete[]heap;}constMinHeap<Type>&operator=(constMinHeap&R);intInsert(constType&x);intRemoveMin(Type&xintIsEmpty()const{returnCurrentSize==0;intIsFull(){returnCurrentSize==MaxHeapSize;}voidMakeEmpty(){CurrentSize=0;}enum{DefaultSize=10};Type*heap;intCurrentSize;intMaxHeapSize;voidFilterDown(inti,intm);voidFilterUp(inti);}堆的建template<classType>堆的建MinHeap(intmaxSize)//根據給定大小maxSize,MaxHeapSize=DefaultSize<maxSizemaxSize:DefaultSize; heap=newType[MaxHeapSize];//創建堆空間CurrentSize=0; }template<classType>MinHeapMinHeap(Typearr[],intn)//根據給定數組中的數據和大小,建立堆對MaxHeapSize=DefaultSize<n?n:DefaultSize;heap=newType[MaxHeapSize];heap //數組傳CurrentSize //當前堆intcurrentPos=(CurrentSize-2)/2; while(currentPos>=0){//從下到上逐步擴大,形成FilterDown(currentPos,CurrentSize//從currentPos開始,到CurrentSize為止,調currentPos--}}將將一組用數組存放的任意數據自下向上逐步調整為最小最小堆的向下調整算template<classType>voidMinHeap<Type>::FilterDown(constintstart,constintEndOfHeap){inti j ji的Typetemp=while(j<=EndOfHeap)if(j<EndOfHeap&&heap[j].keyheap[j+1].key) // 中選小if(temp.key<=heap[j].key)else{heap[i]=heap[j];i= j=2*j+1;}heap[i]=}堆template<classType>intMinHeap<Type>::Insert(constType&x){//在堆 新元素ifCurrentSizeMaxHeapSize //堆{cout<<"堆已滿"<<endl;return0;}heap[CurrentSize]=x; FilterUp(CurrentSize); return1;}template<classType>voidMinHeap<Type>::FilterUp(intstart){//從start開始,向上直到0,調整intjstart,ij- ij的雙Typetemp=heap[j];while(j>0){if(heap[i].key<=temp.key)else{heap[j]=heap[i];j=i;i=(i-1)/2;}heap[j]=}template<classType>intMinHeapRemoveMin(Type&x)if(!CurrentSize{cout<<“堆已空"<<endl;return0;}x=heap[0]; heap[0]=heap[CurrentSize-1]; FilterDown(0,CurrentSize-1);return1;}樹 表樹的廣義表表(結點的utype域沒有畫出雙雙親表 -右兄弟表示第一種解決方d第二種解決方樹的 -右兄弟表用 -右兄弟表示實現的樹的類定template<classType>classtemplate<classType>classTreeNode{friendclassTree<Type>;TreeNode(Typevalue=0,TreeNode<Type>*fc=NULL,TreeNode<Type>*ns=NULL):data(value),firstChild(fc),nextSibling(ns){}template<classType>classTree{Tree(){root=current=NULL;voidPreOrder(ostream&out,intFind(TypeNode<Type>*p,Type voidRemovesubTree(TreeNode<Type>*p);intFindParent(TreeNode<Type>*t,*p);}用 -右兄弟表示實現的樹的部分操template<classType>voidTree//建立樹的根結點,并使之成為樹的當前結template<classType>intTreeNodeRoot()if(root==NULL){current=NULL;return0;}else{current=root;return1;}}//在樹中尋找當前結點的雙親,使之成為當前結TreeNode<Type>*p=current,if(current==NULL||current==root{current=NULL;return0;t=root; intk=FindParent(t,p);returnk;}template<classType>intTreeFirstChild()//在樹中尋找當前結點的長子,使之成為當前結if(current!=NULL&&!=NULL{current=current→firstChild;return1;current=NULL;return}NextSibling()//在樹中尋找當前結點的兄弟,使之成為當前結點(current!=NULL&¤t→nextSiblingNULL{current=current→nextSibling;return1;current=NULL;return}FindParent(TreeNode<Type>*t,*p){//在根t的樹中尋找p的雙親,使之成為當前結while(q!=NULL&&q!=p)//循根的長子的兄弟鏈,遞歸在子樹中搜if((inti=FindParent!=0)returni;q=q→nextSibling;}if(q!=NULL&&q==p{current=t;return1;elsereturn //未找到雙親,當前結}Find(Type ){if(IsEmpty())return0;returnFind(root, }template<classType>intTreeFind(TreeNode<Type>*p, )//在根為p的樹中尋找值 的結點,找到//該結點成為當前結點,否則當前結點不變。函//返回成功標志：=1,搜索成功;=0,搜索intresult=if(p→data ){result=1;current=p;elseTreeNode<Type>*q=p→firstChild;while(q!=NULL&&!(result=Find( ))q=}return}森林與二叉樹的對應關森林轉化成二叉樹的規若F為空，即n0，對應的二叉樹B為空二叉樹若F不空，對應二叉樹B的根root(B)是F中第一棵樹的根root其左子樹為B(T11T12T1m)，其中T12T1m是root(T1)的子樹其右子樹為B(T2T3Tn)，其中，T2,T3,…,Tn是除T1外其它樹構成的森林。二叉樹轉換為森林的規如果B為空，對應的森林F也為空如果B非空，F中第一棵樹T1的根為T1的根的子樹森林{T11T12,…,T1m}是由root的左子樹LB轉換而來，F中除了T1之外其余的樹組成的森林{T2,T3,…,Tn}是由root的右子樹RB轉換而成的森林。深度優先遍樹的二叉樹表樹的先根次序遍歷的遞歸算PreOrder(){if(!IsEmpty())visit(); TreeNode<Type>*p=current;//暫存當前結點inti=FirstChild(); while(i){PreOrder();i=NextSibling();}//遞歸先根遍歷各current //遞歸完恢復當前結}}樹的后根次序遍歷的遞歸算PostOrder(){if(!IsEmpty())TreeNode<Type>*p=current;//暫存當前結點inti=FirstChild(); while(i){PostOrder();i=NextSibling();}//遞歸后根遍歷各棵子current //遞歸完恢復當visit 根結}}按先根次序遍歷樹的迭代算NorecPreOrder(){do{while(!IsEmpty()){//從根沿長子鏈向下visit;st.Pushcurrent)//邊邊進棧FirstChild();}while(IsEmpty()&&!st.IsEmpty())current=st.Pop();NextSibling( // 或無兄弟,退棧,轉向下一兄whileIsEmpty //棧空,退出循current=}(4)(4)按后根次序遍歷樹的迭代算PostOrder1(){do{whileIsEmpty //從根沿長子鏈向st.Pushcurrent);FirstChild //進}while(IsEmpty()&&!st.IsEmpty()){current=st.Pop();visit();NextSibling();// 或無兄弟,退棧 ,轉向兄}while(!IsEmpty()current=}廣度優先遍按層次次序遍歷樹的算LevelOrder(){Queue<TreeNode<Type>*>Qu(DefaultSize);if(!IsEmpty()){TreeNode<Type>*p=current;Qu.EnQueue(current); while(!Qu.IsEmpty()) //隊列不current=Qu.DeQueue();visit(//退出FirstChild(); //轉向長子while(!IsEmpty()) {Qu.EnQueue(current);NextSibling();}}current=}先