數(shù)據(jù)結(jié)構(gòu)第六章

1、Chapter 6Tree and Binary Tree共二百七十五頁(yè)課時(shí)安排(npi) 8學(xué)時(shí)教學(xué)內(nèi)容： 樹(shù)的基本概念；二叉樹(shù)的性質(zhì)和存儲(chǔ)(cn ch)結(jié)構(gòu)；遍歷二叉樹(shù)和線索二叉樹(shù);樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷；哈夫曼樹(shù)及其應(yīng)用； 要求學(xué)生掌握： 1、二叉樹(shù)的結(jié)構(gòu)特點(diǎn)；2、二叉樹(shù)各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；3、按各種次序遍歷二叉樹(shù)的遞歸和非遞歸算法；4、二叉樹(shù)的線索化，在中序線索樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；5、樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)；6、編寫(xiě)樹(shù)的各種運(yùn)算的算法；7、建立最優(yōu)二叉樹(shù)和哈夫曼編碼的方法。 教學(xué)重點(diǎn)及難點(diǎn)： 按各種次序遍歷二叉樹(shù)的遞歸和非遞歸算法。 共二百七十五頁(yè)1 Tree D

2、efinition1. TerminologyLineal TreePedigree Tree( binary tree )共二百七十五頁(yè)Example of Tree共二百七十五頁(yè)Example of Tree共二百七十五頁(yè)Example of Tree共二百七十五頁(yè)Example of Tree共二百七十五頁(yè)Example of Expression tree共二百七十五頁(yè)【Definition】A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a

3、distinguished node r, called the root; (2) and zero or more nonempty (sub)trees T1, , Tk, each of whose roots are connected by a directed edge from r.Note: Subtrees must not connect together. Therefore every node in the tree is the root of some subtree. There are edges in a tree with N nodes. Normal

4、ly the root is drawn at the top.N 1共二百七十五頁(yè)ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2rootexample:共二百七十五頁(yè)線性結(jié)構(gòu)(jigu)樹(shù)型結(jié)構(gòu)(jigu)第一個(gè)數(shù)據(jù)元素 (無(wú)前驅(qū)) 根結(jié)點(diǎn) (無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素 (無(wú)后繼)多個(gè)葉子結(jié)點(diǎn) (無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、 一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、 多個(gè)后繼)對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)共二百七十五頁(yè)ACBDGFEHIJMLK degree of a node := number of subtrees of

5、 the node. For example, degree(A) = 3, degree(F) = 0. degree of a tree := For example, degree of this tree = 3. leaf ( terminal node ) := a node with degree 0 (no children). parent := a node that has subtrees. children := the roots of the subtrees of a parent. siblings := children of the same parent

6、.3/16terminology共二百七十五頁(yè)1 PreliminariesACBDGFEHIJMLK ancestors of a node := all the nodes along the path from the node up to the root. descendants of a node := all the nodes in its subtrees. depth of ni := length of the unique path from the root to ni. Depth(root) = 0. height of ni := length of the l

7、ongest path from ni to a leaf. Height(leaf) = 0, and height(D) = 2. height (depth) of a tree := height(root) = depth(deepest leaf). path from n1 to nk := a (unique) sequence of nodes n1, n2, , nk such that ni is the parent of ni+1 for 1 i =0) is at least log2n +1 。證明(zhngmng)：設(shè)完全(wnqun)二叉樹(shù)的深度為 k 則根據(jù)

