文稿數(shù)據(jù)結(jié)構(gòu)2009級(jí)chapterTechnology

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

2、 n (n0) 個(gè)元素組個(gè)元素組成的有限非空集合，稱為頂點(diǎn)集合。成的有限非空集合，稱為頂點(diǎn)集合。E = (vi, vj) | vi, vj V, 1i, jn 是是n-1個(gè)序?qū)Φ募?，稱為邊個(gè)序?qū)Φ募希Q為邊集合，集合，E 中的元素中的元素 (vi, vj）稱為邊或分支。）稱為邊或分支。 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES自由樹(shù) Department of Computer Science & Technology, Nanjing Unive

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

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

5、Computer Science & Technology, Nanjing University fall DATA STRUCTURES0層層1層層3層層2層層height= 3ACGBDEFKLHMIJ術(shù)語(yǔ)術(shù)語(yǔ) 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滿二叉樹(shù)滿二叉樹(shù) 完全二叉樹(shù)完全二叉樹(shù) 層次層次h，葉結(jié)點(diǎn)僅在，葉結(jié)點(diǎn)僅在 兩層出兩層出現(xiàn)現(xiàn) 對(duì)任一結(jié)點(diǎn)，若其右子樹(shù)的高度為對(duì)任一結(jié)點(diǎn)，若其右子樹(shù)的高度為k，則其左子樹(shù)的高度是，則其左子樹(shù)的高度是 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 ( ); /構(gòu)造函數(shù)構(gòu)造函數(shù) BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /構(gòu)造以構(gòu)造以item為根，為根，lch和和rch為左、為左、右右 /子樹(shù)的二叉樹(shù)子樹(shù)的二叉樹(shù) int IsEmpty ( ); /判二叉樹(shù)空否？判二叉樹(shù)空否？ BinTreeNode * Par

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

12、 BinTreeNode *GetRoot ( ) const; /取根結(jié)點(diǎn)地址 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES0 1 2 3 4 5 6 7 8 9 完全二叉樹(shù)0137894562 順序表示 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES0 1 2 3 5 6 7 8 9 11 13一般二叉樹(shù)的順序表示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二叉鏈表二叉樹(shù)的鏈表表示 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關(guān)于樹(shù)的性質(zhì)：關(guān)于樹(shù)的性質(zhì)：1. 對(duì)于一棵具有對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為：有結(jié)點(diǎn)的度數(shù)之和為： 2. 假定一棵三叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為假定一棵三叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為50，則，則它的最小高度為它的最小高度為 ，最大高，最大高度為度為 。3. 在一棵二叉樹(shù)中，假定度為在一棵二叉樹(shù)中，

25、假定度為2的結(jié)點(diǎn)有的結(jié)點(diǎn)有5個(gè)，度為個(gè)，度為1的結(jié)點(diǎn)有的結(jié)點(diǎn)有6個(gè)，則葉子結(jié)點(diǎn)數(shù)個(gè)，則葉子結(jié)點(diǎn)數(shù)有有 個(gè)個(gè)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如圖所示的二叉樹(shù)的前序遍歷順序?yàn)槿鐖D所示的二叉樹(shù)的前序遍歷順序?yàn)?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 ) /私有函數(shù)私有函數(shù): 以遞歸方式建立二叉樹(shù)。以遞歸方式建立二叉樹(shù)。/輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)前輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)前/序遍歷的順序。并約定以輸入序列中不可序遍歷的順序。并約定以輸入序列中不可/能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,/此值在此值在RefValue中。例如用中。例如用“”或用或用“-1”/表示字符序列或正整數(shù)序列

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

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

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

