第6章樹6.1樹的定義和基本術(shù)語(yǔ)6.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.3樹的順序存儲(chǔ)6.4K叉樹(不講)6.1樹的定義和基本術(shù)語(yǔ)6.1.1樹和森林6.1.2 森林與二叉樹的等價(jià)轉(zhuǎn)換6.1.3樹的抽象數(shù)據(jù)類型6.1.4樹的周游6.1.1樹和森林

樹的定義(遞歸)樹(tree)是包括n個(gè)結(jié)點(diǎn)的有限集合T(n≥1)，使:有且僅有一個(gè)特定結(jié)點(diǎn)稱為根(root)除根以外的其它結(jié)點(diǎn)被分成m個(gè)(m≥0)不相交的集合T1，T2，…，Tm，而且這些集合的每一個(gè)又都是樹。樹T1，T2，…，Tm稱作這個(gè)根的子樹(subtree)6.1.1樹和森林

樹的邏輯結(jié)構(gòu)包含n個(gè)結(jié)點(diǎn)的有窮集合K(n>0)，且在K上定義了一個(gè)滿足以下條件的二元關(guān)系R={r}：有且僅有一個(gè)結(jié)點(diǎn)k0∈K，它對(duì)于關(guān)系N來(lái)說(shuō)沒(méi)有前驅(qū)。結(jié)點(diǎn)k0稱作樹的根除結(jié)點(diǎn)k0外，K中的每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系r來(lái)說(shuō)都有且僅有一個(gè)前驅(qū)

除結(jié)點(diǎn)k0外的任何結(jié)點(diǎn)k∈K，都存在一個(gè)結(jié)點(diǎn)序列k0，k1，…，ks，使得k0就是樹根，且ks=k，其中有序?qū)?lt;ki-1，ki>∈r(1≤i≤s)。這樣的結(jié)點(diǎn)序列稱為從根k0到結(jié)點(diǎn)k的一條路徑6.1.1樹和森林

樹形結(jié)構(gòu)的各種表示法樹的邏輯結(jié)構(gòu)是：結(jié)點(diǎn)集合K={A，B，C，D，E，F(xiàn)，G，H，I，J}K上的關(guān)系r={ <A，B>，<A，C>， <B，D>，<B，E>，<B，F(xiàn)>， <C，G>，<C，H>， <E，I>，<E，J>}（d）嵌套括號(hào)表示法（b）文氏圖表示法（a）樹形表示法（c）凹入表表示法(A(B(D(I,J),E),(C(F,G())(H)))樹形結(jié)構(gòu)的各種表示法6.1.1樹和森林

樹結(jié)構(gòu)中的概念一棵樹若存在結(jié)點(diǎn)k指向結(jié)點(diǎn)k’的連線(<k，k’>∈r)則稱k是k’的父結(jié)點(diǎn)，k’則是k的子結(jié)點(diǎn)，有向連線稱作邊同一個(gè)父結(jié)點(diǎn)的子結(jié)點(diǎn)之間互稱兄弟沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)稱為根，沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹數(shù)目樹的度：樹中各結(jié)點(diǎn)度的最大值若樹中存在結(jié)點(diǎn)序列k0,k1…ks,使得<k0,k1>，<k1,k2>，…<ks-1,ks>都是樹中的邊，成從結(jié)點(diǎn)k0到結(jié)點(diǎn)ks存在一條路徑，則稱k0是ks的祖先，ks是k0的子孫

結(jié)點(diǎn)層數(shù)：根為第0層，子結(jié)點(diǎn)層數(shù)=父結(jié)點(diǎn)層數(shù)+16.1.1樹和森林

樹結(jié)構(gòu)中的概念在樹T中如果子樹T1，T2，…，Tm的相對(duì)次序是重要的，則稱樹T為有序樹為方便計(jì)算機(jī)處理，將子結(jié)點(diǎn)從左到右依次編號(hào)，即樹是有序樹(orderedtree)度為2的有序樹≠二叉樹度為2的有序樹：刪除第1子結(jié)點(diǎn)后,第2子結(jié)點(diǎn)頂替為第1子結(jié)點(diǎn)二叉樹：度為2且嚴(yán)格區(qū)分左右兩個(gè)子結(jié)點(diǎn)的有序樹才是二叉樹6.1.1樹和森林

