1、 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES第第 5章章 樹樹 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES樹和森林的概念u兩種樹：自由樹與有根樹。兩種樹：自由樹與有根樹。 u自由樹：自由樹：u 一棵自由樹一棵自由樹 Tf 可定義為一個二元組可定義為一個二元組u Tf = (V, E) u其中其中V = v1, ., vn 是由是由

2、 n (n0) 個元素組個元素組成的有限非空集合，稱為頂點集合。成的有限非空集合，稱為頂點集合。E = (vi, vj) | vi, vj V, 1i, jn 是是n-1個序對的集合，稱為邊個序對的集合，稱為邊集合，集合，E 中的元素中的元素 (vi, vj）稱為邊或分支。）稱為邊或分支。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES自由樹 Department of Computer Science & Technology, Nanjing Unive

3、rsity fall DATA STRUCTURESu r 是一個特定的稱為根(root)的結點，它只有直接后繼，但沒有直接前驅；u根以外的其他結點劃分為 m (m 0) 個互不相交的有限集合T1, T2, , Tm，每個集合又是一棵樹，并且稱之為根的子樹。u每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。00n,T,.,T,Tr,n,Tm21u有根樹：有根樹：u一棵有根樹一棵有根樹 T，簡稱為樹，它是，簡稱為樹，它是n (n0) 個結個結點的有限集合。當點的有限集合。當n = 0時，時，T 稱為空樹；否則，稱為空樹；否則，T 是非空樹，記作是非空樹，記作 Departmen

4、t of Computer Science & Technology, Nanjing University fall DATA STRUCTURES樹的示意圖樹的示意圖（P.187） Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES樹的特點 每棵子樹的根結點有且僅有一個直接前驅，每棵子樹的根結點有且僅有一個直接前驅，但可以有但可以有0個或多個直接后繼。個或多個直接后繼。0層1層3層2層height= 3ACGBDEFKLHMIJ Department of

5、Computer Science & Technology, Nanjing University fall DATA STRUCTURES0層層1層層3層層2層層height= 3ACGBDEFKLHMIJ術語術語 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const Type& valu

6、e ); position FirstChild ( position p ); position NextSibling ( position p ); position Parent ( position p ); Type GetData ( position p ); int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i ); Department of Computer Science & Technology, Nanjing Univ

7、ersity fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESLLRR Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES D

8、epartment of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES滿二叉樹滿二叉樹 完全二叉樹完全二叉樹 層次層次h，葉結點僅在，葉結點僅在 兩層出兩層出現現 對任一結點，若其右子樹的高度為對任一結點，若其右子樹的高度為k，則其左子樹的高度是，則其左子樹的高度是 h和和h-1 k or k+1 Departmen

9、t of Computer Science & Technology, Nanjing University fall DATA STRUCTURES23-124-1 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES123485679 10 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES123485679 10 Department

10、 of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate class BinaryTree public: BinaryTree ( ); /構造函數構造函數 BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /構造以構造以item為根，為根，lch和和rch為左、為左、右右 /子樹的二叉樹子樹的二叉樹 int IsEmpty ( ); /判二叉樹空否？判二叉樹空否？ BinTreeNode * Par

11、ent ( ); /雙親雙親 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES BinTreeNode * LeftChild ( ); /取左子女結點地址 BinTreeNode * RightChild ( ); /取右子女結點地址 int Insert ( const Type& item ); /插入 int Find ( const Type &item ) const; /搜索 Type GetData ( ) const; /取得結點數據

12、 BinTreeNode *GetRoot ( ) const; /取根結點地址 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES0 1 2 3 4 5 6 7 8 9 完全二叉樹0137894562 順序表示 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES0 1 2 3 5 6 7 8 9 11 13一般二叉樹的順序表示130265378

13、111 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES02614300261430 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESleftChild data rightChilddataleftChildrightChild二叉鏈表二叉樹的鏈表表示 Department of Computer Science & Technol