8、第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n k 因?yàn)?k 只能是整數(shù),因此, k =log2n + 1 共二百七十五頁(yè)porperty 5 (only for complete binary tree) suppose we number the elements in a complete binary tree that contain n element from top level to bottom level ,within level the element are numbered from left to right. let i (1=i1, then th

9、e parent of this element has been assigned the number i/2 .(2) If 2in，then this element has no left child, otherwise its left child has been assigned the number 2i ；(3) if 2i+1n，then this element has no right child, otherwise its right child has been assigned the number 2i+1 。共二百七十五頁(yè)6.3 Storage stru

10、cture of binary tree二、Linked representation一、 Sequential representation共二百七十五頁(yè) 用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素。對(duì)于一般二叉樹(shù)，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹(shù)上的結(jié)點(diǎn)相對(duì)(xingdu)照，存儲(chǔ)在一維數(shù)組的相應(yīng)分量中。12345678910111212345000067 完全二叉樹(shù) 一般(ybn)二叉樹(shù)順序存儲(chǔ)適用于完全二叉樹(shù) （0表示不存在的結(jié)點(diǎn)）1234578910111261234567一.Sequential representation of binary tree共

11、二百七十五頁(yè)Sequential representation of Incomplete binary tree共二百七十五頁(yè)Sequential representation of Right-skewed tree共二百七十五頁(yè)#define MAX_TREE_SIZE 100 / 二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0號(hào)單元(dnyun)存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;共二百七十五頁(yè)二.Linked representation of binary tree1. 二叉鏈表2三叉鏈表3雙親(shungqn)鏈表4線索

12、(xin su)鏈表(見(jiàn)下一節(jié))共二百七十五頁(yè)ADEBCFrootlchild data rchild結(jié)點(diǎn)(ji din)結(jié)構(gòu):1. 二叉鏈表含有兩個(gè)指針(zhzhn)域的結(jié)點(diǎn)結(jié)構(gòu)共二百七十五頁(yè)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)(jigu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)(ji din)結(jié)構(gòu):C 語(yǔ)言的類(lèi)型描述如下:共二百七十五頁(yè)BinaryTreeNode class definition(c+)共二百七十五頁(yè)

13、Linked representation of binary tree共二百七十五頁(yè)ADEBCFroot2三叉鏈表parent lchild data rchild結(jié)點(diǎn)(ji din)結(jié)構(gòu):含有(hn yu)三個(gè)指針域的結(jié)點(diǎn)結(jié)構(gòu)共二百七十五頁(yè) typedef struct TriTNode / 結(jié)點(diǎn)(ji din)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)(j

14、i din)結(jié)構(gòu):C 語(yǔ)言的類(lèi)型描述如下:共二百七十五頁(yè)ABCDEFGABCDEFGBCDEFGA二叉樹(shù) 二叉鏈表 三叉鏈表rootroot共二百七十五頁(yè)0123456 data parent結(jié)點(diǎn)(ji din)結(jié)構(gòu):3雙親(shungqn)鏈表LRTagLRRRLABCDEF共二百七十五頁(yè) typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)(jigu) TElemType data; int parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹(shù)結(jié)構(gòu) BPTNode nodesMAX_TRE

15、E_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置 BPTreeC 語(yǔ)言描述雙親(shungqn)鏈表結(jié)點(diǎn)共二百七十五頁(yè)一、問(wèn)題(wnt)的提出二、先左后右的遍歷(bin l)算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例6.4 binary tree traversal共二百七十五頁(yè) 順著某一條搜索(su su)路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。一、問(wèn)題(wnt)的提出 “訪問(wèn)”的含義可以很廣，可以對(duì)結(jié)點(diǎn)作各種處理，如：輸出結(jié)點(diǎn)的信息等。共二百七十五頁(yè) “遍歷”是任何類(lèi)型均有的操作(coz

16、u)，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問(wèn)題。 共二百七十五頁(yè) 對(duì)“二叉樹(shù)”而言，可以有三條搜索(su su)路徑： 1先上后下的按層次(cngc)遍歷； 2先左(子樹(shù))后右(子樹(shù))的遍歷； 3先右(子樹(shù))后左(子樹(shù))的遍歷。共二百七十五頁(yè)二、先左后右的遍歷(bin l)算法Pre-order traversal(先（根）序的遍歷(bin l)算法)In-order traversal(中（根）序的遍歷算法)Post-order traversal(后（根）序的遍歷

17、算法)共二百七十五頁(yè) if binary tree is empty, then NULL operation, otherwise（1）visit root node；（2）pre-order traversal left subtree（3）pre-order traversal right subtreePre-order traversal：-+/e*afb-cdPre-order： -+a*b-cd/ef共二百七十五頁(yè) if binary tree is empty, then NULL operation, otherwise（1）in-order traversal left s

18、ubtree（2）visit root node；（3） in-order traversal right subtreein-order traversal： -+/e*afb-cdIn-order：a+b*c-d-e/f共二百七十五頁(yè) if binary tree is empty, then NULL operation, otherwise（1）post-order traversal left subtree（2）post-order traversal right subtree（3）visit root node；Post-order traversal：-+/e*afb-cdP

19、ost-order：abcd-*+ef/-共二百七十五頁(yè) Tree Traversals visit each node exactly once2 Binary Trees Preorder Traversal Postorder Traversal Levelorder Traversalvoid preorder ( tree_ptr tree ) if ( tree ) visit ( tree ); for (each child C of tree ) preorder ( C ); void postorder ( tree_ptr tree ) if ( tree ) for