森林與樹森林(forest)是零棵或多棵不相交的樹的集合(通常是有序集合)。樹森林：刪去樹根，樹就變成森林。森林樹：加上一個(gè)結(jié)點(diǎn)作樹根，森林就變成樹在樹或森林與二叉樹之間有一個(gè)一一對(duì)應(yīng)的關(guān)系任何森林都唯一地對(duì)應(yīng)到一棵二叉樹任何二叉樹也都唯一地對(duì)應(yīng)到一個(gè)森林ABDC^^EFG^^^^^^firstchildnextsiblingABDEFGCABDEFGCleftchildrightchild6.1.2森林與二叉樹的等價(jià)轉(zhuǎn)換

樹與二叉樹的等價(jià)轉(zhuǎn)換舉例角色互換ABDEFGCABDEFGCABDEFGC6.1.2森林與二叉樹的等價(jià)轉(zhuǎn)換

樹二叉樹轉(zhuǎn)換規(guī)則理解一.樹（森林）二叉樹將第一個(gè)孩子當(dāng)作左孩子,將下一個(gè)兄弟當(dāng)作右孩子(各樹的根當(dāng)作兄弟)二.二叉樹樹（森林）將左孩子當(dāng)作第一個(gè)孩子,將右孩子當(dāng)作下一個(gè)兄弟(共有一個(gè)雙親)(各樹的根當(dāng)作兄弟)ABDEFGCABDEFGC6.1.2森林與二叉樹的等價(jià)轉(zhuǎn)換

圖式森林由３部分組成：森林中第一棵樹的根結(jié)點(diǎn)森林中第一棵樹的子樹森林森林中其它樹構(gòu)成的森林6.1.2森林與二叉樹的等價(jià)轉(zhuǎn)換

舉例

6.1.2森林與二叉樹的等價(jià)轉(zhuǎn)換

森林與二叉樹的轉(zhuǎn)換規(guī)則

F(T1,T2,…,Tn)T1(root,t11,t12,…t1m)

B(LBT,Node(root),RBT)

森林二叉樹若F=空，則B=空否則由Root(T1)Node(root)由(t11,t12,…,t1m)LBT由(T2,T3,…,Tn)RBT森林二叉樹若B=空，則F=空否則由Node(root)Root(T1)由LBT(t11,t12,…,t1m)由RBT

(T2,T3,…,Tn)6.1.3樹的抽象數(shù)據(jù)類型