31、結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)如果指向根結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)據(jù)項(xiàng)出棧，有兩種情況：據(jù)項(xiàng)出棧，有兩種情況： 若若tag=L,則改變則改變tag的值，將的值，將tag置置R；再把；再把tag和彈和彈出的結(jié)點(diǎn)重新入棧出的結(jié)點(diǎn)重新入棧 ；然后將指針指向該結(jié)點(diǎn)的右；然后將指針指向該結(jié)點(diǎn)的右子樹(shù)根結(jié)點(diǎn)，繼續(xù)遍歷。子樹(shù)根結(jié)點(diǎn)，繼續(xù)遍歷。若若tag=R，則訪問(wèn)彈出的結(jié)點(diǎn)，并將彈出的指針置，則訪問(wèn)彈出的結(jié)點(diǎn)，并將彈出的指針置為空為空 直到棧為空并且指針為空時(shí)，遍歷結(jié)束。直到棧為空并且指針為空時(shí)，遍歷結(jié)束。 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; /繼續(xù)循環(huán)標(biāo)記繼續(xù)循環(huán)標(biāo)記, 用于用于R while (continue

33、1 & !S.IsEmpty () S.Pop (w); p = w.ptr; switch (w.tag) /判斷棧頂?shù)呐袛鄺ｍ數(shù)膖ag標(biāo)記標(biāo)記 case L: w.tag = R; S.Push (w); continue1 = 0; p = p-rightChild; break; case R: visit (p); break; while (!S.IsEmpty ();/繼續(xù)遍歷其他結(jié)點(diǎn)繼續(xù)遍歷其他結(jié)點(diǎn) cout endl; Department of Computer Science & Technology, Nanjing University fall DA

34、TA STRUCTURES另一版本實(shí)現(xiàn)另一版本實(shí)現(xiàn):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算法分析 時(shí)間復(fù)雜性時(shí)間復(fù)雜性入、出棧：入、出棧： O(n)訪問(wèn)結(jié)點(diǎn)：訪問(wèn)結(jié)點(diǎn)： O(n)總的時(shí)間復(fù)雜度：總的時(shí)間復(fù)雜度：O(n)空間復(fù)雜性空間復(fù)雜性O(shè)(k),k為樹(shù)的高度為樹(shù)的高度 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹(shù)遍歷的非遞歸算法二叉樹(shù)遍

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

38、為空或棧非空，則：(1) 如果指向根結(jié)點(diǎn)的指針?lè)强?，則將根結(jié)點(diǎn)指針如果指向根結(jié)點(diǎn)的指針?lè)强?，則將根結(jié)點(diǎn)指針進(jìn)棧，然后將指針指向該結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)，繼續(xù)進(jìn)棧，然后將指針指向該結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)，繼續(xù)遍歷遍歷 (2) 如果指向根結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)如果指向根結(jié)點(diǎn)的指針為空，則將棧頂存放的數(shù)據(jù)項(xiàng)出棧，有兩種情況：據(jù)項(xiàng)出棧，有兩種情況：若從左子樹(shù)返回，則應(yīng)該訪問(wèn)當(dāng)前層根結(jié)點(diǎn)，然后將若從左子樹(shù)返回，則應(yīng)該訪問(wèn)當(dāng)前層根結(jié)點(diǎn)，然后將指針指向該結(jié)點(diǎn)的右子樹(shù)根結(jié)點(diǎn)，繼續(xù)遍歷；指針指向該結(jié)點(diǎn)的右子樹(shù)根結(jié)點(diǎn)，繼續(xù)遍歷； 若從右子樹(shù)返回，則表明當(dāng)前層遍歷結(jié)束，應(yīng)該繼若從右子樹(shù)返回，則表明當(dāng)前層遍歷結(jié)束，

39、應(yīng)該繼續(xù)退棧。續(xù)退棧。(3)當(dāng)指針為空并且棧為空時(shí)，遍歷結(jié)束。當(dāng)指針為空并且棧為空時(shí)，遍歷結(jié)束。 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左空左空 退棧退棧訪問(wèn)訪問(wèn)左空左空 退棧退棧訪問(wèn)訪問(wèn)退棧退棧訪問(wèn)訪問(wèn)左空左空ec退棧訪問(wèn)退棧訪問(wèn)cc右空右空 退棧訪問(wèn)退棧訪問(wèn) ?？战Y(jié)束棧空結(jié)束abcde利用棧的中序遍歷非遞歸算法利用棧的中序遍歷非遞歸算法 Department of Computer Science & Technology, Nan

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

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

43、兩種方法：假設(shè)兩種方法：假設(shè)p是要遍歷樹(shù)的根指針，若是要遍歷樹(shù)的根指針，若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); /訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn)

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

45、左進(jìn)左進(jìn)e訪問(wèn)訪問(wèn)e左進(jìn)左進(jìn)空空?？諚？战Y(jié)束結(jié)束利用棧的前序遍歷非遞歸算法利用棧的前序遍歷非遞歸算法 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES遍歷順序遍歷順序abcdef層次序遍歷二叉樹(shù)的算法層次序遍歷二叉樹(shù)的算法n層次序遍歷二叉樹(shù)就是從根結(jié)點(diǎn)開(kāi)始，按層層次序遍歷二叉樹(shù)就是從根結(jié)點(diǎn)開(kāi)始，按層次逐層遍歷次逐層遍歷 Department of Computer Science & Technology, Nanjing University fall DA

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

47、Qa出隊(duì)出隊(duì)訪問(wèn)訪問(wèn)b, 進(jìn)隊(duì)進(jìn)隊(duì)訪問(wèn)訪問(wèn)c, 進(jìn)隊(duì)進(jìn)隊(duì)bcQb出隊(duì)出隊(duì)訪問(wèn)訪問(wèn)d, 進(jìn)隊(duì)進(jìn)隊(duì)cdQc出隊(duì)出隊(duì)訪問(wèn)訪問(wèn)e, 進(jìn)隊(duì)進(jìn)隊(duì)deQd出隊(duì)出隊(duì)eQe出隊(duì)出隊(duì) 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二叉樹(shù)的建立二叉樹(shù)的建立 通過(guò)算法遞歸地實(shí)現(xiàn)通過(guò)算法遞歸地實(shí)現(xiàn) 已知一棵二叉樹(shù)的前序序列和中序序列，已知一棵二叉樹(shù)的前序序列和中序序列，可以唯一地確定一棵二叉樹(shù)；可以唯一地確定一棵二叉樹(shù)； 已知一棵二叉樹(shù)的中序序列和后序序列，已知一棵二叉樹(shù)的中序序列和后序序列，可以唯一地確定一棵二叉樹(shù)；可以唯一地確定一棵二叉樹(shù)； 由廣義表建立由廣義表建立 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES由前序序列和中序序列