20、(each child C of tree ) postorder ( C ); visit ( tree ); void levelorder ( tree_ptr tree ) enqueue ( tree ); while (queue is not empty) visit ( T = dequeue ( ) ); for (each child C of T ) enqueue ( C ); 2453671112324536745679/16共二百七十五頁(yè)2 Binary Treesvoid inorder ( tree_ptr tree ) if ( tree ) inorder

21、( tree-Left ); visit ( tree-Element ); inorder ( tree-Right ); Inorder TraversalIterative Programvoid iter_inorder ( tree_ptr tree ) Stack S = CreateStack( MAX_SIZE ); for ( ; ; ) for ( ; tree; tree = tree-Left ) Push ( tree, S ) ; tree = Top ( S ); Pop( S ); if ( ! tree ) break; visit ( tree-Elemen

22、t ); tree = tree-Right; Example Given an infix expression: A + B C D+ADBCThen inorder traversal A + B C D postorder traversal A B C D + preorder traversal + A B C D10/16共二百七十五頁(yè)三、Recursion algorithm( c language)void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍歷(bin l)二叉樹(shù) if (T) visit(T-data)

23、; / 訪問(wèn)根結(jié)點(diǎn) Preorder(T-lchild, visit); / 遍歷左子樹(shù) Preorder(T-rchild, visit);/ 遍歷右子樹(shù) 共二百七十五頁(yè)void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍歷二叉樹(shù) if (T) Inorder(T-lchild, visit); / 遍歷左子樹(shù) visit(T-data); / 訪問(wèn)(fngwn)根結(jié)點(diǎn) Inorder(T-rchild, visit);/ 遍歷右子樹(shù) 共二百七十五頁(yè)void Postorder (BiTree T, void( *visit)(T

24、ElemType& e) / 后序遍歷二叉樹(shù) if (T) Postorder(T-lchild, visit); / 遍歷左子樹(shù) Postorder(T-rchild, visit);/ 遍歷右子樹(shù) visit(T-data); / 訪問(wèn)(fngwn)根結(jié)點(diǎn) 遞歸算法簡(jiǎn)明(jinmng)精練，但效率較低。共二百七十五頁(yè) 在非遞歸算法中要用棧來(lái)保存遍歷過(guò)程中經(jīng)歷的結(jié)點(diǎn)的左孩子和右孩子。 使用(shyng)棧來(lái)實(shí)現(xiàn)中序遍歷二叉樹(shù)的基本思想：從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直走到末端為止，在向前搜索的過(guò)程中將所遇結(jié)點(diǎn)進(jìn)棧，待遍歷完左子樹(shù)時(shí)，從棧頂退出結(jié)點(diǎn)并訪問(wèn)，然后再遍歷右子樹(shù)。四. Iterat

25、ive algorithm( c language)共二百七十五頁(yè)BiTNode *GoFarLeft(BiTree T, Stack *S) if (!T ) return NULL; while (T-lchild )/ 找到最左下的結(jié)點(diǎn)(ji din) Push(S, T); T = T-lchild; return T; 1、in-order traversal Iterative algorithm(1) ( c language)共二百七十五頁(yè)void Inorder_I(BiTree T, void (*visit) (TelemType& e) Stack *S; t = Go

26、FarLeft(T, S); / 找到最左下的結(jié)點(diǎn) while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 棧不空時(shí)退棧 t = Pop(S); else t = NULL; / ?？毡砻鞅闅v(bin l)結(jié)束 / while/ Inorder_I 共二百七十五頁(yè)算法思想：(p131) 假設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)，根據(jù)中序遍歷二叉樹(shù)的遞歸定義，轉(zhuǎn)換成非遞歸函數(shù)時(shí)用一個(gè)棧保存返回的結(jié)點(diǎn)，先掃描根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧，出棧一個(gè)結(jié)點(diǎn)，訪問(wèn)之，然后(rnhu)掃描該結(jié)點(diǎn)

27、的右結(jié)點(diǎn)并入棧，再掃描該右結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧，如此這樣，直到?？諡橹?。in-order traversal Iterative algorithm(2)共二百七十五頁(yè)in-order traversal Iterative algorithm(2)( c language)void inorder( BiTree b) BiTree *stackm0,*p; int top=0; p=b; do while (p!=NULL) /掃描(somio)所有左結(jié)點(diǎn) top+; stacktop=p; p=p-lchild; 共二百七十五頁(yè) if (top0) p=stacktop; /p所指結(jié)點(diǎn)

28、為無(wú)左子樹(shù)的結(jié)點(diǎn)或其左子樹(shù)已遍歷(bin l)過(guò) top-; printf(“%d”,p-data); /訪問(wèn)結(jié)點(diǎn) p=p-rchild; /掃描右子樹(shù) while (p!=NULL | top!=0) 共二百七十五頁(yè)2.pre-order traversal Iterative algorithm 假設(shè)二叉樹(shù)采用(ciyng)二叉鏈表存儲(chǔ)。算法思想： 依題意，使用(shyng)一個(gè)棧 stack實(shí)現(xiàn)非遞歸的前序遍歷。共二百七十五頁(yè)pre-order traversal Iterative algorithm( c language)void preorder( BiTree b) BiTre

29、e *stackm0; int top; if (b!=NULL) top=1; /根結(jié)點(diǎn)入棧 stacktop=b; while (top0) /棧不為空時(shí)循環(huán)(xnhun) p=stacktop; /退棧并訪問(wèn)該結(jié)點(diǎn) top-; printf(“%d”,p-data); 共二百七十五頁(yè) if (p-rchild!=NULL) /右孩子(hi zi)入棧 top+; stacktop=p-rchild; if (p-lchild!=NULL) /左孩子入棧 top+; stacktop=p-lchild; 共二百七十五頁(yè)3.post-order traversal Iterative alg

30、orithm 假設(shè)(jish)二叉樹(shù)采用二叉鏈表存儲(chǔ)。算法思想： 根據(jù)后序(hu x)遍歷二叉樹(shù)的遞歸定義，轉(zhuǎn)換成非遞歸函數(shù)時(shí)用一個(gè)棧保存返回的結(jié)點(diǎn)，先掃描根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧，出棧一個(gè)結(jié)點(diǎn)，然后掃描該結(jié)點(diǎn)的右結(jié)點(diǎn)并入棧，再掃描該結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧，當(dāng)一個(gè)結(jié)點(diǎn)的左右子樹(shù)均訪問(wèn)后再訪問(wèn)該結(jié)點(diǎn)，如此這樣，直到?？諡橹埂９捕倨呤屙?yè) 在訪問(wèn)根結(jié)點(diǎn)的右子樹(shù)后，當(dāng)指針p指向右子樹(shù)樹(shù)根時(shí)，必須記下根結(jié)點(diǎn)的位置，以便在遍歷右子樹(shù)之后正確返回，這就產(chǎn)生了一個(gè)問(wèn)題：在退?；氐礁Y(jié)點(diǎn)時(shí)如何區(qū)別是從左子樹(shù)返回還是從右子樹(shù)返回。這里采用兩個(gè)棧 stack 和 tag，并用一個(gè)共同的棧頂指針，一個(gè)存放指針值，