樹結(jié)點(diǎn)的抽象數(shù)據(jù)類型[代碼6.1]1/2 template<classT> classTreeNode { public: TreeNode(constT&value);//用于拷貝的構(gòu)造函數(shù) virtual~TreeNode(); //析構(gòu)函數(shù) boolisLeaf();//判斷當(dāng)前結(jié)點(diǎn)是否是葉(返true/false) TValue(); //返回結(jié)點(diǎn)的值 TreeNode<T>*LeftMostChild();//返回第一個(gè)左孩子 TreeNode<T>*RightSibling();//返回右兄弟樹結(jié)點(diǎn)的抽象數(shù)據(jù)類型2/2 voidsetValue(T&); //設(shè)置結(jié)點(diǎn)的值 voidsetChild(TreeNode<T>*pointer);//設(shè)置左子結(jié)點(diǎn) voidsetSibling(TreeNode<T>*pointer);//設(shè)置右兄弟 voidInsertFirst(TreeNode<T>*node); //以當(dāng)前結(jié)點(diǎn)第一個(gè)左子結(jié)點(diǎn)身份插入結(jié)點(diǎn) voidInsertNext(TreeNode<T>*node); //以右兄弟的身份插入結(jié)點(diǎn)};6.1.3樹的抽象數(shù)據(jù)類型

樹的抽象數(shù)據(jù)類型[代碼6.2]1/2 template<classT> classTree{ public: Tree(); //構(gòu)造函數(shù) virtual~Tree(); //析構(gòu)函數(shù) TreeNode<T>*getRoot();//返回樹中的根結(jié)點(diǎn) voidCreateRoot(constT&rootValue); //創(chuàng)建值為rootValue的根結(jié)點(diǎn) boolisEmpty();//判空樹(返true/false)樹的抽象數(shù)據(jù)類型2/2TreeNode<T>*Parent(TreeNode<T>*current); //返回current結(jié)點(diǎn)父結(jié)點(diǎn) TreeNode<T>*PrevSibling(TreeNode<T>*current); //返回current結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn) voidDeleteSubTree(TreeNode<T>*subroot); //刪除以subroot為根的子樹的所有結(jié)點(diǎn) voidRootFirstTraverse(TreeNode<T>*root);

//先根深度優(yōu)先周游樹 voidRootLastTraverse(TreeNode<T>*root); //后根深度優(yōu)先周游樹

voidWidthTraverse(TreeNode<T>*root); //廣度優(yōu)先周游樹};6.1.4樹的周游

1、深度優(yōu)先周游樹一.先根次序周游森林≡前序周游二叉樹首棵樹根；首棵樹各子樹；余下各樹根；左子樹；右子樹依次從左至右對(duì)森林每棵樹進(jìn)行先序周游二.后根次序周游森林≡中序周游二叉樹首棵樹各子樹；首棵樹根；余下各樹

左子樹；根；右子樹依次從左至右對(duì)森林每棵樹進(jìn)行后序周游先序：ABCEFDGHJI后序：BEFCDAJHIGABCFEDGHJIABGHCEFIDJ6.1.4樹的周游

1深度優(yōu)先周游

先根深度優(yōu)先周游樹算法6.3template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){ while(root!=NULL){ Visit(root->Value());//訪問(wèn)當(dāng)前結(jié)點(diǎn) RootFirstTraverse(root->LeftMostChild()); //周游頭一棵樹樹根的子樹 root=root->RightSibling();//周游其他的樹 }}6.1.4樹的周游

后根深度優(yōu)先周游樹算法6.4template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){ while(root!=NULL){ RootLastTraverse(root->LeftMostChild()); //周游頭一棵樹樹根的子樹 Visit(root->Value()); //訪問(wèn)當(dāng)前結(jié)點(diǎn) root=root->RightSibling();//周游其他的樹 }}6.1.4樹的周游

2、廣度優(yōu)先周游森林breadth-first,也稱寬度優(yōu)先周游、層次周游從根開始自上至下逐層周游，同層從左到右逐一訪問(wèn)下圖廣度優(yōu)先周游森林的結(jié)點(diǎn)序列AGBCDHIEFJABCFEDGHJI6.1.4樹的周游廣度優(yōu)先周游樹/森林template<classT>//[算法6.5]voidTree<T>::WidthTraverse(TreeNode<T>*root){ usingstd::queue; //使用STL隊(duì)列 queue<TreeNode<T>*>aQueue; TreeNode<T>*pointer=root; while(pointer!=NULL){ aQueue.push(pointer); //當(dāng)前結(jié)點(diǎn)入隊(duì) pointer=pointer->RightSibling();} //指向右兄弟 while(!aQueue.empty()){ pointer=aQueue.front(); //取隊(duì)列首結(jié)點(diǎn)指針 aQueue.pop(); //出隊(duì) Visit(pointer->Value()); //訪問(wèn)當(dāng)前結(jié)點(diǎn) pointer=pointer->LeftMostChild();//指向最左子結(jié)點(diǎn) while(pointer!=NULL){ //當(dāng)前結(jié)點(diǎn)子結(jié)點(diǎn)入隊(duì) aQueue.push(pointer); pointer=pointer->RightSibling();}}}6.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6.2.1子結(jié)點(diǎn)表表示法6.2.2靜態(tài)左子/右兄表示法6.2.3動(dòng)態(tài)結(jié)點(diǎn)表示法6.2.4動(dòng)態(tài)“左子/右兄”二叉鏈表表示法6.2.5父指針表示法6.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.2.1子結(jié)點(diǎn)表表示法用數(shù)組存儲(chǔ)各結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)信息包括結(jié)點(diǎn)值、其父結(jié)點(diǎn)在數(shù)組中下標(biāo)、一個(gè)指向孩子鏈表的頭指針每個(gè)結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)鏈接成表，數(shù)組存儲(chǔ)其頭指針查找firstchild易，但查找nextsibling難12456父孩子^^ABCFEDG3^值000223\6.2.2靜態(tài)左子/右兄表示法

兩樹合并舉例ABCFED左子值父右兄0123456789GHJI1A\\\B024C03\D0\\E25\F2\\G\\9H68\I6\\J7\09A作H首子：H任A作左子A認(rèn)H作父A認(rèn)J作右兄76.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.2.2靜態(tài)左子/右兄表示法用數(shù)組存儲(chǔ)各結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包括4個(gè)域：結(jié)點(diǎn)的值，父結(jié)點(diǎn)、最左子結(jié)點(diǎn)和右側(cè)兄弟結(jié)點(diǎn)的下標(biāo)ADT的基本操作可通過(guò)讀取結(jié)點(diǎn)中的一個(gè)值來(lái)實(shí)現(xiàn)。如果兩棵樹存儲(chǔ)在同一個(gè)數(shù)組中，那么把其中一個(gè)添加為另一棵樹的子樹只需簡(jiǎn)單設(shè)置三個(gè)指針值即可。此法比子結(jié)點(diǎn)表表示法空間效率更高，能方便訪問(wèn)右兄弟,而且結(jié)點(diǎn)數(shù)組中的每個(gè)結(jié)點(diǎn)僅需要固定大小的存儲(chǔ)空間6.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.2.3動(dòng)態(tài)表示法定長(zhǎng)：為每個(gè)結(jié)點(diǎn)分配確定數(shù)目的指針（對(duì)結(jié)點(diǎn)度小的樹浪費(fèi)空間，對(duì)度大結(jié)點(diǎn)難以擴(kuò)充）變長(zhǎng)：每個(gè)結(jié)點(diǎn)空間動(dòng)態(tài)分配可變的存儲(chǔ)空間

每個(gè)結(jié)點(diǎn)存儲(chǔ)子結(jié)點(diǎn)數(shù)目和一個(gè)相應(yīng)長(zhǎng)度的(孩)子結(jié)點(diǎn)指針表（見p145圖6.9）本質(zhì)上“子結(jié)點(diǎn)表”表示法相同，但是它動(dòng)態(tài)地分配結(jié)點(diǎn)空間，而不是把結(jié)點(diǎn)分配在數(shù)組中6.2樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

6.2.4動(dòng)態(tài)左子/右兄二叉鏈表表示法(最常用)ABDC^^EFG^^^^^^ABDEFGC每一個(gè)結(jié)點(diǎn)除數(shù)據(jù)域,還設(shè)兩個(gè)指針域指向該結(jié)點(diǎn)的第一個(gè)孩子LeftChild下一個(gè)兄弟RightSiblingpChildpSibling樹結(jié)點(diǎn)抽象數(shù)據(jù)類型的實(shí)現(xiàn)//補(bǔ)充與具體實(shí)現(xiàn)相關(guān)的私有成員變量申明private: Tm_Value; //樹結(jié)點(diǎn)的值 TreeNode<T>* pChild; //左子結(jié)點(diǎn) TreeNode<T>* pSibling; //右兄弟結(jié)點(diǎn)樹結(jié)點(diǎn)抽象數(shù)據(jù)類型的實(shí)現(xiàn)template<classT>boolTreeNode<T>::isLeaf(){ //如果結(jié)點(diǎn)是葉，返回true if(pChild==NULL) returntrue; returnfalse; }template<classT>voidTreeNode<T>::setValue(Tvalue){ //設(shè)置結(jié)點(diǎn)的值 m_Value=value; }template<classT>voidTreeNode<T>::InsertFirst(TreeNode<T>*node){ //以第一個(gè)子結(jié)點(diǎn)的身份插入結(jié)點(diǎn) if(!pChild) pChild=node;//this沒(méi)左子:node作 else{ node->pSibling=pChild;//有:原左子作node右兄 pChild=node; } }//node作左子樹抽象數(shù)據(jù)類型的部分實(shí)現(xiàn)[算法6.7]//與具體實(shí)現(xiàn)相關(guān)的私有成員變量private: TreeNode<T>*root; //樹根結(jié)點(diǎn)//部分成員函數(shù)的具體實(shí)現(xiàn)

template<classT>Tree<T>::Tree() { //構(gòu)造函數(shù) root=NULL; }template<classT>TreeNode<T>*Tree(T)::Parent(TreeNode<T>*current){ usingstd::queue;Queue<TreeNode<T>*>aQueue;//邊按層周游邊找TreeNode<T>*pointer=root;TreeNode<T>*upperlevelpointer=NULL;//存父結(jié)點(diǎn)if(current!=NULL&&pointer!=current){ while(pointer!=NULL){

//森林所有樹根入隊(duì) if(current==pointer)returnNULL; aQueue.push(pointer); pointer=pointer->RightSibling(); } while(!aQueue.empty()){ pointer=aQueue.front(); aQueue.pop();//取隊(duì)頭 upperlevelpointer=pointer;//父 pointer=pointer->LeftMostChild();//子 while(pointer){//pointer的所有兄弟與current比 if(current==pointer)//若等 returnupperlevelpointer;//找到parent else{ aQueue.push(pointer);//比pointer其他兄弟 pointer=pointer->RightSibling();}}}}returnNULL; }template<classT>voidTree<T>::DestoryNodes(TreeNode<T>*root){//刪除以root為根的子樹的所有結(jié)點(diǎn)（后序周游） if(root!=NULL){ DestroyNodes(root->LeftMostChild()); DestroyNodes(root->RightSibling()); deleteroot; } }樹抽象數(shù)據(jù)類型的實(shí)現(xiàn) template<classT> voidTree<T>::DeleteSubTree(TreeNode<T>*subroot) {//刪除以subroot為根的子樹的所有結(jié)點(diǎn)[代碼6.7] TreeNode<T>*pointer; if(subroot==NULL)return;//空樹不必刪 pointer=Parent(subroot);//point指向(被刪子樹根的)父結(jié)點(diǎn) if(pointer==NULL)//被刪樹是森林第1棵樹讓第2棵樹作root root=subroot->RightSibling(); elseif(pointer->LeftMostChild()==subroot_)//被刪點(diǎn)是父最左子 pointer->setChild(subroot->RightSibling());//讓右兄作父最左子 else{//被刪(不是最左子)有左兄,讓左兄的右兄是被刪點(diǎn)右兄 pointer=pointer->LeftMostChild(); while(pointer->RightSibling()!=subroot)//則找直接左兄 pointer=pointer->RightSibling(); pointer->setSibling(subroot->RightSibling()); } //讓左兄pointer的右兄是被刪點(diǎn)subroot的右兄

subroot->setSibling(NULL);//被刪點(diǎn)的右兄為空(成為樹而非森林) DestroyNodes(subroot);}//刪樹6.2.5父指針表示法父指針(parentpointer)表示法：每個(gè)結(jié)點(diǎn)只保存一個(gè)指針域指向其父結(jié)點(diǎn)用數(shù)組實(shí)現(xiàn)，查找父結(jié)點(diǎn)的T(n)=O(1)方便實(shí)現(xiàn)求根和求祖先算法等”向上”的操作不適合求子孫算法節(jié)省空間，適合無(wú)序樹查詢結(jié)點(diǎn)的根、合并樹父指針數(shù)組表示法父節(jié)點(diǎn)索引標(biāo)記結(jié)點(diǎn)索引6.3樹的順序存儲(chǔ)6.3.1帶右鏈的先根次序表示6.3.2帶雙標(biāo)記位的先根次序表示6.3.3帶度數(shù)的后根次序表示6.3.4帶雙標(biāo)記的層次次序表示ABCFEDGHJI6.3.1帶右鏈的先根次序表示在帶右鏈的先根次序表示中，結(jié)點(diǎn)按先根次序順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。每個(gè)結(jié)點(diǎn)除包括結(jié)點(diǎn)本身數(shù)據(jù)外，還附加兩個(gè)表示結(jié)構(gòu)的信息字段，結(jié)點(diǎn)的形式為:info是結(jié)點(diǎn)的數(shù)據(jù)，rlink是右指針，指向結(jié)點(diǎn)的下一個(gè)兄弟、即對(duì)應(yīng)的二叉樹中結(jié)點(diǎn)的右子結(jié)點(diǎn)ltag是一個(gè)一位的左標(biāo)記，當(dāng)結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)，即對(duì)應(yīng)的二叉樹中結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)時(shí)，ltag為1，否則為0帶右鏈的先根次序表示法這種表示法與llink—rlink表示法相比，用ltag代替了llink，占用的存儲(chǔ)單元要少些，但并不丟失信息可以從結(jié)點(diǎn)的次序和ltag的值完全可以推知llinkltag==0:有左子，它的llink指向該結(jié)點(diǎn)數(shù)組右鄰ltag==1:沒(méi)有左子，它的llink為空6.3.2帶雙標(biāo)記位的先根次序表示法帶右鏈先根序表示法中每個(gè)結(jié)點(diǎn)都含ltag和rlink域，rlink也可替換為一位的rtagltag==1：葉，llink=NULLltag==0：有孩子，左子為其右鄰居rtag==1：沒(méi)右兄，rlink=NULLrtag==0：有右兄，但暫時(shí)不知，入棧等待確定右兄ltaginfortag6.3.2帶雙標(biāo)記位的先根次序表示法1000010111infoltagHFDECKABJG1010110011rtagltag==1：葉，llink=NULLltag==0：有孩子，左子為其右鄰rtag==1：沒(méi)右兄，rlink=NULLrtag==0：有右兄，但暫時(shí)不知6.3.2帶雙標(biāo)記位的先根次序表示法任何結(jié)點(diǎn)的子樹結(jié)點(diǎn)在先根序列中都排在該結(jié)點(diǎn)之后；任何結(jié)點(diǎn)的子樹結(jié)點(diǎn)在先根序列中排在最后的一個(gè)結(jié)點(diǎn)一定沒(méi)有子結(jié)點(diǎn)(ltag為1)由結(jié)點(diǎn)排列次序和ltag，rtag的值就可推知rlink的值。當(dāng)一個(gè)結(jié)點(diǎn)x的rtag為1時(shí)（無(wú)右兄），rlink應(yīng)為空當(dāng)一個(gè)結(jié)點(diǎn)x的rtag為0時(shí)（有右兄），其rlink應(yīng)指向結(jié)點(diǎn)序列中排在結(jié)點(diǎn)x的子樹結(jié)點(diǎn)后面的那個(gè)結(jié)點(diǎn)y如何確定x的右兄y?由于先根次序表示的樹結(jié)構(gòu)是嵌套的，需要用一個(gè)棧來(lái)記錄待配置rlink的結(jié)點(diǎn)帶雙標(biāo)記位的先根次序表示法雖然節(jié)省空間，但因需要耗費(fèi)時(shí)間推導(dǎo)失去的信息，所以采用得更多的還是帶右鏈的先根次序表示法帶雙標(biāo)記位先根次序樹構(gòu)造算法template<classT>classDualTagTreeNode//雙標(biāo)記位先根次序樹結(jié)點(diǎn)類{ public: T info; //樹結(jié)點(diǎn)信息 int ltag; //左標(biāo)記 intrtag; //右標(biāo)記 DualTagTreeNode(); virtual~DualTagTreeNode();};算法6.10算法框架newp,作rootfor(count-1) p數(shù)值=node[i] ifnode[i].rtag==0:(有右兄)入棧等待確定右兄 ifnode[i].rtag==1:(無(wú)右兄)p->rlink=NULL newtempp; ifnode[i].ltag==0:(有子)p->llink=tempp; ifnode[i].ltag==1:(葉)為棧頂確定右兄 { p->llink=NULL 出棧p p->rlink=tempp;} p=tempp;最后結(jié)點(diǎn)被賦值A(chǔ)BCFEDGHJI帶雙標(biāo)記位先根次序樹構(gòu)造算法[算法6.10]template<classT>//構(gòu)造左子右兄樹Tree<T>::Tree(DualTagTreeNode<T>*nodeArray,intcount){ usingstd::stack;//使用STL中的stack stack<TreeNode<T>*>aStack; TreeNode<T>*pointer=newTreeNode<T>;//建立結(jié)點(diǎn)p root=pointer; //作根for(inti=0;i<count-1;i++)//處理一個(gè)結(jié)點(diǎn){ pointer->setValue(nodeArray[i].info); if(nodeArray[i].rtag==0) aStack.push(pointer);//有右兄入棧待定 else pointer->setSibling(NULL);//沒(méi)右兄，rlink設(shè)為空 TreeNode<T>*temppointer=newTreeNode<T>;//建tempp if(nodeArray[i].ltag==0)pointer->setChild(temppointer);//有子 else{pointer->setChild(NULL);//葉：llink設(shè)為空 pointer=aStack.top(); aStack.pop(); //出棧ppointer->setSibling(temppointer); }//p->rlink=tempp;

pointer=temppointer; }//endfor帶雙標(biāo)記位先根次序樹構(gòu)造算法[算法6.10]//處理最后一個(gè)結(jié)點(diǎn) pointer->setValue(nodeArray[count-1].info); pointer->setChild(NULL); pointer->setSibling(NULL); }帶度數(shù)的后根次序表示法在帶度