14、ogy, Nanjing University fall DATA STRUCTURESleftChild data parent rightChildparentdataleftChildrightChild三叉鏈表 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESABCDFEroot AABBCCDDFFEErootroot 二叉鏈表 三叉鏈表 Department of Computer Science & Technology, Nanjing Uni

15、versity fall DATA STRUCTURESABCDFErootdata parent leftChild rightChild012345 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate class BinaryTree;template Class BinTreeNode friend class BinaryTree;private: Type data; BinTreeNode * leftChild; BinTreeNode *

16、 rightChild; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Type

17、GetData ( ) const return data; BinTreeNode * GetLeft ( ) const return leftChild; BinTreeNode * GetRight ( ) const return rightChild; void SetData ( const Type& item ) data = item; Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES void SetLeft ( BinTreeNode

18、* L ) leftChild = L; void SetRight ( BinTreeNode * R ) rightChild = R; ;template class BinaryTree private: BinTreeNode *root; Type RefValue; void CreateBinTree ( ifstream& in, BinTreeNode * & current ); Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES

19、BinTreeNode * Parent ( BinTreeNode * subTree, BinTreeNode * current); int Insert (BinTreeNode * & subTree, const Type &item); /插入 void Traverse (BinTreeNode *subTree, ostream &out) const /遍歷 int Find (BinTreeNode *subTree, const Type &item) const/搜索 void destroy (BinTreeNode * subTre

20、e); /刪除 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Sc

21、ience & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing U

22、niversity fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES LRV Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURE

23、S Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate void BinaryTree : InOrder ( ) InOrder ( root );template void BinaryTree : PreOrder ( ) PreOrder ( root );templat

24、e void BinaryTree : PostOrder ( ) PostOrder ( root ); Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES關于樹的性質：關于樹的性質：1. 對于一棵具有對于一棵具有n個結點的樹，該樹中所個結點的樹，該樹中所有結點的度數之和為：有結點的度數之和為： 2. 假定一棵三叉樹的結點個數為假定一棵三叉樹的結點個數為50，則，則它的最小高度為它的最小高度為 ，最大高，最大高度為度為 。3. 在一棵二叉樹中，假定度為在一棵二叉樹中，

25、假定度為2的結點有的結點有5個，度為個，度為1的結點有的結點有6個，則葉子結點數個，則葉子結點數有有 個個n-14496 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate int BinaryTree : Count ( BinTreeNode * t ) const if ( t = NULL ) return 0; else return 1 + Count ( t-leftChild ) + Count ( t-rightChild ); Dep

26、artment of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES如圖所示的二叉樹的前序遍歷順序為如圖所示的二叉樹的前序遍歷順序為:A B C D E G F ABCDEGF Department of Computer Science & Technology, Nanjing University fal

27、l DATA STRUCTURES template void BinaryTree : CreateBinTree ( ifstream& in, BinTreeNode * & subTree ) /私有函數私有函數: 以遞歸方式建立二叉樹。以遞歸方式建立二叉樹。/輸入結點值的順序必須對應二叉樹結點前輸入結點值的順序必須對應二叉樹結點前/序遍歷的順序。并約定以輸入序列中不可序遍歷的順序。并約定以輸入序列中不可/能出現的值作為空結點的值以結束遞歸能出現的值作為空結點的值以結束遞歸,/此值在此值在RefValue中。例如用中。例如用“”或用或用“-1”/表示字符序列或正整數序列

28、空結點。表示字符序列或正整數序列空結點。 Type item; if ( !in.eof ( ) ) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES in item; /讀入根結點的值讀入根結點的值 if ( item != RefValue ) subTree = new BinTreeNode ( item );/建立根結點建立根結點 if ( subTree = NULL ) cerr “存儲分配錯存儲分配錯!” leftChild ); CreateBinT