31、一個(gè)存放左右子樹(shù)標(biāo)志（0為左子樹(shù)，1為右子樹(shù)）。退棧時(shí)在退出(tuch)結(jié)點(diǎn)指針的同時(shí)區(qū)分是遍歷左子樹(shù)返回的還是遍歷右子樹(shù)返回的，以決定下一步是繼續(xù)遍歷右子樹(shù)還是訪問(wèn)根結(jié)點(diǎn)。共二百七十五頁(yè)post-order traversal Iterative algorithm( c language)void postorder( BiTree b) BiTree *stackm0,*p; int tagm0, top=0; p=b; do while (p!=NULL) /掃描(somio)左結(jié)點(diǎn) top+; stacktop=p; tagtop=0; p=p-lchild; 共二百七十五頁(yè) /p所

32、指結(jié)點(diǎn)為無(wú)左子樹(shù)的結(jié)點(diǎn)或其左子樹(shù)已遍歷(bin l)過(guò) while (top0) & tagtop=1) / p的左右子樹(shù)都訪問(wèn)過(guò) printf(“%d”, stacktop -data); /訪問(wèn)結(jié)點(diǎn) top-; p=stacktop; if (top0) & (tagtop=0) p=p-rchild; /掃描右子樹(shù) tagtop=1; /表示當(dāng)前結(jié)點(diǎn)的右子樹(shù)已訪問(wèn)過(guò) while (p!=NULL | top!=0) 共二百七十五頁(yè)4、level-order traversal （within level from left to right traversal)算法思想： 假設(shè)二叉樹(shù)采用