50、，建立二叉樹(shù)的遞歸算法由前序序列和中序序列，建立二叉樹(shù)的遞歸算法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由廣義表建立二叉樹(shù)由廣義表建立二叉樹(shù)A(B(C,F(H),D(E(,F)廣義表廣義表 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES二叉樹(shù)對(duì)應(yīng)的廣義表有如下規(guī)定：二叉樹(shù)對(duì)應(yīng)的廣義表有如下規(guī)定： 每棵樹(shù)的根結(jié)點(diǎn)作為由子樹(shù)構(gòu)成的表的名每棵樹(shù)的根結(jié)點(diǎn)作為由子樹(shù)構(gòu)成的表的名字而放在表的前面；字而放在表的前面； 每一個(gè)結(jié)點(diǎn)的左右子樹(shù)用每一個(gè)結(jié)點(diǎn)的左右子樹(shù)用“,”分開(kāi)，若只

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

54、（k=2）鏈接到其雙親結(jié)點(diǎn)；）鏈接到其雙親結(jié)點(diǎn)； 遇到遇到“(”, 則表明子表開(kāi)始，把剛剛建立的結(jié)則表明子表開(kāi)始，把剛剛建立的結(jié)點(diǎn)的指針進(jìn)棧（為了括號(hào)內(nèi)孩子結(jié)點(diǎn)指向雙親結(jié)點(diǎn)的指針進(jìn)棧（為了括號(hào)內(nèi)孩子結(jié)點(diǎn)指向雙親結(jié)點(diǎn)用，并置點(diǎn)用，并置k=1） 遇到遇到“)”, 則表明子表結(jié)束，應(yīng)退棧則表明子表結(jié)束，應(yīng)退棧遇到遇到“,”,表示以左孩子為根的子樹(shù)已處理完畢，表示以左孩子為根的子樹(shù)已處理完畢，應(yīng)接著處理以右孩子為根的子樹(shù)，應(yīng)接著處理以右孩子為根的子樹(shù)，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;/作為存儲(chǔ)二叉樹(shù)中根結(jié)點(diǎn)指作為存儲(chǔ)二叉樹(shù)中根結(jié)點(diǎn)指針的棧使用針的棧使用 int top=-1; BT=NULL; BinTreeNode *p; int k;/k=1,處理左子樹(shù)；處理左子樹(shù)；k=2，處理右子樹(shù)，處理右子樹(shù) istrstream ins(a);/ 把字符串把字符串a(chǎn)定義為輸入字符串流定義為輸入字符串流對(duì)象對(duì)象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二叉樹(shù)的計(jì)數(shù)有有n個(gè)結(jié)點(diǎn)的不同的二叉樹(shù)有多少種？個(gè)結(jié)點(diǎn)的不同的二叉樹(shù)有多少種？ 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如果我們能夠做到結(jié)點(diǎn)編號(hào)的前序排列正好如果我們能夠做到結(jié)點(diǎn)編號(hào)的前序排列正好是是1,2,3,n,1,2,3,n,那么，這棵二叉樹(shù)有多少中那么，這棵二叉樹(shù)有多少中序排列，就能確定多少棵不同的二叉樹(shù)。

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

60、=1b2 =2b3 =5求解不同的二叉樹(shù)棵數(shù)求解不同的二叉樹(shù)棵數(shù)設(shè)設(shè)bn表示有表示有n個(gè)結(jié)點(diǎn)的不同的二叉樹(shù)棵數(shù)。個(gè)結(jié)點(diǎn)的不同的二叉樹(shù)棵數(shù)。當(dāng)當(dāng)n很小時(shí)，很小時(shí)， 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 線索二叉樹(shù)線索二叉樹(shù) Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES兩種方法：兩種方法：1）原有二叉樹(shù)的結(jié)構(gòu)中，增加兩個(gè)鏈域；）原有二叉樹(shù)的結(jié)構(gòu)中，增加兩個(gè)鏈域；2）利用空鏈域）利用空鏈域 如果結(jié)點(diǎn)有左孩子，則其如果結(jié)點(diǎn)有左孩子，則其leftchild指示其左孩子；否則指示指示其左孩子；否則指示其前驅(qū)其前驅(qū)如果結(jié)點(diǎn)有右孩子，則其如果結(jié)點(diǎn)有右孩子，則其rightchild指示其右孩子；否則指指示其右孩子；否則指