數(shù)據(jù)結(jié)構(gòu)講義

1、Chapter 06 Tree and binary tree第六章 樹和二叉樹Prof. Qing Wang共一百八十三頁Prof. Q. Wang本章學習(xux)的線索主要線索重點(zhngdin)樹和二叉樹的定義及表示二叉樹的遍歷樹、森林和二叉樹的轉(zhuǎn)換哈夫曼樹和哈夫曼編碼 難點 二叉樹的遍歷及線索化樹和二叉樹的定義和表示二叉樹的遍歷（遞歸和非遞歸）及線索化樹、森林和二叉樹的轉(zhuǎn)換哈夫曼樹和哈夫曼編碼共一百八十三頁Prof. Q. WangContentsDefinition and notations of Tree and ForestNotations and representat

2、ion of binary treeBinary tree traversalThreading binary treeReconstruction of binary treeTransformation among Tree, Forest and binary treeHuffman tree and Huffman coding共一百八十三頁Prof. Q. Wang6.1 Definition and notations of Tree A tree is a set of n nodes. If n=0, it is a NULL tree. If n0, then 1. It h

3、as a so-called “root” node which only has successors and without predecessor. 2. Except the root, the remainders can be partitioned into m (m0) un-overlapped subsets T1,T2, Tm, each of which is also a tree. They are called the sub-trees of the root. Note: The root of the tree has no predecessor and

4、0 to m successors (sub trees).6.1.1 Definition of Tree共一百八十三頁Prof. Q. Wang基本操作：InitTree(&T);DestroyTree(&T);CreateTree(&T);ClearTree(&T);TreeEmpty(T);TreeDepth(T);Root(T);Value(T, cur_e);Assign(T, cur_e, value);Parent(T, cur_e);LeftChild(T, cur_e);RightSibling(T, cur_e);InsertChild(&T, &p, i, c);Del