33、二叉鏈表結(jié)構(gòu)，依題意，本算法要采用一個(gè)隊(duì)列(duli)q，先將二叉樹(shù)根結(jié)點(diǎn)入隊(duì)列，然后出隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹(shù)，便將左子樹(shù)根結(jié)點(diǎn)入隊(duì)列；若它有右子樹(shù)，便將右子樹(shù)根結(jié)點(diǎn)入隊(duì)列，如此直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)先出，從而達(dá)到按層次順序遍歷二叉樹(shù)的目的。共二百七十五頁(yè)level-order traversal( c language)#define MAXLEN 100void translevel(BiTree t) struct node BiTree *vecMAXLEN; int f,r; q; q.f=0; q.r=0; /置隊(duì)列為空隊(duì)列 if (b!=NULL) prin

34、tf(“%d”,b-data); q.vecq.r=b; /結(jié)點(diǎn)(ji din)指針進(jìn)入隊(duì)列 q.r=q.r+1;共二百七十五頁(yè)while (q.flchild!=NULL) /輸出(shch)左孩子，并入隊(duì)列 printf(“%d”,b-lchild-data); q.vecq.r=b-lchild; q.r=q.r+1; if (b-rchild!=NULL) /輸出右孩子，并入隊(duì)列 printf(“%d”,b-rchild-data); q.vecq.r=b-rchild; q.r=q.r+1; 共二百七十五頁(yè)BinaryTree class definition(c+)共二百七十五頁(yè)B

35、inaryTree class definition(c+)(continue)共二百七十五頁(yè)BinaryTree class definition(c+)(continue)共二百七十五頁(yè)BinaryTree class Root Function(c+)共二百七十五頁(yè)BinaryTree class MakeTree Function(c+)共二百七十五頁(yè)BinaryTree class BreakTree Function(c+)共二百七十五頁(yè)BinaryTree class PreOrder Function(c+)共二百七十五頁(yè)BinaryTree class InOrder Fun

36、ction(c+)共二百七十五頁(yè)BinaryTree class PostOrder Function(c+)共二百七十五頁(yè)BinaryTree class LevelOrder Function(c+)共二百七十五頁(yè)Application of class BinaryTree共二百七十五頁(yè)五、遍歷(bin l)算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹(shù)中葉子(y zi)結(jié)點(diǎn)的個(gè)數(shù) (先序遍歷)2、求二叉樹(shù)的深度(后序遍歷)4、復(fù)制二叉樹(shù)(后序遍歷)5、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6、根據(jù)遍歷序列構(gòu)造二叉樹(shù)3、求二叉樹(shù)值為X的祖先(后序遍歷)共二百七十五頁(yè)1、統(tǒng)計(jì)二叉樹(shù)中葉子(y zi)結(jié)點(diǎn)的個(gè)數(shù)算法(sun f

37、)基本思想: 先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。共二百七十五頁(yè)Int CountLeaf (BiTree T) ( c language) if (T=NULL) return 0; else if (T-lchild=NULL & T-rchild=NULL) return 1; else return CountLeaf(T-lchild) + CountLeaf(T-rchild);共二百七十五頁(yè)2、求二叉樹(shù)的深度(后序(hu x)遍歷)算法(sun f)

38、基本思想: 從二叉樹(shù)深度的定義可知，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此，需先分別求得左、右子樹(shù)的深度，算法中“訪問(wèn)結(jié)點(diǎn)”的操作為：求得左、右子樹(shù)深度的最大值，然后加 1 。 首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。共二百七十五頁(yè)int Depth (BiTree T )( c language) / 返回(fnhu)二叉樹(shù)的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft dep