29、ree ( in, subTree-rightChild ); else subTree = NULL; /封閉葉結點封閉葉結點 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法1 1）后序遍歷的非遞歸算法）后序遍歷的非遞歸算法struct STKNode BinTreeNode *ptr; senun tagL,R;/tag = L, 表示從左子樹退回還要遍歷右子表示從左子樹退回還要遍歷右子樹樹; /tag = R，表示從

30、右子樹退回要訪問根，表示從右子樹退回要訪問根結點。結點。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES算法思想：算法思想： 將棧將棧s初始化，然后令指針初始化，然后令指針p指向二叉樹的根結點，指向二叉樹的根結點，即即p=T. 如果指向根結點的指針不為空，先將如果指向根結點的指針不為空，先將tag置置L；再；再將將tag和根結點一起送入棧中；然后將指針指向該和根結點一起送入棧中；然后將指針指向該結點的左子樹根結點；繼續遍歷。結點的左子樹根結點；繼續遍歷。 如果指向根

31、結點的指針為空，則將棧頂存放的數如果指向根結點的指針為空，則將棧頂存放的數據項出棧，有兩種情況：據項出棧，有兩種情況： 若若tag=L,則改變則改變tag的值，將的值，將tag置置R；再把；再把tag和彈和彈出的結點重新入棧出的結點重新入棧 ；然后將指針指向該結點的右；然后將指針指向該結點的右子樹根結點，繼續遍歷。子樹根結點，繼續遍歷。若若tag=R，則訪問彈出的結點，并將彈出的指針置，則訪問彈出的結點，并將彈出的指針置為空為空 直到棧為空并且指針為空時，遍歷結束。直到棧為空并且指針為空時，遍歷結束。 Department of Computer Science & Technolog