5、eteChild(&T, &p, i);TravseTree(T, visit(); ADT描述參見(cnjin)課本 pp118共一百八十三頁Prof. Q. WangTree formGeneral list form(A(B(E(K,L),F), C(G), D(H(M),I,J)Representations of tree I JFKLGMCHDBEAWen GraphRetraction formABCDEFGHIJKLMABDEIJFCGH共一百八十三頁Prof. Q. Wang6.1.2 NotationsNode (結(jié)點)：包含一個數(shù)據(jù)元素及若干指向其子樹的分支。Leaf (

6、樹葉)、Branch node(分支結(jié)點)Parent node (父結(jié)點)、child node(子結(jié)點)Edge (邊) ：父結(jié)點x到子結(jié)點y的有序?qū)?Sibling (兄弟) ：同一雙親的孩子Ancestor (祖先(zxin) 、offspring (子孫)：堂兄弟：雙親在同一層的結(jié)點Layer (結(jié)點的層數(shù)、樹的層數(shù))：規(guī)定根的層數(shù)為1Degree (結(jié)點的度、樹的度)：結(jié)點擁有的子樹數(shù)目Depth (樹的高度或深度)：樹中結(jié)點的最大層次稱為樹的深度Path and Path length (路徑和路徑長度)ABCDEFGHIJKL共一百八十三頁Prof. Q. WangExampl

7、es12344共一百八十三頁Prof. Q. WangA set of trees. 森林是m (m=0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。就邏輯結(jié)構(gòu)而言，任何一棵樹是一個二元組Tree=(root, F)，其中root稱為樹的根結(jié)點；F是m (m=0)棵子(k zi)樹構(gòu)成的森林，F(xiàn)=(T1, T2,Tm), 其中Ti=(ri, Fi)稱作根root的第i棵子樹；當m0時，在樹根和其子樹森林之間存在下列關(guān)系:由這個定義，可以得到森林和二叉樹之間轉(zhuǎn)換的遞歸定義。6.1.3 Forest (Orchard)RF= | i=1,2,m, m0共一百八十三頁Prof.

8、Q. Wang6.1.4 Basic functions for the tree樹的基本運算通常有以下幾種：1. Initialization - 創(chuàng)建一棵空樹；2. IsEmpty - 判斷某棵樹是否為空；3. GetRoot - 求樹中的根結(jié)點，若為空樹，則返回一特殊值；4. GetParent - 求樹中某個指定結(jié)點的父結(jié)點，當指定結(jié)點為根時，返回一特殊值；5. GetFirstChild - 求樹中某個指定結(jié)點的最左子結(jié)點，當指定結(jié)點為樹葉時，它沒有子女，則返回一特殊值；6. GetRightSibling - 求樹中某個指定結(jié)點的右兄弟(xingd)結(jié)點，當指定結(jié)點沒有右兄弟(xi

9、ngd)時，返回一特殊值；7. Traversal - 樹的遍歷（周游），即按某種方式訪問樹中的所有結(jié)點，并使每個結(jié)點恰好被訪問一次。共一百八十三頁Prof. Q. WangDiscussionStorage structure of treeGeneral list共一百八十三頁Prof. Q. WangDiscussionStorage structure of treeFixed multiple-branch listNumber of branch：trees degreeNull Pointer？Variable multiple-branch listNumber of bran

10、ch：nodes degree data child1child2child3childd共一百八十三頁Prof. Q. WangBinary Tree (二叉樹)：它的每一個結(jié)點至多有兩棵子樹（也是二叉樹），并且子樹有 左右 之分，其次序不能隨意顛倒(dindo)。二叉樹的5種基本形態(tài)：ADT描述參見課本 pp121。6.2.1 Basic notations6.2 Binary tree共一百八十三頁InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T, definition);ClearBiTree(&T);BiTreeEmpty (T);Bi

11、TreeDepth(T);Root(T);Value(T, e);Assign(T, e,value);Parent(T, e);LeftChild(T, e);RightChild(T, e);LeftSibling(T, e);RightSibling(T, e);InsertChild(T, p, LR, c);DeleteChild(T, p, LR);PreOrderTravse(T, visit();InOrderTravse(T, visit();PostOrderTravse(T, visit();LevelOrderTravse(T, visit(); ADT描述參見(cnj

12、in)課本 pp121Prof. Q. Wang共一百八十三頁Prof. Q. WangExamples of binary treeBinary tree = (Root, Left sub binary tree, Right sub binary tree)共一百八十三頁Prof. Q. Wang二叉樹不是樹的特殊情形，盡管樹和二叉樹的概念之間有許多類似，但它們是兩個概念。樹和二叉樹之間最主要的差別是：Full binary tree (滿二叉樹)：如果一棵二叉樹的任何結(jié)點或者(huzh)是樹葉，或有兩棵結(jié)構(gòu)完全相同的非空子樹，則此二叉樹稱作“滿二叉樹”（離散數(shù)學中稱此樹是“正則的”）。

13、 Complete binary tree (完全二叉樹)：如果一棵二叉樹至多只有最下面的兩層結(jié)點度數(shù)可以小于2（度為1的結(jié)點只能在倒數(shù)第二層），并且最下面一層的結(jié)點（葉子）都集中在該層最左邊的若干位置上，則此二叉樹稱為“完全二叉樹”。完全二叉樹不一定是滿二叉樹。二叉樹中結(jié)點的子樹要區(qū)分為左子樹和右子樹，即使(jsh)在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。共一百八十三頁Prof. Q. WangFull binary treeComplete binary treeABCDEFGHIGeneric binary treeABCFGDEABCFGDEHIJ共一百八十三頁

14、Prof. Q. Wang(1) Suppose that binary tree is leveled from 1, there are at most 2i-1 nodes at the level i (i1).在二叉樹的第i層上至多有2i-1個結(jié)點(ji din)（i 1）?？梢杂脷w納法證明。(2) If the height of binary tree is k (k 1), the number of nodes is at most 2k-1.深度為k的二叉樹至多有2k-1個結(jié)點（k=1）。6.2.2 Characteristics of binary tree2021222

15、k-12k-1Level 1Level 2Level 3Level k共一百八十三頁Prof. Q. Wang(3) In binary tree, if the number of leaves is n0, and the number of nodes with left and right children is n2, then n0n21對任何一棵二叉樹T，如果(rgu)其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。6.2.2 Characteristics of binary tree證明： 設(shè)n1為二叉樹中度為1的結(jié)點數(shù)。則有，n=n0+n1+n2 再看二叉樹中的

16、分支數(shù)。除了根結(jié)點外，其余結(jié)點都有一個分支進入，設(shè)B為分支總數(shù)，則n=B+1。由于(yuy)這些分支都是由分支為1或2的結(jié)點發(fā)出的，因此有： B=n1+2n2于是有n=n1+2n2+1n1+2n2+1=n0+n1+n2 =n0=n2+1共一百八十三頁Prof. Q. Wang(4) The depth of the complete binary tree with n nodes is具有n個結(jié)點(ji din)的完全二叉樹的深度為證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有2k-1-1 n = 2k-1 或 2k-1 = n 2k于是(ysh) k-1=log2n k因k是整數(shù)，所

17、以共一百八十三頁Prof. Q. Wang(5) 如果對一棵有n個結(jié)點的完全二叉樹按層序從1開始編號(bin ho)，則對任一結(jié)點i（1=i1, 則其雙親結(jié)點是 i/2 ； b）如果2in, 則結(jié)點i無左孩子；否則其左孩子是結(jié)點2i； c）如果2i+1n, 則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1。123456789101112131415123456789101112共一百八十三頁Prof. Q. WangExtended binary tree (擴充二叉樹 )：對一個二叉樹進行“擴充”，可得到擴充的二叉樹。擴充的方法(fngf)是：把原二叉樹的結(jié)點都變?yōu)槎葦?shù)為2的分支結(jié)點，也就是說，

18、如果原結(jié)點的度數(shù)為2，則不變，度數(shù)為1，則增加一個分支，度數(shù)為0 (樹葉)增加兩個分支。 在擴充的二叉樹里外部結(jié)點 (葉結(jié)點)都是新增加的結(jié)點。如果原二叉樹有n個結(jié)點，在擴充的二叉樹里這n個結(jié)點的度數(shù)都是2。因此擴充的二叉樹有2n條邊，2n+1個結(jié)點，除n個原來二叉樹結(jié)點，還有n+1個是新增加的外部結(jié)點，也就是說：在擴充的二叉樹里，新增加的外部結(jié)點的個數(shù)比原來的內(nèi)部結(jié)點個數(shù)多1。 abcdefabcdef1234675共一百八十三頁Prof. Q. Wang“外部(wib)路徑長度”E：在擴充的二叉樹里從根到每個外部結(jié)點的路徑長度之和?！皟?nèi)部路徑長度”I：在擴充的二叉樹里從根到每個內(nèi)部結(jié)點的路

19、徑長度之和。 關(guān)系：E = I + 2nE=21, I=9, n=6請證明上述關(guān)系式。abcdef1234675共一百八十三頁Prof. Q. Wang6.2.3 Basic functions for binary tree 二叉樹的基本運算通常有以下幾種： 1. Initialization - 創(chuàng)建一棵空二叉樹； 2. IsEmpty - 判斷某棵二叉樹是否為空； 3. GetRoot -求二叉樹中的根結(jié)點，若為空二叉樹，則返回一特殊值； 4. GetParent - 求二叉樹中某個指定結(jié)點的父結(jié)點，當指定結(jié)點為根時，返回一特殊值； 5. GetLeftChild - 求二叉樹中某個指定

20、結(jié)點的左子女結(jié)點，當指定結(jié)點沒有左子女時，返回一特殊值； 6. GetRightChild - 求二叉樹中某個指定結(jié)點的右子女結(jié)點，當指定結(jié)點沒有右子女時，返回一特殊值； 7. Traversal - 二叉樹的遍歷(bin l)，即按某種方式訪問二叉樹中的所有結(jié)點，并使每個結(jié)點僅僅被訪問一次。共一百八十三頁Prof. Q. Wang用一組地址連續(xù)(linx)的存儲單元依次自上而下、自左而右存儲完全二叉樹的結(jié)點。對于一般樹，則應(yīng)將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組的相應(yīng)分量中。6.3 Storage of Binary Tree6.3.1 Sequential formABCD

21、EFGABCDEFGABCDEFG0順序(shnx)表共一百八十三頁Prof. Q. Wang/Declaration#define MAXNODE 100 /* 定義二叉樹中結(jié)點(ji din)的最大個數(shù) */typedef struct SeqBTree /* 順序二叉樹類型定義 */DataType nodelistMAXNODE+1;int n;/* 改造成完全二叉樹后，結(jié)點的個數(shù) */SeqBTree, *PSeqBTree;共一百八十三頁Prof. Q. Wang由二叉樹的定義可知(k zh)，二叉樹的結(jié)點由一個數(shù)據(jù)元素和兩個分支構(gòu)成，因此在表示時，至少需要包含三個域：數(shù)據(jù)域和左、

22、右指針域。如果想能夠找到父結(jié)點，則可以增加一個指向父結(jié)點的指針域。利用這兩種結(jié)點結(jié)構(gòu)所得的二叉樹存儲結(jié)構(gòu)分別稱為二叉鏈表和三叉鏈表。/Declarationtypedef struct BinTreeNodeDataType info;struct BinTreeNode*lchild;struct BinTreeNode*rchild;BinTreeNode, *PBinTreeNode, BinTree, *PBinTree;6.3.2 Linked form共一百八十三頁Prof. Q. WangExample共一百八十三頁Prof. Q. WangStatic tri-branch l

23、inked list共一百八十三頁Quick ReviewTree and Binary treeADTConcepts and notationsBinary treePhysical form: bi-branch linked list Complete binary tree Sequential listProf. Q. Wang123456789101112123451112共一百八十三頁Prof. Q. WangTraversing Binary Tree (二叉樹的遍歷)：按某條搜索路徑訪問樹中每一個結(jié)點，使得每個結(jié)點被訪問且僅被訪問一次 (once and only once

24、)。Depth-first traversal (深度優(yōu)先)： 由于二叉樹是由根結(jié)點和左右子樹構(gòu)成的，因此訪問時就可以有6種訪問順序。如果限定訪問從左到右進行，則只有(zhyu)三種情況，分別稱為先根次序 (先序)、中根次序 (中序)、后根次序 (后序)，相應(yīng)的輸出序列稱為先序、中序和后序序列。Level-first traversal (按層次遍歷)：6.4.1 Definition of Traversal6.4 Traversal of binary tree共一百八十三頁Prof. Q. Wang/-abcdFig.1 (a-b)/(c+d)/bca-+dFig.2 a-(b/c+d)

25、/bca-+dFig.3 a-b/c+d/bca-+dFig.4 a-b/(c+d)Expression: a-b/c+d共一百八十三頁Prof. Q. Wang從上圖我們可以看出，二叉樹表示一個算術(shù)表達式。二叉樹的每一個子樹對應(yīng)一個子表達式，而且二叉樹的左右次序(cx)也對應(yīng)了表達式的運算次序(cx)。對圖1進行先根、后根和中根次序的遍歷得到如下的結(jié)點序列:先根：/-ab+cd后根：ab-cd+/中根：a-b/c+d這些序列分別稱為表達式的前綴表示法、后綴表示法 (逆波蘭表示法) 和中綴表示法。逆波蘭表示法可以簡化表達式的計算(why?)/-abcdFig.1 (a-b)/(c+d)共一百八

26、十三頁Prof. Q. Wang6.4.2 Traversal algorithmsRecursive algorithm (遞歸算法(sun f)InOrderTraverse (中序遍歷)PreOrderTraverse (先序遍歷)PostOrderTraverse (后序遍歷)Non-recursive algorithm (非遞歸算法)InOrderTraverse (中序遍歷)PreOrderTraverse (先序遍歷)PostOrderTraverse (后序遍歷)LevelOrderTraverse (按層次遍歷)共一百八十三頁Prof. Q. WangInorder tra

27、versalFramework of Inorder traversalIf binary tree T is NULL, NULL operationelse1) Inorder traverse the left sub-tree2) Visit the root3) Inorder traverse the right sub-treeThe result of Inorder traversal isSyntax tree of expressiona + b * c - d - e / f共一百八十三頁Prof. Q. WangStatus InOrderTraverse (PBin

28、Tree T, Status (*Visit)(ElemType e)if (T)InOrderTraverse (T-lchild, Visit);(*Visit)(T- info);InOrderTraverse (T-rchild, Visit);int PrintElement (ElemType e)printf (e);return OK;Recursive Inorder Traversal共一百八十三頁Prof. Q. WangRecursive tree of Inorder traversal1234567910118a+b*c-de/f-共一百八十三頁Prof. Q. W

29、angPreorder traversalFramework of Preorder traversalIf binary tree T is NULL, NULL operationelse1) Visit the root2) Preorder traverse the left sub-tree3) Preorder traverse the right sub-treeThe result of Preorder traversal isSyntax tree of expression- + a * b - c d / e f共一百八十三頁Prof. Q. WangStatus Pr