39、thRight ? depthLeft : depthRight); return depthval;共二百七十五頁(yè)Height of a binary tree(c+)共二百七十五頁(yè)3、在二叉樹(shù)中查找值為x的結(jié)點(diǎn)，試設(shè)計(jì)打印值為x的結(jié)點(diǎn)的所有祖先(zxin)的算法。假設(shè)值為x的結(jié)點(diǎn)不多于1個(gè)。算法思想： 依題意，本題采用后序遍歷的非遞歸算法，因退棧時(shí)需區(qū)分其左右子樹(shù)是否已遍歷，因此在結(jié)點(diǎn)(ji din)入棧的同時(shí)附帶一個(gè)標(biāo)志：0表示是左子樹(shù)，1表示是右子樹(shù)。用棧stack保存結(jié)點(diǎn)指針及其標(biāo)志。共二百七十五頁(yè)實(shí)現(xiàn)本題(bnt)功能的函數(shù)如下：void ancestor(BiTree t, in

40、t x) ( c language) struct node BiTree *p; int tag; /只取0或1 s100; int top=0,i; while (1) while (t!=NULL & t-data!=x) /將t所指結(jié)點(diǎn)的所有左孩子入棧 top+; stop.p=t; stop.tag=0; t=t-lchild; if (t!=NULL&t-data=x) /找到了該結(jié)點(diǎn)，則打印(d yn)其祖先共二百七十五頁(yè) printf(“結(jié)點(diǎn)%d的祖先是:”, x) ; for (i=1;idata); break; else while (top0&stop.tag=1) t