32、y, Nanjing University fall DATA STRUCTUREStemplate void BinaryTree:PostOrder (void (*visit) (BinTreeNode *p) StackstkNode S; stkNode w; BinTreeNode * p = root; /p是遍歷指針是遍歷指針 do while (p != NULL) w.ptr = p; w.tag = L; S.Push (w); p = p-leftChild; int continue1 = 1; /繼續循環標記繼續循環標記, 用于用于R while (continue

33、1 & !S.IsEmpty () S.Pop (w); p = w.ptr; switch (w.tag) /判斷棧頂的判斷棧頂的tag標記標記 case L: w.tag = R; S.Push (w); continue1 = 0; p = p-rightChild; break; case R: visit (p); break; while (!S.IsEmpty ();/繼續遍歷其他結點繼續遍歷其他結點 cout endl; Department of Computer Science & Technology, Nanjing University fall DA

34、TA STRUCTURES另一版本實現另一版本實現:void postorder(BinTreeNode *T) stack STKNode s(10); STKNode Cnode; BinTreeNode *p=T; do while (p!=NULL) Cnode.ptr=p;Cnode.tag=L;s.push(Cnode); p=p-leftchild; Cnode=s.pop( );p=Cnode.ptr; Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES

35、while (Cnode.tag=R) coutdata; if (!s.IsEmpty( ) Cnode=s.pop( );p=Cnode.ptr; else return; Cnode.tag=R;s.push(Cnode); p=p-rightchild; while (p!=NULL |!s.IsEmpty( ) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaR

36、aRabcde Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESpostorder算法分析 時間復雜性時間復雜性入、出棧：入、出棧： O(n)訪問結點：訪問結點： O(n)總的時間復雜度：總的時間復雜度：O(n)空間復雜性空間復雜性O(k),k為樹的高度為樹的高度 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹遍歷的非遞歸算法二叉樹遍

37、歷的非遞歸算法(cont.)2 2）中序遍歷的非遞歸算法）中序遍歷的非遞歸算法棧中：用以存放待訪問的根結點指針棧中：用以存放待訪問的根結點指針, 以備在以備在訪問該結點的左子樹之后再訪問該結點及其訪問該結點的左子樹之后再訪問該結點及其右子樹。右子樹。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES算法思想算法思想 將棧將棧s初始化，令指針初始化，令指針p指向二叉樹的根結點，即指向二叉樹的根結點，即p=T.如果指向根結點的指針不為空或棧非空，則：如果指向根結點的指針不

38、為空或棧非空，則：(1) 如果指向根結點的指針非空，則將根結點指針如果指向根結點的指針非空，則將根結點指針進棧，然后將指針指向該結點的左子樹根結點，繼續進棧，然后將指針指向該結點的左子樹根結點，繼續遍歷遍歷 (2) 如果指向根結點的指針為空，則將棧頂存放的數如果指向根結點的指針為空，則將棧頂存放的數據項出棧，有兩種情況：據項出棧，有兩種情況：若從左子樹返回，則應該訪問當前層根結點，然后將若從左子樹返回，則應該訪問當前層根結點，然后將指針指向該結點的右子樹根結點，繼續遍歷；指針指向該結點的右子樹根結點，繼續遍歷； 若從右子樹返回，則表明當前層遍歷結束，應該繼若從右子樹返回，則表明當前層遍歷結束，

39、應該繼續退棧。續退棧。(3)當指針為空并且棧為空時，遍歷結束。當指針為空并且棧為空時，遍歷結束。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESvoid inorder (BinTreeNode *T) stack BinTreeNode * s(10); BinTreeNode *p=T; while (p|!s.IsEmpty( ) while (p!=NULL) s.push(p); p=p-leftchild; if (!s.IsEmpty( ) p=s.p

40、op( ); coutdata; p=p-rightchild; else return; Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESacdebaadaa左空左空 退棧退棧訪問訪問左空左空 退棧退棧訪問訪問退棧退棧訪問訪問左空左空ec退棧訪問退棧訪問cc右空右空 退棧訪問退棧訪問 棧空結束棧空結束abcde利用棧的中序遍歷非遞歸算法利用棧的中序遍歷非遞歸算法 Department of Computer Science & Technology, Nan

41、jing University fall DATA STRUCTURESinorder算法分析 時間復雜性時間復雜性入、出棧：入、出棧：訪問結點：訪問結點：總的時間復雜度：總的時間復雜度：O(n)O(n)O(n)空間復雜性空間復雜性O(k),k為樹的高度為樹的高度 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法(cont.)3 3）前序遍歷的非遞歸算法）前序遍歷的非遞歸算法需要棧嗎？需要棧嗎？棧中結點的棧中結點的pop和和

42、push Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES訪問訪問p-data后，將后，將p入棧，遍歷左子樹；遍入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素歷完左子樹返回時，棧頂元素p出棧，再先序出棧，再先序遍歷遍歷p的右子樹。的右子樹。訪問訪問p-data后，將后，將p-rchild入棧，遍歷左子入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素樹；遍歷完左子樹返回時，棧頂元素p-rchild出棧，遍歷以該指針為根的子樹。出棧，遍歷以該指針為根的子樹。算法思想算法思想

43、兩種方法：假設兩種方法：假設p是要遍歷樹的根指針，若是要遍歷樹的根指針，若p != NULL Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREStemplate void BinaryTree:PreOrder (void (*visit) (BinTreeNode *t) ) stackBinTreeNode* S; BinTreeNode *p = root; S.Push (NULL); while (p != NULL) visit(p); /訪問結點訪問結點

44、if (p-rightChild != NULL) S.Push (p-rightChild); /預留右指針在棧中預留右指針在棧中 if (p-leftChild != NULL) p = p-leftChild;/進左子樹進左子樹 else S.Pop(p);/左子樹為空左子樹為空 ; Department of Computer Science & Technology, Nanjing University fall DATA STRUCTUREScabcdedcc訪問訪問a進棧進棧c左進左進b訪問訪問b進棧進棧d左進左進空空退棧退棧d訪問訪問d左進左進空空退棧退棧c訪問訪問c

45、左進左進e訪問訪問e左進左進空空棧空?？战Y束結束利用棧的前序遍歷非遞歸算法利用棧的前序遍歷非遞歸算法 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES遍歷順序遍歷順序abcdef層次序遍歷二叉樹的算法層次序遍歷二叉樹的算法n層次序遍歷二叉樹就是從根結點開始，按層層次序遍歷二叉樹就是從根結點開始，按層次逐層遍歷次逐層遍歷 Department of Computer Science & Technology, Nanjing University fall DA

46、TA STRUCTURESn這種遍歷需要使用一個先進先出的隊列，這種遍歷需要使用一個先進先出的隊列，在處理上一層時，將其下一層的結點直接在處理上一層時，將其下一層的結點直接進到隊列（的隊尾）。在上一層結點遍歷進到隊列（的隊尾）。在上一層結點遍歷完后，下一層結點正好處于隊列的隊頭，完后，下一層結點正好處于隊列的隊頭，可以繼續訪問它們?？梢岳^續訪問它們。n算法是非遞歸的。算法是非遞歸的。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESabcdeQa訪問訪問a, 進隊進隊

47、Qa出隊出隊訪問訪問b, 進隊進隊訪問訪問c, 進隊進隊bcQb出隊出隊訪問訪問d, 進隊進隊cdQc出隊出隊訪問訪問e, 進隊進隊deQd出隊出隊eQe出隊出隊 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES層次序遍歷的（非遞歸）算法層次序遍歷的（非遞歸）算法template void BinaryTree:levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBinTre

48、eNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-leftChild != NULL) visit (p-leftChild); Q.EnQueue (p-leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ; Department of Computer Science & Technology, Nanjing

49、University fall DATA STRUCTURES二叉樹的建立二叉樹的建立 通過算法遞歸地實現通過算法遞歸地實現 已知一棵二叉樹的前序序列和中序序列，已知一棵二叉樹的前序序列和中序序列，可以唯一地確定一棵二叉樹；可以唯一地確定一棵二叉樹； 已知一棵二叉樹的中序序列和后序序列，已知一棵二叉樹的中序序列和后序序列，可以唯一地確定一棵二叉樹；可以唯一地確定一棵二叉樹； 由廣義表建立由廣義表建立 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES由前序序列和中序序列

50、，建立二叉樹的遞歸算法由前序序列和中序序列，建立二叉樹的遞歸算法private:BinTreeNode * CreateBT(string pres,ins)int Inpos; string Prestemp,Instemp;if (pres.length( )=0) T=NULL;else temp=new BinTreeNode; temp-data=pres.ch0; Inspos=0; while (Ins.chInpos!=T-data) Inpos+; Department of Computer Science & Technology, Nanjing Univers

51、ity fall DATA STRUCTURES prestemp=pres(1,Inpos); Instemp=ins(0,Inpos-1); temp-leftchild=CreateBT(prestemp,Instemp); prestemp=pres(Inpos+1,pres.length( )-Inpos-1); Instemp=Ins(Inpos+1,pres.length( )-Inpos-1); temp-rightchild=CreateBT(prestemp,Instemp); return temp; Department of Computer Science &

52、; Technology, Nanjing University fall DATA STRUCTURES由廣義表建立二叉樹由廣義表建立二叉樹A(B(C,F(H),D(E(,F)廣義表廣義表 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹對應的廣義表有如下規定：二叉樹對應的廣義表有如下規定： 每棵樹的根結點作為由子樹構成的表的名每棵樹的根結點作為由子樹構成的表的名字而放在表的前面；字而放在表的前面； 每一個結點的左右子樹用每一個結點的左右子樹用“,”分開，若只

53、分開，若只有右子樹而沒有左子樹，則逗號不能省略；有右子樹而沒有左子樹，則逗號不能省略； 在廣義表后面加一特殊符號在廣義表后面加一特殊符號作為結作為結束標志。束標志。A(B(C,F(H),D(E(,F) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES算法思想：算法思想： 遇到字母，則表明是結點的值，為它建立新結遇到字母，則表明是結點的值，為它建立新結點；點； 若該結點不是整個樹的根，還應該作為左子女若該結點不是整個樹的根，還應該作為左子女（k=1）或右子女（）或右子女

54、（k=2）鏈接到其雙親結點；）鏈接到其雙親結點； 遇到遇到“(”, 則表明子表開始，把剛剛建立的結則表明子表開始，把剛剛建立的結點的指針進棧（為了括號內孩子結點指向雙親結點的指針進棧（為了括號內孩子結點指向雙親結點用，并置點用，并置k=1） 遇到遇到“)”, 則表明子表結束，應退棧則表明子表結束，應退棧遇到遇到“,”,表示以左孩子為根的子樹已處理完畢，表示以左孩子為根的子樹已處理完畢，應接著處理以右孩子為根的子樹，應接著處理以右孩子為根的子樹，k=2A(B(C,F(H),D(E(,F) Department of Computer Science & Technology, Nanji

55、ng University fall DATA STRUCTURESvoid CreateBT(BTreeNode *BT, char *a)/a為廣義表為廣義表表示表示 BinTreeNode *s10;/作為存儲二叉樹中根結點指作為存儲二叉樹中根結點指針的棧使用針的棧使用 int top=-1; BT=NULL; BinTreeNode *p; int k;/k=1,處理左子樹；處理左子樹；k=2，處理右子樹，處理右子樹 istrstream ins(a);/ 把字符串把字符串a定義為輸入字符串流定義為輸入字符串流對象對象ins char ch; insch; while (ch!=) 具

56、體算法具體算法: Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES switch (ch) case(: top+;stop=p;k=1;break; case ): top-;break; case ,: k=2;break; default: p=new BinTreeNode; p-data=ch;p-leftchild=p-rightchild=NULL; if (BT=NULL) BT=p; else if (k=1) stop-leftchild=p; e

57、lse stop-rightchild=p; /switch end insch;/while end A(B(C,F(H),D(E(,F) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹的計數有有n個結點的不同的二叉樹有多少種？個結點的不同的二叉樹有多少種？ Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES612345789前序排列

58、：前序排列：1 2 3 4 5 6 7 8 9中序排列：中序排列：3 2 5 4 1 6 8 7 9612375849前序排列：前序排列：1 2 3 4 5 6 7 8 9中序排列：中序排列：4 3 5 2 1 7 6 8 9 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES如果我們能夠做到結點編號的前序排列正好如果我們能夠做到結點編號的前序排列正好是是1,2,3,n,1,2,3,n,那么，這棵二叉樹有多少中那么，這棵二叉樹有多少中序排列，就能確定多少棵不同的二叉樹。

59、序排列，就能確定多少棵不同的二叉樹。當二叉樹的前序排列為當二叉樹的前序排列為1,2,3,n1,2,3,n時，時，可能有多少種中序排列？可能有多少種中序排列？ Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES123123123123123若用若用 表示進棧表示進棧表示出棧表示出棧 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESb0 =1b1

60、=1b2 =2b3 =5求解不同的二叉樹棵數求解不同的二叉樹棵數設設bn表示有表示有n個結點的不同的二叉樹棵數。個結點的不同的二叉樹棵數。當當n很小時，很小時， Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES!)!(211112nnnnnbCnnn1101niininbbb512345641131363Cb141234567851141484Cb Department of Computer Science & Technology, Nanjing Uni

61、versity fall DATA STRUCTURES5.5 5.5 線索二叉樹線索二叉樹 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES兩種方法：兩種方法：1）原有二叉樹的結構中，增加兩個鏈域；）原有二叉樹的結構中，增加兩個鏈域；2）利用空鏈域）利用空鏈域 如果結點有左孩子，則其如果結點有左孩子，則其leftchild指示其左孩子；否則指示指示其左孩子；否則指示其前驅其前驅如果結點有右孩子，則其如果結點有右孩子，則其rightchild指示其右孩子；否則指指示其右孩子；否則指