30、eOrderTraverse (PBinTree T, Status (*Visit)(ElemType e)if (T)(*Visit)(T- info);PreOrderTraverse (T-lchild, Visit);PreOrderTraverse (T-rchild, Visit);int PrintElement (ElemType e)printf (e);return OK;Recursive Preorder Traversal共一百八十三頁Prof. Q. WangPostorder traversalFramework of Postorder traversalIf

31、 binary tree T is NULL, NULL operationelse1) Postorder traverse the left sub-tree2) Postorder traverse the right sub-tree3) Visit the rootThe result of Postorder traversal isSyntax tree of expressiona b c d - * + e f / -共一百八十三頁Prof. Q. WangStatus PostOrderTraverse (PBinTree T, Status (*Visit)(ElemTy

32、pe e)if (T)PostOrderTraverse (T-lchild, Visit);PostOrderTraverse (T-rchild, Visit);(*Visit) (T- info);int PrintElement (ElemType e)printf (e);return OK;Recursive Postorder Traversal共一百八十三頁Prof. Q. WangOther recursive algorithm of binary tree1. Get the number of nodes of a binary tree (求二叉樹的結(jié)點(ji din

33、)個數(shù))int count ( PBinTree T ) if ( T = NULL ) return 0; else return 1 + count ( Tlchild ) + count ( Trchild );共一百八十三頁Prof. Q. WangOther recursive algorithm of binary tree2. Get the depth of a binary tree (求二叉樹的深度(shnd)int depth (PBinTree T) if ( T = NULL ) return 0; else return 1+Maxdepth ( Tlchild )

34、 , depth ( Trchild ) ;共一百八十三頁Prof. Q. WangInitialization of binary tree via PreOrderint CreateBinTree (PBinTree T ) /按先序次序(cx)構(gòu)造二叉鏈表 scanf(&ch); if ( ch = ) T=NULL; else if ( !(T = (PBinTree) malloc(sizeof(BinTreeNode) exit(-1); T - info = ch; CreateBinTree (T-lchild); CreateBinTree (T-rchild); Inpu

35、t：Get the character sequentially A B C D E G F ABCDEGFABCDEG F 共一百八十三頁Prof. Q. WangQuick reviewStorage of binary treeRecursive algorithms of traversing binary treePreorderInorderPostorder共一百八十三頁Prof. Q. WangNon-recursive traversal algorithm 二叉樹遍歷(bin l)的非遞歸算法中序遍歷的基本思想：遇到一個結(jié)點(ji din)，就把它壓入棧中，去遍歷它的左子樹

36、，遍歷它的左子樹后，從棧頂彈出這個結(jié)點并訪問之，然后再去遍歷它的右子樹。對于先根遍歷，可以通過適當判斷減少進出棧的次數(shù)：訪問一個結(jié)點之后，僅當該結(jié)點左、右子樹都不空時才把結(jié)點的右子女壓進棧。這樣可以節(jié)省算法的時間與空間開銷。先序遍歷的基本思想：遇到一個結(jié)點，訪問之，接著把壓入棧中，然后去遍歷它的左子樹。遍歷完它的左子樹后，從棧頂彈出這個結(jié)點，然后再去遍歷它的右子樹。共一百八十三頁Prof. Q. Wang/Preorder Traversalvoid PreOrderTraverse (PBinTree T ) Stack S; PBinTree p; StackEmpty( S ); p =

37、 T; do while ( p ) printf ( pinfo); Push( S, p ); p = plchild; if ( !IsEmpty( S ) ) p = getTop( S ); Pop( S ); p = prchild; while ( p | !IsEmpty( S ) ); ptrstruct StackNode PBinTree ptr; ;共一百八十三頁Prof. Q. WangStack state in PreOrderTraversal先序遍歷(bin l)中棧的變化-+-+a-+-*-*b-*-c-共一百八十三頁Prof. Q. Wang-d-/e/f

38、/?？誗tack state in PreOrderTraversal先序遍歷(bin l)中棧的變化共一百八十三頁Prof. Q. Wang/Inorder Traversalvoid InOrderTraverse (PBinTree T ) Stack S; PBinTree p; StackEmpty( S ); p = T; do while ( p ) Push( S, p ); p = plchild; if ( !IsEmpty( S ) ) p = getTop( S ); Pop( S ); printf ( pinfo); p = prchild; while ( p |

39、 !IsEmpty( S ) ); ptr共一百八十三頁Prof. Q. Wang-+-+a-+-*-*b-*-c-Stack state in InOrderTraversal中序遍歷(bin l)中棧的變化共一百八十三頁Prof. Q. Wang-d-/e/f/?？誗tack state in InOrderTraversal中序遍歷(bin l)中棧的變化共一百八十三頁Prof. Q. Wang后序遍歷(bin l)的基本思想是：后序非遞歸算法比較復雜，每個結(jié)點要到它們左、右子樹都遍歷完時才得以訪問，所以在去遍歷它的左、右子樹之前都需要進棧。當它出棧時，需要判斷是從左子樹回來（即剛遍歷完

40、左子樹，此時需要去遍歷右子樹），還是從右子樹回來（即剛遍歷完右子樹，此時需要去訪問這個結(jié)點）。因此，進棧的結(jié)點需要伴隨著一個標記tag 。 L 表明遍歷它的左子樹tag = R 表明遍歷它的右子樹需要(xyo)考慮二次進棧！共一百八十三頁Prof. Q. Wang后序遍歷根為 T 的二叉樹, 存儲結(jié)構(gòu)為二叉鏈表, S 是存儲所經(jīng)過二叉樹結(jié)點的工作棧。其中, tag 是結(jié)點標記(bioj)。當 tagL 時, 表示剛才是在左子樹中, 從左子樹退出時, 還要去遍歷右子樹。當 tag R 時, 表示剛才是在右子樹中, 在從右子樹中退出時, 去訪問位于棧頂?shù)慕Y(jié)點。typedef struct Stac

41、kNode enum tag L, R ; PBinTree ptr; StackNode; ptr tag (LR) 共一百八十三頁Prof. Q. Wang/Postorder Traversalvoid PostOrderTraverse (PBinTree T ) Stack S; PBinTree p; StackNode w; StackEmpty( S ); p = T; do while ( p ) w.ptr = p; w.tag = L; Push( S, w); p = plchild; -+aLLL-+aLLR-+LL-+LR共一百八十三頁Prof. Q. Wang i

42、nt continue = 1; while ( continue & ! IsEmpty( S ) ) w = getTop( S ); Pop( S ); p = w.ptr; switch (w.tag) case L : w.tag = R; Push( S, w); continue = 0; p = prchild; break; case R : printf (pinfo); break; while ( p | !IsEmpty( S ) );二次進棧共一百八十三頁Prof. Q. Wang-L-+aLLR-+LL-+aLLL-+aLLR-+LL-+LR-+LR*LbL-+L

43、R*R-+LR*LbR-+LR*LbR-+LR*R-L-+LR*R-LcL-+LR*R-LcR-+LR*R-LcR-+LR*R-L-+LR*R-R-+LR*R-RdLStack state in InOrderTraversal后序(hu x)遍歷中棧的變化共一百八十三頁Prof. Q. Wang-+LR*R-RdR-+LR*R-RdR-+LR*R-R-+LR*R-+LR-R-R/L-R/LeL-R/LeR-R/LeR-R/L-R/R-R/RfL-R/RfR-R/RfR-R/R-R棧空Stack state in InOrderTraversal后序遍歷(bin l)中棧的變化共一百八十三頁Q

44、uick ReviewStructure of binary treeBinary linked listTraversal of binary treeRecursive algorithmsNon-recursive algorithmsProf. Q. Wang共一百八十三頁Prof. Q. WangLevelOrderTraversalFrom the root, visit the nodefrom the top to the bottom, and from the left to the right at the same level.Queue involved共一百八十三頁

45、Prof. Q. Wang/Level order Traversalvoid LevelOrderTraverse (PBinTree T ) Queue qu; PBinTree p; if ( !T) printf( “End of level order traversal!n”); return; EnQueue (qu, T); while ( !empty(qu) ) DeQueue ( qu, p); printf (p-info);/DeQueue & output if ( plchild != NULL ) /Left child EnQueue ( qu, p-lchi

46、ld ); /EnQueue if ( prchild != NULL ) /Right child EnQueue ( qu, p-rchild ); /EnQueue struct QueueNode PBinTree ptr; ;共一百八十三頁Prof. Q. WangAnalysis of binary tree traversalTime complexity (時間復雜度)O(n)Space complexity (空間復雜度)Depth-first methods (深度優(yōu)先的方法)O(棧的深度)Level-first method (按層次(cngc)遍歷)O(n)n: num

47、ber of binary tree nodes (二叉樹的結(jié)點個數(shù))共一百八十三頁Prof. Q. Wangvoid Postorder(PBinTree t) Stack s; PBinTreeNode p;/* 周游時當前要處理結(jié)點的位置 */ char flag;/* 結(jié)點p的標志量 */ char continueflag; /* 表明是否要繼續(xù)退棧，當從右子樹返回 時，則要在訪問完根之后繼續(xù)退棧 */ ElemTypeelem; if (t = NULL)return; InitStack(&s); p = t;/* 從根結(jié)點開始 */ do/* 每執(zhí)行(zhxng)一次大循環(huán)進入

48、一棵由p指出根的子樹去周游 */while (p != NULL)/* 反復地把遇到的結(jié)點進棧并進入它的左子樹 */elem.ptr = p;elem.tag = 1;Push(&s, elem); p = p-llink; continueflag = 1;共一百八十三頁Prof. Q. Wang while ( continueflag = 1 & !IsStackEmpty(s)Pop(&s, &elem);p = elem.ptr; if (elem.tag = 1)/* 如果是從左子樹回來，則 改標志重新(chngxn)進棧，停止退棧并進入右子樹 */elem.tag = r;Pus

49、h(&s, elem);continueflag = 0;p = p-rlink; elsevisit(p-info); while (!IsStackEmpty(s);/* 棧為空時，全部周游完 */ DestroyStack(&s);共一百八十三頁Prof. Q. Wang6.4.3 Reconstruction of Binary TreeProblem 1Given a binary tree, isPreorder sequence, orInorder sequence, orPostorder sequenceUnique?Problem 2Given a preorder se

50、quence of BT, can you reconstruct an unique binary tree?How about Inorder sequence, postorder sequence?共一百八十三頁Prof. Q. WangProblem 3Given preorder and inorder sequences of BT, can you reconstruct this binary tree?Preorder: abcd;Inorder: badc;Given postorder and inorder sequences of BT, can you recon

51、struct this binary tree?Postorder: bdca;Inorder: badc;Given preorder and postorder sequences of BT, can you reconstruct this binary tree?Preorder: abcd;Postorder: dcba;共一百八十三頁Prof. Q. WangExampleSuppose that the preorder sequence of BT isABECDFGHIJand the inorder sequence of BT isEBCDAFHIGJtry to re

52、construct this binary tree.共一百八十三頁Prof. Q. WangAEBCDFHIGJBECDHIGJFAPreorder sequence: ABECDFGHIJInorder sequence: EBCDAFHIGJ共一百八十三頁Prof. Q. WangABFCEDJGHIABECDFGJHIPreorder sequence: ABECDFGHIJInorder sequence: EBCDAFHIGJ共一百八十三頁Prof. Q. Wang6.4.4 Counter of BTProblem (問題)給你一個二叉樹的前序遍歷序列，問具有(jyu)這樣先序序

53、列的二叉樹有多少棵？123456789共一百八十三頁Prof. Q. WangExample (1)For example, 1, 2, 3 Preorder sequence 123Inorder traversed sequences are 123, 132, 213, 231, and 321123132213231321共一百八十三頁Prof. Q. WangExample (2)n=0, 1, 2, 3, 4共一百八十三頁Prof. Q. WangConclusionbibn-i-1共一百八十三頁Prof. Q. Wang定義(dngy)生成函數(shù)由于(yuy)共一百八十三頁Prof

54、. Q. Wang共一百八十三頁Prof. Q. WangQuestions共一百八十三頁Prof. Q. WangQuestions共一百八十三頁Quick ReviewTraversalReconstructionProf. Q. Wang共一百八十三頁Prof. Q. WangTraversing Binary Tree (二叉樹的遍歷)：按某條搜索路徑訪問樹中每一個結(jié)點，使得每個結(jié)點被訪問且僅被訪問一次 (once and only once)。Depth-first traversal (深度優(yōu)先)： 由于二叉樹是由根結(jié)點和左右子樹構(gòu)成的，因此訪問時就可以有6種訪問順序。如果限定訪問

55、從左到右進行，則只有三種情況，分別稱為先根次序 (先序)、中根次序 (中序)、后根次序 (后序(hu x)，相應(yīng)的輸出序列稱為先序、中序和后序序列。Level-first traversal (按層次遍歷)：6.4.1 Definition of Traversal6.4 Traversal of binary tree共一百八十三頁Prof. Q. WangAEBCDFHIGJBECDHIGJFAPreorder sequence: ABECDFGHIJInorder sequence: EBCDAFHIGJ共一百八十三頁Quick ReviewTraversalReconstruction

56、Threaded binary treeMotivationMethodologyApplicationProf. Q. Wang共一百八十三頁Prof. Q. Wang 遍歷二叉樹是按一定的規(guī)則將二叉樹中結(jié)點排列成一個線性序列；這實際上是把一個非線性結(jié)構(gòu)進行線性化的操作。 以二叉鏈表作為存儲結(jié)構(gòu)時，對于某個(mu )結(jié)點只能找到其左右孩子，而不能直接得到結(jié)點在任一序列中的前驅(qū)或后繼。要想得到，只能通過遍歷的動態(tài)過程才行。 怎樣保存遍歷過程中得到的信息呢？6.5 Threading binary tree共一百八十三頁Prof. Q. Wangpresucrchildlchildinfo1）增

57、加(zngji)兩個指針，分別指示其前驅(qū)和后繼結(jié)點predecessorsuccessor共一百八十三頁Prof. Q. Wangstruct ThrTreeNode/* 線索(xin su)樹中每個結(jié)點的結(jié)構(gòu) */ DataType info;struct ThrTreeNode *lchild;struct ThrTreeNode *rchild;struct ThrTreeNode *pre;struct ThrTreeNode *suc;ThrTree, *PThrTree, *PThrTreeNode;BDAECSucPreroot共一百八十三頁Prof. Q. Wangrtagrc

58、hildlchildinfoltag2）利用(lyng)結(jié)構(gòu)中的空鏈域，并設(shè)立標志，即采用如下的形式共一百八十三頁Prof. Q. Wangstruct ThrTreeNode/* 線索樹中每個結(jié)點的結(jié)構(gòu)(jigu) */ DataType info;struct ThrTreeNode *lchild, *rchild;int ltag, rtag;ThrTree, *PThrTree, *PThrTreeNode;其中當ltag或rtag為0時，llink或rlink為指針，否則為1時，llink或rlink表示線索。共一百八十三頁Prof. Q. Wang線索鏈表：以上面結(jié)構(gòu)構(gòu)成的二叉鏈

59、表作為(zuwi)二叉樹的存儲結(jié)構(gòu)，叫做線索鏈表。線索：指向結(jié)點前驅(qū)或后繼的指針叫做線索。線索二叉樹：加上線索的二叉樹叫線索二叉樹。線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。共一百八十三頁Prof. Q. WangQuestion (1)In an InOrderThreading binary tree, where is The predecessor of a given nodeThe successor of a given node共一百八十三頁Prof. Q. Wang在中序線索(xin su)二叉樹中找結(jié)點的后繼在中序線索樹中找結(jié)點后繼的規(guī)律是： 1)

60、若右標志(biozh)是1，則右鏈為線索，指示其后繼；2) 否則，遍歷該結(jié)點的右子樹時訪問的第一個結(jié)點(右子樹中最左下的結(jié)點)為其后繼。-+a*b-cd+efNULLNULL共一百八十三頁Prof. Q. Wang在中序線索(xin su)二叉樹中找結(jié)點的前驅(qū)在中序線索樹中找結(jié)點(ji din)前驅(qū)的規(guī)律是：1) 若左標志是1，則左鏈為線索，指示其前驅(qū)；2) 否則，遍歷該結(jié)點的左子樹時最后訪問的結(jié)點(左子樹中最右下的結(jié)點)為其前驅(qū)。-+a*b-cd+efNULLNULL共一百八十三頁Prof. Q. WangOther questions (2)In PreOrderThreading tre