41、op-; /當(dāng)前結(jié)點(diǎn)的左右結(jié)點(diǎn)都訪問(wèn)(fngwn)過(guò)，則退棧 t=stacktop; if (top0) & (tagtop=0) t=t-rchild; tagtop=1; /開(kāi)始訪問(wèn)其右結(jié)點(diǎn) 共二百七十五頁(yè)4、復(fù)制(fzh)二叉樹(shù)(后序遍歷)其基本操作為：生成(shn chn)一個(gè)結(jié)點(diǎn)。根元素T左子樹(shù)右子樹(shù)根元素NEWT左子樹(shù)右子樹(shù)左子樹(shù)右子樹(shù)共二百七十五頁(yè)BiTNode *GetTreeNode (TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(

42、1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一個(gè)二叉樹(shù)的結(jié)點(diǎn)(ji din)( c language)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)共二百七十五頁(yè)BiTNode *CopyTree(BiTNode *T) ( c language) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /復(fù)制(fzh)左子樹(shù) else newlptr = NULL; if (T-rchild ) newrpt

43、r = CopyTree(T-rchild); /復(fù)制右子樹(shù) else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree共二百七十五頁(yè)ABCDEFGHK D C B H K G F E A例如：下列二叉樹(shù)的復(fù)制(fzh)過(guò)程如下：newT共二百七十五頁(yè)5、建立(jinl)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 定義(dngy)的方法不同，相應(yīng)地建立存儲(chǔ)結(jié)構(gòu)的算法也不同共二百七十五頁(yè) (1) 以字符串的形式(xngsh) 根-左子樹(shù)-右子樹(shù) 定義一棵二叉樹(shù)例如(lr):ABCD以空白字符“ ”表示

44、A(B( ,C( , ),D( , )空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A( )”表示以下列字符串表示共二百七十五頁(yè)Status CreateBiTree(BiTree &T) ( c language) /按先序輸入(shr)二叉樹(shù)結(jié)點(diǎn)的值 scanf(&ch); if (ch= ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; / 生成根結(jié)點(diǎn) CreateBiTree(T-lchild); / 構(gòu)造左子樹(shù) CreateBiTree(T-rchild); /

45、構(gòu)造右子樹(shù) return OK; / CreateBiTree共二百七十五頁(yè)A B C D ABCD上頁(yè)算法執(zhí)行(zhxng)過(guò)程舉例如下：ATBCD共二百七十五頁(yè)(2) 按給定(i dn)的先綴表達(dá)式建相應(yīng)的二叉樹(shù)例如(lr)：已知表達(dá)式的先綴表達(dá)式 -+ a b c / d e 由原表達(dá)式建樹(shù)例如：已知表達(dá)式 (a+b)c d/e共二百七十五頁(yè)對(duì)應(yīng)(duyng)先綴表達(dá)式 -+ a b c / d e的二叉樹(shù)abcde-+/特點(diǎn)(tdin)： 操作數(shù)為葉子結(jié)點(diǎn) 運(yùn)算符為分支結(jié)點(diǎn)共二百七十五頁(yè)scanf(&ch);if ( In(ch, 字母(zm)集 ) 建葉子結(jié)點(diǎn); /為操作數(shù)else

46、建根結(jié)點(diǎn); 遞歸建左子樹(shù); 遞歸建右子樹(shù);由先綴表達(dá)式建樹(shù)(jinsh)的算法的基本操作：共二百七十五頁(yè)a+b(a+b)c d/ea+bc 分析(fnx)表達(dá)式和二叉樹(shù)的關(guān)系:ab+abc+abc+(a+b)cabcde-+/共二百七十五頁(yè) Expression Trees (syntax trees)Example Given an infix expression: A + B C D+ADBC Constructing an Expression Tree (from postfix expression)Example ( a + b ) * ( c * ( d + e ) ) = a

47、 b + c d e + * * abT2aT1b+cdec+T1T2de+abc+deT1T2*+abc+deT1T2*8/16共二百七十五頁(yè)基本操作:scanf(&ch);if (In(ch, 字母(zm)集 ) 建葉子結(jié)點(diǎn); 暫存; else if (In(ch, 運(yùn)算符集) 和前一個(gè)運(yùn)算符比較優(yōu)先數(shù); 若當(dāng)前的優(yōu)先數(shù)“高”，則暫存; 否則建子樹(shù); 共二百七十五頁(yè)void CrtExptree(BiTree &T, char exp ) ( c language) InitStack(S); Push(S, #); InitStack(PTR); p = exp; ch = *p; /

48、PTR堆棧放樹(shù)和結(jié)點(diǎn)，S堆棧放字符和運(yùn)算符 while (!(GetTop(S)=# & ch=#) if (!IN(ch, OP) CrtNode( t, ch );/代表讀入的是字符，建立葉子(y zi)結(jié)點(diǎn)并入棧， #號(hào)代表表達(dá)式的開(kāi)始和結(jié)束， OP代表運(yùn)算符集合 else /代表讀入的是運(yùn)算符 if ( ch!= # ) p+; ch = *p;/未結(jié)束時(shí)指針后移 / while Pop(PTR, T); /從PTR棧中彈出最后的一棵樹(shù) / CrtExptree 共二百七十五頁(yè)switch (ch) case ( : Push(S, ch); break; /表示(biosh)讀入的c

49、h是“(” case ) : Pop(S, c); /表示讀入的ch是“)” while (c!= ( ) /棧頂不是“(” CrtSubtree( t, c); /按棧頂元素建子樹(shù)并入棧 Pop(S, c) ; break; defult : /表示讀入的ch是其他運(yùn)算符 / switch 共二百七十五頁(yè)while(!Gettop(S, c) & ( precede(c,ch) /棧頂元素c的運(yùn)算(yn sun)優(yōu)先級(jí)大于剛讀入的ch運(yùn)算符的優(yōu)先級(jí) CrtSubtree( t, c); /按棧頂元素建子樹(shù) Pop(S, c); /彈出棧頂元素if ( ch!= # ) Push( S, ch

50、); /將ch運(yùn)算符入棧break;共二百七十五頁(yè)建葉子(y zi)結(jié)點(diǎn)的算法為：void CrtNode(BiTree& T,char ch) ( c language) T=(BiTNode*)malloc(sizeof(BiTNode); T-data = ch; T-lchild = T-rchild = NULL; Push( PTR, T );共二百七十五頁(yè)建子(jin z)樹(shù)的算法為：void CrtSubtree (Bitree& T, char c)( c language) T=(BiTNode*)malloc(sizeof(BiTNode); T-data = c; Po

51、p(PTR, rc); T-rchild = rc; Pop(PTR, lc); T-lchild = lc; /遍歷時(shí)先左后右，所以入棧時(shí)是左子樹(shù)先入，后入右子樹(shù)。 /由于堆棧(duzhn)是先入后出，所以必須先彈出右子樹(shù) Push(PTR, T);共二百七十五頁(yè) 僅知二叉樹(shù)的先序序列(xli)“abcdefg” 不能唯一確定一棵二叉樹(shù);(3) 由二叉樹(shù)的先序和中序序列(xli)建樹(shù) 如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf ”，則會(huì)如何？ 二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根共二百七十五頁(yè)a b c d e f gc b d a e g f例如(lr):aab

52、bccddeeffggabcdefg先序序列(xli)中序序列共二百七十五頁(yè)void CrtBT(BiTree& T, char pre, char ino, int ps, int is, int n ) ( c language)/ 已知preps.ps+n-1為二叉樹(shù)的先序序列，/ inois.is+n-1為二叉樹(shù)的中序序列，本算法由此兩個(gè)序列構(gòu)造二叉鏈表 ,ps為先序序列的開(kāi)始位置(wi zhi)，is為中序序列的開(kāi)始位置，n為序列長(zhǎng)度 if (n=0) T=NULL; else k=Search(ino, preps); /查詢先序序列中的 /第一個(gè)字符在中序序列中的位置 if (k

53、= -1) T=NULL; else / CrtBT 共二百七十五頁(yè)T=(BiTNode*)malloc(sizeof(BiTNode);T-data = preps;if (k=is) T-Lchild = NULL; /先序序列中第一個(gè)字 符在中序序列中也是第一個(gè)字符，則表示沒(méi)有左子樹(shù)else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is );if (k=is+n-1) T-Rchild = NULL; /先序序列中第一(dy) 個(gè)字符在中序序列中是最后一個(gè)字符，則表示沒(méi)有右子樹(shù)else CrtBT(T-Rchild, pre, ino, ps+1+(k

54、-is), k+1, n-(k-is)-1 );共二百七十五頁(yè)6、根據(jù)遍歷(bin l)序列構(gòu)造二叉樹(shù)例: 已知一棵二叉樹(shù)的先序遍歷序列(xli)為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試構(gòu)造這棵二叉樹(shù) 若已知二叉樹(shù)的先序和中序（或中序和后序）序列，即可構(gòu)造唯一的二叉樹(shù)。共二百七十五頁(yè)AEBCDF HI G JAFBEC DHIGJHGDCEFBAIJABFEGCJDH I先序遍歷(bin l)序列為 ABECDFGHIJ中序遍歷序列為 EBCDAFHIGJ共二百七十五頁(yè)6.5 線索(xin su)二叉樹(shù) 何謂(hwi)線索二叉樹(shù)？ 線索鏈表的遍歷算法 如何建立線索鏈表？共

55、二百七十五頁(yè) Here comes the typical question of mine: Why do we need threaded binary trees?Because I enjoy giving you headaches . Just kidding.Okay, think of a fullbinary tree with n nodes.How many links are there?How many of them are NULL?n + 1.Can I stand that?Of course not!You got it!Any clue on how to

56、improve the situation?We can replace the null links by “threads”which will make traversalseasier. You are such agenius !Oh well, I wish Id have really done it Then who should take the credit?They are A. J. Perlis and C. Thornton. Threaded Binary Trees14/16共二百七十五頁(yè)2 Binary TreesRule 1: If Tree-Left is

57、 null, replace it with a pointer to the inorder predecessor of Tree.Rule 2: If Tree-Right is null, replace it with a pointer to the inorder successor of Tree.Rule 3: There must not be any loose threads. Therefore a threaded binary tree must have a head node of which the left child points to the firs

58、t node.typedef struct ThreadedTreeNode *PtrTo ThreadedNode;typedef struct PtrToThreadedNode ThreadedTree;typedef struct ThreadedTreeNode int LeftThread; /* if it is TRUE, then Left */ ThreadedTree Left; /* is a thread, not a child ptr. */ ElementTypeElement; int RightThread; /* if it is TRUE, then R

59、ight */ ThreadedTree Right; /* is a thread, not a child ptr. */15/16共二百七十五頁(yè)2 Binary Trees+ADBCExample Given the syntax tree of an expression (infix)A + B C DFFF+FTATFFFFTDTTBTTCThead node16/16共二百七十五頁(yè)一、何謂(hwi)線索二叉樹(shù)？遍歷二叉樹(shù)的結(jié)果是:求得結(jié)點(diǎn)(ji din)的一個(gè)線性序列。ABCDEFGHK例如:先序序列: A B C D E F G H K中序序列: B D C A H G K F

60、 E后序序列: D C B H K G F E A共二百七十五頁(yè) 當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能(zh nn)找到結(jié)點(diǎn)的左右孩子信息，而不能直接得到結(jié)點(diǎn)在任一序列的前驅(qū)和后繼信息，這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。 如何保存(bocn)這種在遍歷過(guò)程中得到的信息呢？共二百七十五頁(yè)方法一： 在每個(gè)結(jié)點(diǎn)上增加兩個(gè)指針(zhzhn)域fwd和bkwd，分別指示結(jié)點(diǎn)在任一次序遍歷時(shí)得到的前驅(qū)和后繼信息。 顯然，這樣做使得結(jié)構(gòu)的存儲(chǔ)密度大大降低。方法二： 在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定存在n+1個(gè)空鏈域，利用這些空鏈域來(lái)存放(cnfng)結(jié)點(diǎn)的前驅(qū)和后繼的信息。共二百七十五頁(yè)指向該線性序列中的“前