考研暑期數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)

1、1n 這種觀點(diǎn)的典型代表是 Knuth。他認(rèn)為圖至少有一個(gè)頂點(diǎn)， 必須至少有一個(gè)頂點(diǎn)。樹(shù)不能是空樹(shù)，但 N 可以是空樹(shù)。N 是限制根的子樹(shù)最多不能超過(guò) N 棵的樹(shù)。n 隨著對(duì)樹(shù)討論的深入，人們放寬了對(duì)樹(shù)結(jié)構(gòu)的限制。若把樹(shù)當(dāng)作層次結(jié)構(gòu)單獨(dú)對(duì)待， 允許結(jié)點(diǎn)個(gè)數(shù)為0。這樣，樹(shù)與N 就沒(méi)有不可逾越的鴻溝了。n 從面向?qū)ο笥^點(diǎn)，N是樹(shù)的特殊實(shí)現(xiàn)：父類，N是子類。N繼承了樹(shù)的特性， 它還有增加的特性，例如清航考研樹(shù)和森林的概念n 樹(shù)的定義r 由n (n0) 個(gè)結(jié)點(diǎn)組成的有限集合：Ø 有一個(gè)特定的稱之為根(root)的結(jié)點(diǎn)；Ø 除根以外的其它結(jié)點(diǎn)劃分為m (m0) 個(gè)互不相交的有限集合T

2、1, T2, , Tm ，每個(gè)集合又是一棵樹(shù)，并且稱之為根的子樹(shù)。n 此定義是離散數(shù)學(xué)和圖論中給出的。它們把樹(shù)視為圖的一個(gè)極小連通子圖。有 n 個(gè)結(jié)點(diǎn)的樹(shù)有 n-1 條邊，而且不能有回路。清航考研第三章 樹(shù)與二樹(shù)的定義與基本概念二二遍歷二的計(jì)數(shù)線索二樹(shù)與樹(shù)的遍歷樹(shù)的應(yīng)用清航考研數(shù)據(jù)結(jié)構(gòu) 輔導(dǎo)第三章 樹(shù)與二計(jì)算機(jī)系清航考研2n 注意，結(jié)點(diǎn)的深度和結(jié)點(diǎn)的高度是不同的。結(jié)點(diǎn)的深度即結(jié)點(diǎn)所處層次，是從根向下逐層計(jì)算 的；結(jié)點(diǎn)的高度是從下向上逐層計(jì)算的：葉結(jié)點(diǎn)的高度為1, 其他結(jié)點(diǎn)的高度是取它的結(jié)點(diǎn)最大高度加一。n 樹(shù)的深度與高度相等。A樹(shù)的深度按離根最遠(yuǎn)的深度=3 BC葉結(jié)點(diǎn)算，樹(shù)的高度按D E F根

3、結(jié)點(diǎn)算，都是6。G Hl 葉結(jié)點(diǎn)也稱為終端結(jié)點(diǎn)，高度=4非葉結(jié)點(diǎn)也稱為非終端I結(jié)點(diǎn)。J K L清航考研 結(jié)點(diǎn) 子女 子孫 樹(shù)的度 結(jié)點(diǎn)的度 雙親 結(jié)點(diǎn)層次 樹(shù)深度 分支結(jié)點(diǎn) 兄弟 結(jié)點(diǎn)深度 樹(shù)高度 葉結(jié)點(diǎn) 祖先 結(jié)點(diǎn)高度 森林A1層BCD2層 depth = 4EFGHIJ3層 height = 4KLM4層清航考研樹(shù)的特點(diǎn)n 分層結(jié)構(gòu)，又是遞歸結(jié)構(gòu)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0 個(gè)或多個(gè)直接后繼。前驅(qū)A1層BCD2層depth = 4后繼EFGHIJ3層 height= 4KLM4層清航考研r 理論上樹(shù)不空樹(shù)，N可以是空樹(shù)；r 樹(shù)的子樹(shù)可以有序，也可以不要求有序，而N的

4、子樹(shù)必須有序。r N的定義也是遞歸的，遞歸到空樹(shù)終止；遞歸到只有一個(gè)結(jié)點(diǎn)的子樹(shù)。r 樹(shù)的子樹(shù)棵數(shù)不限，而N中根的子樹(shù)最多N棵。r 樹(shù)可以區(qū)分為外向樹(shù)和內(nèi)向樹(shù)，而N一般是外向樹(shù)，即有向的，從父。r 樹(shù)可以用N實(shí)現(xiàn)。二、B樹(shù)等又都是N的特殊情形。清航考研3性質(zhì)3對(duì)任何一棵二, 如果其葉結(jié)點(diǎn)有 n0 個(gè), 度為2 的非葉結(jié)點(diǎn)有 n2 個(gè), 則有n0n21證明：若為 1 的結(jié)點(diǎn)有 n 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為n，總邊數(shù)為 e ，則根據(jù)二的定義，n = n0+n1+n2e = 2n2+n1 = n-1因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1n0 = n2+1n 引申：可用于二各類結(jié)點(diǎn)

5、個(gè)數(shù)。清航考研性質(zhì)2高度為 h 的二最多有 2h -1個(gè)結(jié)點(diǎn)。(h1)證明用求等比級(jí)數(shù)前k項(xiàng)和的公式高度為 h 的二有 h 層，各層最多結(jié)點(diǎn)個(gè)數(shù)相加，得到等比級(jí)數(shù)，求和得：20 + 21 + 22 + + 2h-1 = 2h-1n 空樹(shù)的高度為 0，只有根結(jié)點(diǎn)的樹(shù)的高度為 1。清航考研二的性質(zhì)性質(zhì)1若二的層次從 1 開(kāi)始, 則在二的第 i 層最多有 2i-1 個(gè)結(jié)點(diǎn)。( i1)證明用數(shù)學(xué)歸納法r i = 1時(shí)，根結(jié)點(diǎn)只有1個(gè)，21-1 = 20 =1；r 若設(shè) i = k 時(shí)性質(zhì)成立，即該層最多有 2k-1 個(gè)結(jié)點(diǎn)，則當(dāng) i = k+1 時(shí)，由于第 k 層每個(gè)結(jié)點(diǎn)最多可有 2 個(gè)子女，第 k+

6、1 層最多結(jié)點(diǎn)個(gè)數(shù)可有 2*2k-1 = 2k 個(gè)，故性質(zhì)成立。清航考研二(Binary Tree)n 二 的定義一棵二 是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不相交的二 組成。n 這個(gè)定義是遞歸的。LRLR二的五種不同形態(tài)清航考研4性質(zhì)5如將一棵有n 個(gè)結(jié)點(diǎn)的完全二自頂向下，同一層自連續(xù)給結(jié)點(diǎn)編號(hào): 0, 1, 2, , n-1， 則有以：r 若i = 0, 則 i 無(wú)雙親；若i > 0, 則 i 的雙親為ë(i-1)/2û。r 若2*i+1 < n, 則 i 的為 2*i+1；若2*i+2 < n,

7、 則 i 的右子女為2*i+2。 0r 若 i 為偶數(shù), 且i != 0, 則12其為i-1；若 i 為 奇數(shù), 且i != n-1,3456則其右兄弟為i+1。7 89清航考研注意：n 求高度的另一公式為 ëlog2nû +1, 此公式對(duì)于 n = 0不適用。n 若設(shè)完全二中葉結(jié)點(diǎn)有 n0 個(gè), 則該二總的結(jié)點(diǎn)數(shù)為 n = 2n0, 或 n = 2n0 1。n 若完全二的結(jié)點(diǎn)數(shù)為奇數(shù)，沒(méi)有度為1的結(jié)點(diǎn)；為偶數(shù)，有一個(gè)度為1的結(jié)點(diǎn)。n 右圖為理想平衡樹(shù)，23-上層的，第24-1h 層結(jié)點(diǎn)分布在各處。清航考研1性質(zhì)4具有 n (n0) 個(gè)結(jié)點(diǎn)的完全二的高度為élog

8、2(n+1)ù證明：設(shè)完全二的高度為 h，則有2h-1-1n 2h -1上面h-1層結(jié)點(diǎn)數(shù)第h層的最大結(jié)點(diǎn)數(shù)變形 2h-1n+12h取對(duì)數(shù)23-24-1h-1log2(n+1)h有h = élog2(n+1)ù清航考研1定義1 滿二(Full Binary Tree)定義2 完全二(Complete Binary Tree)r 若設(shè)二的高度為h，則共有 h 層。除第 h 層外，其它各層 (1h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二。清航考研5二的二叉鏈表表示指針右子女指針dataleftChildrightChildn 使用

9、二叉鏈表，找子女的時(shí)間復(fù)雜度為O(1)，找雙親的時(shí)間復(fù)雜度為O(log2i)O(i )，其中，i 是該結(jié)點(diǎn)編號(hào)。清航考研l(wèi)eftChilddatarightChild情形: 只有右的二n 對(duì)于完全二，因結(jié)點(diǎn) 0編號(hào)連續(xù)，數(shù)據(jù)密2集，適于用順序表示；n 對(duì)于二，用鏈表6表示較好；清航考研二的順序表示0012345678 9 10 11 12 13完全二二的順序表示的順序表示清航考研01235678110123456789注意：如果完全二各層次結(jié)點(diǎn)從1 開(kāi)始編號(hào)：1, 2, 3, , n，則有以：r 若i = 1, 則 i 無(wú)雙親；若i > 1, 則 i 的雙親為ëi / 2

10、51;。r 若2*i <= n, 則 i 的為 2*i； 若2*i +1 <= n, 則 i 的右子女為2*i+1r 若 i 為奇數(shù), 且i != 1,1則其為i-1；23若 i 為偶數(shù), 且i != n,4567則其右兄弟為i+1。8 9 10清航考研6二遍歷n 樹(shù)的遍歷就是按某種次序的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)一次且僅一次。設(shè)r 根結(jié)點(diǎn)記作V，r 遍歷根的左子樹(shù)記作L，r 遍歷根的右子樹(shù)記作R，n 則可能的遍歷次序有r 前序 VLR鏡像 VRLr 中序 LVR鏡像 RVLr 后序 LRV鏡像RLV清航考研二的定義typedef char ElemType ;/ 樹(shù)結(jié)點(diǎn)數(shù)據(jù)類型typed

11、ef struct node / 樹(shù)結(jié)點(diǎn)定義ElemType data ;/結(jié)點(diǎn)數(shù)據(jù)域struct node *leftChild , *rightChild ;/子女指針域 BinTreeNode ;typedef BinTreeNode *BinTree ;/ 樹(shù)定義，代表樹(shù)的根指針清航考研二鏈表表示的示例rootrootroot ABCDEF二二叉鏈表三叉鏈表清航考研ÙEÙÙFÙÙEÙÙFÙÙCÙDÙCÙDBBAÙÙAÙ二的三叉鏈表表示指針

12、雙親指針 右子女指針parentdataleftChildrightChildn 使用三叉鏈表，找子女、雙親的時(shí)間都是O(1)。清航考研l(wèi)eftChilddataparentrightChild7二遞歸的前序遍歷算法void PreOrder (BinTreeNode *T) if (T != NULL) visit (T->data) ;PreOrder (T->leftChild); PreOrder (T->rightChild);n 與中序遍歷算法相比，visit() 操作放在兩個(gè)子樹(shù)遞歸前序遍歷的最前面。清航考研前序遍歷 (Preorder Traversal)前序

13、遍歷二算法的框架是：-n 若二為空，則空操作；n 否則+/u 根結(jié)點(diǎn) (V)；u 前序遍歷左子樹(shù) (L)；a*efu 前序遍歷右子樹(shù) (R)。b-遍歷結(jié)果- + a * b - c d / e fcd清航考研二遞歸的中序遍歷算法void InOrder ( BinTreeNode *T ) if ( T != NULL ) InOrder ( T->leftChild );visit ( T->data ) ;InOrder ( T->rightChild );n visit() 是輸出數(shù)據(jù)值的操作，在實(shí)際使用時(shí)可用相應(yīng)的操作來(lái)替換。清航考研中序遍歷 (Inorder Tra

14、versal)中序遍歷二算法的框架是：n 若二為空，則空操作；-n 否則+/u 中序遍歷左子樹(shù) (L)；u 根結(jié)點(diǎn) (V)；a*efu 中序遍歷右子樹(shù) (R)。b-遍歷結(jié)果a + b * c - d - e / fcd清航考研8求二高度的遞歸算法int Height ( BinTreeNode *T ) if (T = NULL) return 0; else int m = Height (T->leftChild ); int n = Height (T->rightChild); return (m > n) ? m+1 : n+1 ;n 空樹(shù)的高度為 0；非空樹(shù)情形，

15、先計(jì)算根結(jié)點(diǎn)左右子樹(shù)的高度，取大者再加一得到二高度。清航考研應(yīng)用二遍歷的事例計(jì)算二結(jié)點(diǎn)個(gè)數(shù)的遞歸算法int Count (BinTreeNode *T) if (T = NULL) return 0;else return 1+ Count (T->leftChild)+ Count (T->rightChild);n 空二 的結(jié)點(diǎn)個(gè)數(shù)為 0，可直接計(jì)算；否則可分別計(jì)算左、右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，再相加得到總結(jié)點(diǎn)個(gè)數(shù)。清航考研二遞歸的后序遍歷算法void PostOrder (BinTreeNode *T) if (T != NULL) PostOrder (T->leftChil

16、d); PostOrder (T->rightChild); visit (T->data) ;n 與中序遍歷算法相比，visit() 操作放在兩個(gè)子樹(shù)遞歸前序遍歷的最后面。清航考研后序遍歷 (Postorder Traversal)后序遍歷二算法的框架是：-n 若二為空，則空操作；n 否則+/u 后序遍歷左子樹(shù) (L)；u 后序遍歷右子樹(shù) (R)；a*efu 根結(jié)點(diǎn) (V)。b-遍歷結(jié)果cda b c d - * + e f / -d清航考研9void InOrder(BinTreeT) stack S; InitStack(S);/遞歸工作棧BinTreeNode *p = T

17、;/初始化do while (p != NULL)/ 子空找中序第一個(gè) Push(S, p); p = p->leftChild; /邊找邊進(jìn)棧if (!StackEmpty(S) /棧非空Pop(S, p);/子序第一個(gè)退棧visit(p->data);/之p = p->rightChild;/向右子樹(shù)走 while ( p != NULL | !StackEmpty(S) );清航考研利用棧的中序遍歷的非遞歸算法abcde左空 退棧 左空 退棧 退棧左空 退棧右空 退棧?？战Y(jié)束清航考研ccecadaabavoid PreOrder(BinTree T) stack S;

18、InitStack(S );/遞歸工作棧BinTreeNode * p = T; Push (S, NULL); while (p != NULL) visit(p->data) ;if (p->rightChild != NULL) Push(S, p->rightChild);if (p->leftChild != NULL)p = p->leftChild ;/進(jìn)左子樹(shù)else Pop(S, p);/左子樹(shù)空, 進(jìn)右子樹(shù)清航考研利用棧的前序遍歷的非遞歸算法abcde退棧 退棧abdce進(jìn)棧 進(jìn)棧左進(jìn)cddc空左進(jìn) 左進(jìn) 左進(jìn) 左進(jìn) 退棧b空空eÙ

19、結(jié)束清航考研ÙcÙdcÙcÙ10while (succ && !StackEmpty(S ) Pop(S, w); p = w.ptr;switch (w.tag) /棧頂tag標(biāo)記case L : w.tag = R; Push(S, w); succ = 0;p = p->rightChild ; break; case R : visit(p->data) ; while ( !StackEmpty(S ) );清航考研利用棧的后序遍歷的非遞歸算法void PostOrder(BinTree T) stack S; In

20、itStack(S ); StackNode w; BinTreeNode *p = T;do while (p != NULL) /向左子樹(shù)走w.ptr = p; w.tag = L; Push(S, w); p = p->leftChild ;int succ = 1;/繼續(xù)循環(huán)標(biāo)記清航考研abcde清航考研aRcRaRc LaRe RcLaReLcLaRaRaLbRaLdRbRaLdLbRaLbRaLbLaLaL利用棧的后序遍歷的非遞歸算法n 后序遍歷時(shí)使用的棧的結(jié)點(diǎn)定義typedef struct BinTreeNode *ptr;/結(jié)點(diǎn)指針enum tag L, R ;/該結(jié)點(diǎn)

21、退棧標(biāo)記 StackNode;n 根結(jié)點(diǎn)的r tag = L，表示從左子樹(shù),右子樹(shù)。r tag = R, 表示從右子樹(shù),根。清航考研ptrtagL,R11n 例如, 有 3 個(gè)數(shù)據(jù) 1, 2, 3 ，可得 5 種不同的二。它們的前序排列均為 123，中序序列可能是 123，132，213，231，321。111112223223333n 那么，如何推廣到情形呢？首先，只有一個(gè)結(jié)點(diǎn)的不同二只有一個(gè)；有 2 個(gè)結(jié)點(diǎn)的不同二只有 2 種，其他情況呢？清航考研n 如果前序序列固定不變，給出不同的中序序列， 可得到不同的二。112626347378589459n 問(wèn)題是：固定前序排列，選擇所有可能的中序

22、排列，可以構(gòu)造出多少種不同的二？清航考研AAABEKCGBEKCGBEHDFHFHFKCG ADDBEHFCDKG清航考研二的計(jì)數(shù)n 由二的前序序列和中序序列可唯一地確定一棵二。n 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 構(gòu)造二過(guò)程如下：AAHBDFEKCGBEKCG HDF清航考研12線索二(Thed Binary Tree)n 又稱為穿線樹(shù)。n 通過(guò)二 遍歷，可將二 中所有結(jié)點(diǎn)的數(shù)據(jù)排列在一個(gè)線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。n 希望不必每次都通過(guò)遍歷找出這樣的線性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼 記在樹(shù)的 結(jié)構(gòu)中，以

23、后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。n 為此，在二結(jié)點(diǎn)中增加線索 。清航考研關(guān)于棧的進(jìn)一步討論n 問(wèn)題是：當(dāng)進(jìn)棧元素的編號(hào)為1, 2, , n時(shí)，可能的出棧序列有多少種？n 可將Catalan函數(shù)應(yīng)用在此問(wèn)題：設(shè)有 n 個(gè)元素按序號(hào)1, 2, , n 進(jìn)棧，輪流讓 1在出棧序列的第1, 第2, 第n位，則可能的出棧序列數(shù)為：n-1åmi *mn-i-1 = m0 *mn-1 + m1 *mn-2 +L+mn-1 *m0i=0n 推導(dǎo)結(jié)果為：n -11å mi * mn - i-1 = n + 1n i 0清航考研計(jì)算具有 n 個(gè)結(jié)點(diǎn)的不同二的棵數(shù)n - 1b n = &#

24、229;b i × b n - i - 11i = 0bb函數(shù)in- i- 1n Catalan函數(shù)b =1=1 (2n)!nn + 1nn + 1 n!×n!n 例131 6 × 5 × 4b 3 =C6 = 53 + 14 3 × 2 × 1b = 1 C4 = 1=44 + 18清航考研有0個(gè), 1 個(gè), 2個(gè), 3 個(gè)結(jié)點(diǎn)的不同二如下b0 =1b1 =1b2 =2b3 =5b4 =14清航考研13線索二的結(jié)構(gòu)定義typedef int DataType ; typedef struct node int ltag , rtag

25、 ;struct node *leftChild , *rightChild ; DataType data ; TNode , *ThTree ;n 注意，線索二在樹(shù)結(jié)點(diǎn)中增加了ltag和rtag， 改變了二的結(jié)構(gòu)。清航考研中序線索二及其鏈表表示rootabpred csuccpredsuccsuccpred desucc predpredsucc清航考研1E11D10C11B00A0leftChildltagdatartagrightChildn 這種設(shè)計(jì)的缺點(diǎn)是每個(gè)結(jié)點(diǎn)增加兩個(gè)指針，當(dāng)結(jié)點(diǎn)數(shù)很大時(shí)消耗較大。n 改造樹(shù)結(jié)點(diǎn)，將 pred 指針和 succ 指針壓縮到leftChild 和

26、rightChild 的空閑指針中，并增設(shè)兩個(gè)標(biāo)志 ltag 和 rtag，指明指針是指示子女還是前驅(qū)后繼。后者稱為線索。n ltag (或rtag) = 0，表示相應(yīng)指針指示（或右子女結(jié)點(diǎn)）；n ltag (或rtag) = 1, 表示相應(yīng)指針為前驅(qū)（或后繼） 線索。清航考研l(wèi)eftChildltagdatartagrightChild線索 (Th)n 增加前驅(qū)Pred指針和后繼Succ指針的二rootapredsuccb succ pred csuccC predsuccsucc pred p edsuccdesucc predpred清航考研EDBApredleftChilddatari

27、ghtChildsucc14pre = NULLTt清航考研Ù0E0ÙÙ0D0Ù0C0ÙÙ0B00A0void CreateInTh(ThTree T) ThNode *pre = NULL; /前驅(qū)指針if ( T != NULL ) /空, 線InTh(T, pre);/中序遍歷線索二pre->rightChild = NULL; pre->rtag = 1;/后處理, 中序最后一個(gè)結(jié)點(diǎn)n 通過(guò)該主程序?qū)崿F(xiàn)了對(duì)二的中序線。它是基于二的中序遍歷實(shí)現(xiàn)的。清航考研if ( pre && pre->rig

28、htChild = NULL ) pre->rightChild = t; pre->rtag = 1; / 建立前驅(qū)結(jié)點(diǎn) pre 的后繼線索pre = t;/ 前驅(qū)跟上當(dāng)前指針I(yè)nTh(t->rightChild, pre);/ 遞歸, 右子樹(shù)線n 使用此函數(shù)可以把以 t 為根的子樹(shù)一次中序線，但中序下最后一個(gè)結(jié)點(diǎn)的后繼線索沒(méi)有加上，指針 pre 在指示這一結(jié)點(diǎn)。清航考研通過(guò)中序遍歷建立中序線索二void InTh(ThNode *t, ThNode *& pre)/預(yù)設(shè)了一個(gè) pre 指針，指示 t 的中序前驅(qū)，在主/預(yù)置為NULLif (t != NULL) I

29、nTh(t->leftChild , pre);/遞歸, 左子樹(shù)線if (t->leftChild = NULL) t->leftChild = pre; t->ltag = 1; /建立當(dāng)前結(jié)點(diǎn) t 的前驅(qū)線索清航考研15preTt清航考研1E0Ù1D10C0ÙÙ1B00A0tTpre清航考研Ù0E0Ù1D10C0ÙÙ1B00A0Tpret清航考研Ù0E0Ù1D0Ù0C0ÙÙ1B00A0pre = NULLT t清航考研Ù0E0Ù

30、Ù0D0Ù0C0ÙÙ1B00A016ThNode * First ( ThNode *t ) /函數(shù)返回以*t 為根的線索二中的中序序列下/的第一個(gè)結(jié)點(diǎn)ThNode *p = t;while ( p->ltag = 0 ) p = p->leftChild ; return p;/最左下的結(jié)點(diǎn)ThNode * Next ( ThNode * p ) /函數(shù)返回在線索二中結(jié)點(diǎn)*p 在中序下的后/繼結(jié)點(diǎn)清航考研尋找結(jié)點(diǎn) p 在中序下的后繼Aif (p->rtag =1)后繼為 p->rightChildBCelse /p->rt

31、ag != 1后繼為結(jié)點(diǎn) p 右子樹(shù)DEFq 中的中序下的第一GHI個(gè)結(jié)點(diǎn)JK清航考研T后處理pre清航考研1E11D10C1ÙÙ1B00A0Ttpre清航考研1E11D10C0ÙÙ1B00A017后序線索二Ap->rtag=1?后繼線索 =¹ 右子女BC后繼為q=p->parentp->rightChildq=NULL?DE¹=后序序列q->rtag=1 |無(wú)后繼D B E C Aq->rightChild=p?n 在后序線索二=¹中尋找當(dāng)后繼為q后繼為q的右子前結(jié)點(diǎn)的后繼后序下第一個(gè)結(jié)點(diǎn)清航

32、考研前序線索二Ap->ltag=1?前驅(qū)線索 =¹BCp->righttChild后繼為= NULLp->leftChildDE=¹前序序列 無(wú)后繼后繼為A B D C Ep->rightChildn 在前序線索二中尋找當(dāng)前結(jié)點(diǎn)的后繼清航考研尋找結(jié)點(diǎn) p 在中序下的前驅(qū)Aif (p->ltag =1)BC前驅(qū)為 p->leftChildelse /p->leftTh=0DEF前驅(qū)為結(jié)點(diǎn)p 左子樹(shù)中序下的最后一個(gè)結(jié)GHI點(diǎn)JKL清航考研if ( p->rtag = 0 ) return First(p->rightChil

33、d);/p->rtag=0, 后繼為右子序第一個(gè)結(jié)點(diǎn)else return p->rightChild ;/p->rtag=1, 直接返回后繼線索void Inorder ( ThNode * t ) /以 t 為根的線索二的中序遍歷ThNode * p;for ( p = First (t); p != NULL; p = Next (p) )cout << p->data << endl;清航考研18ABCDE FG空鏈域2n+1個(gè)等數(shù)量的鏈域清航考研datachild1child2child3childdGÙÙÙ

34、;FÙÙÙEÙÙÙDÙÙCÙÙÙBÙA子女指針表示n 一個(gè)合理的想法是在結(jié)點(diǎn)中存放指向每一個(gè)子女結(jié)點(diǎn)的指針。但由于各個(gè)結(jié)點(diǎn)的子女?dāng)?shù)不同，每個(gè)結(jié)點(diǎn)設(shè)置數(shù)目不等的指針，將很難管理。n 為此，設(shè)置等長(zhǎng)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)相等，等于樹(shù)的度（degree）。n 這保證結(jié)點(diǎn)有足夠的指針指向它的結(jié)點(diǎn)。但可能產(chǎn)生很多空閑指針，造成浪費(fèi)。清航考研子女鏈表表示A01BCD2E FG3456n 無(wú)序樹(shù)情形鏈表中各結(jié)點(diǎn)順序任意，有序樹(shù)必須自鏈接各個(gè)子女結(jié)點(diǎn)。清航考研632514ABCDEF

35、G樹(shù)與樹(shù)的遍歷n 樹(shù)的表示雙親表示A0 1 2 3 4 5 6dataBCDparent E FGr 為了操作實(shí)現(xiàn)的方便，有時(shí)會(huì)規(guī)定結(jié)點(diǎn)的存放順序。例如，可以按樹(shù)的前序次序存放的各個(gè)結(jié)點(diǎn)，或按樹(shù)的層次次序安排所有結(jié)點(diǎn)。清航考研ABCDEFG-100011319尋找雙親 子女 兄弟的操作TreeNode *FindParent (TreeNode *T, TreeNode *p) /在以 T 為根的找結(jié)點(diǎn) p 的雙親if (T = NULL | p = NULL) return NULL; TreeNode *q = T->firstChild, *s;while (q != NULL &

36、amp;& q != p) /的長(zhǎng)子的兄弟鏈,遞歸在子搜索if (s = FindParent (q, p) ) != NULL) return s;/在以 q 為根的子樹(shù)找到 p 的雙親，返回q = q->nextSibling ;清航考研-右兄弟表示的樹(shù)的結(jié)構(gòu)定義typedef int DataType ; typedef struct node DataType data ;struct node *firstChild, *nextSibling ; TreeNode , *Tree ;n 注意，雖然此定義與二的類似，操作也類似，但語(yǔ)義是不同的。n 樹(shù)結(jié)構(gòu)是遞歸的，可用遞

37、歸函數(shù)實(shí)現(xiàn)相應(yīng)操作。清航考研樹(shù)的-右兄弟表示ABC DE FG清航考研GFDCEBAdatafirstChildnextSibling子女-兄弟表示n 也稱為樹(shù)的二表示。結(jié)點(diǎn)構(gòu)造為：n firstChild 指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無(wú)序樹(shù)時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。n nextSibling 指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在時(shí)總是有順序的。n 若想找某結(jié)點(diǎn)的，可先找firstChild,再反復(fù)用 nextSibling 沿鏈掃描。清航考研datafirstChildnextSibling20樹(shù)的先根次序遍歷的遞歸算法void PreOrder (TreeNode *t) /以指針

38、 t 為根, 先根次序遍歷if ( t != NULL ) visit ( t->data ) ;/ 根結(jié)點(diǎn)TreeNode *p = t->firstChild ; /第一棵子樹(shù)while ( p != NULL ) PreOrder (p);/遞歸先根遍歷子樹(shù)p = p->nextSibling ;清航考研樹(shù)的先根次序遍歷n 當(dāng)空時(shí)Ar 根結(jié)點(diǎn)BB C Dr 依次先根遍歷根的各棵子樹(shù)ECn 遍歷 ABEFCDGE FG對(duì)應(yīng)二前序遍歷 ABEFCDGFDn 樹(shù)的先根遍歷結(jié)果與其對(duì)應(yīng)二G表示的前序遍歷結(jié)果相同n 樹(shù)的先根遍歷可以借助對(duì)應(yīng)二的前序遍歷算法實(shí)現(xiàn)清航考研if ( p

39、 != NULL ) return p->nextSibling ; else return NULL;樹(shù)的遍歷n 深度優(yōu)先遍歷A二表示Ar 先根次序遍歷BCDBr 后根次序遍歷ECn 廣度優(yōu)先遍歷E FGFDG清航考研if (q != NULL && q = p) return T ; /找到雙親else return NULL; /未找到雙親TreeNode * FindfirstChild (TreeNode * p) /在找結(jié)點(diǎn) p 的第一個(gè)子女if ( p != NULL ) return p->firstChild ; else return NULL;

40、TreeNode *FindnextSibling (TreeNode *p) /在找結(jié)點(diǎn) p 的兄弟清航考研21while ( QueueEmpty(Qu) = 0 ) DeQueue(Qu, p); visit(p->data) ;/隊(duì)列中取一個(gè)并之p = p->firstChild ;/待結(jié)點(diǎn)的子女結(jié)點(diǎn)進(jìn)隊(duì)列while ( p != NULL ) EnQueue ( Qu, p ); p = p->nextSibling ;清航考研廣度優(yōu)先(層次次序)遍歷n 按廣度優(yōu)先次序遍歷樹(shù)的結(jié)果A ABCDEFGBBCDn 廣度優(yōu)先遍歷算法ECvoid LevelOrder (T

41、ree T) E FG/分層遍歷樹(shù)，算法用到一個(gè)隊(duì)列FDQueue Qu; InitQueue(Qu);GTreeNode *p;if (T != NULL) /樹(shù)不空EnQueue(Qu, T) ; /根結(jié)點(diǎn)進(jìn)隊(duì)列清航考研樹(shù)的后根次序遍歷的遞歸算法void PostOrder (TreeNode *t) /以指針 t 為根, 按后根次序遍歷樹(shù)if ( t != NULL ) TreeNode *p = t->firstChild ; while ( p != NULL ) PostOrder ( p );p = p->nextSibling ;visit ( t->data

42、 ) ;/最后根結(jié)點(diǎn)清航考研樹(shù)的后根次序遍歷n 當(dāng)空時(shí)Ar 依次后根遍歷根的各棵子樹(shù)BB C Dr 根結(jié)點(diǎn)ECn 遍歷 EFBCGDAE FG對(duì)應(yīng)二中序遍歷 EFBCGDAFDn 樹(shù)的后根遍歷結(jié)果與其對(duì)應(yīng)二G表示的中序遍歷結(jié)果相同n 樹(shù)的后根遍歷可以借助對(duì)應(yīng)二的中序遍歷算法實(shí)現(xiàn)清航考研22二轉(zhuǎn)換為森林的規(guī)則 如果 B 為空，則對(duì)應(yīng)的森林 F 也為空。 如果 B 非空，則Ø FT1 的根為 B 的根；Ø T1 的根的子樹(shù)森林 T11, T12, , T1m 是由B的根的左子樹(shù) LB 轉(zhuǎn)換而來(lái)；Ø F 中除了 T1 之外其余的樹(shù)組成的森林 T2, T3, , Tn 是

43、由 B 的根的右子樹(shù)RB 轉(zhuǎn)換而成的森林。清航考研森林轉(zhuǎn)化成二的規(guī)則 若 F 為空，即 n = 0，則對(duì)應(yīng)的二B 為空樹(shù)。 若 F 不空，則Ø 二B 的根是 F 第一棵樹(shù) T1 的根；Ø 其左子樹(shù)為 B (T11, T12, , T1m )，其中，T11, T12, , T1m 是 T1 的根的子樹(shù)；Ø 其右子樹(shù)為 B (T2, T3, , Tn )，其中，T2,T3, , Tn 是除 T1 外其它樹(shù)的森林。清航考研T1T2T3AFHAB C D GIJBEKC3 棵樹(shù)的森林DFTTTEGH1 A2 F3 HIBGIKJCKJ森林的二表示DE各棵樹(shù)的二表示清航考研

44、森林與二的轉(zhuǎn)換n 將樹(shù)化為二表示就是用樹(shù)的子女-兄弟表示來(lái)樹(shù)的結(jié)構(gòu)。n 森林與二表示的轉(zhuǎn)換可以借助樹(shù)的二表示來(lái)實(shí)現(xiàn)。清航考研23AT1T2T3BAFHCDFB C DGIJEGHEKIKJn 森林的先根次序遍歷的結(jié)果序列ABCDE FG HIKJn 這相當(dāng)于對(duì)應(yīng)二的前序遍歷結(jié)果。清航考研森林的先根次序遍歷n 若森林F = Ø，返回；否則森林的根（也是第一棵樹(shù)的根）r1； 先根遍歷森林第一棵樹(shù)的根的子樹(shù)森林T11, , T1k； 先根遍歷森林中除第一棵樹(shù)外其他樹(shù)組成的森林T2, .,Tm。n 注意， 是一個(gè)循環(huán)，對(duì)于每一個(gè)T1i，執(zhí)行樹(shù)的先根次序遍歷； 是一個(gè)遞歸過(guò)程，重新執(zhí)行 T2

45、為第一棵樹(shù)的森林的先根次序遍歷。清航考研森林的遍歷n 森林的遍歷也分為深度優(yōu)先遍歷（先根次序遍歷和中根次序遍歷）和廣度優(yōu)先遍歷。深度優(yōu)先遍歷n 給定森林 F，若 F = Ø，則遍歷結(jié)束。否則n 若F = T1 = r1, T11, , T1k , T2, ., Tm，則可以導(dǎo)出先根遍歷、中根遍歷兩種 。其中，r1 是第一棵樹(shù)的根結(jié)點(diǎn)，T , , T k是第一棵樹(shù)的子樹(shù)森林，T2, .,Tm的森林。清航考研例題n 設(shè)森林中有三棵樹(shù)，第一、第二和第三棵 的結(jié)點(diǎn)個(gè)數(shù)分別為 m1，m2 和 m3。那么在由該森林轉(zhuǎn)化成的二 中根結(jié)點(diǎn)的右子樹(shù)上有（ ） 個(gè)結(jié)點(diǎn)。A. m1+m2B. m2+m3C

46、. m3+m1D. m1+m2+m3【解答】在由森林轉(zhuǎn)化成的二 中根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)是除第一棵外其他樹(shù)上的結(jié)點(diǎn)，應(yīng)有m2+m3 個(gè)，故選擇 B。清航考研24樹(shù)的應(yīng)用n 二叉排序樹(shù)n 平衡二n Huffman樹(shù)n 堆n 并清航考研廣度優(yōu)先遍歷（層次序遍歷）n 若森林 F 為空，返回；A否則B 依次遍歷各棵樹(shù)的C根結(jié)點(diǎn)；DF 依次遍歷各棵樹(shù)根H結(jié)點(diǎn)的；EG 依次遍歷這些子女I結(jié)點(diǎn)的子女結(jié)點(diǎn)；KJ ¼¼AFH BCDGIJ EK清航考研AT1T2T3BAFHCB C DGIJDFEGHEKIKJn 森林的中根次序遍歷的結(jié)果序列BCEDA GF KIJHn 這相當(dāng)于對(duì)應(yīng)二中序遍

47、歷的結(jié)果。清航考研森林的中根次序遍歷n 若森林 F = Ø，返回；否則 中根遍歷森林 F 第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林T11, , T1k；森林的根結(jié)點(diǎn) r1； 中根遍歷森林中除第一棵樹(shù)外其他樹(shù)組成的森林T2, ., Tm。n 注意，與先根次序遍歷相比， 根結(jié)點(diǎn)的時(shí)機(jī)不同。所以在的情形，對(duì)以T2為第一棵樹(shù)的森林遍歷時(shí)，重復(fù)執(zhí)行的操作。清航考研25后續(xù)講的特性則定義一定成立。就是說(shuō)，如果一棵二 任一結(jié)點(diǎn)的關(guān)鍵字值都大于 的關(guān)鍵字值，小于右子女的關(guān)鍵字值，則它一定是二叉排序樹(shù)。這就不一定了。右圖描述的二 滿足25任一結(jié)點(diǎn)的關(guān)鍵字值一定大 1535于的關(guān)鍵字值，小于右子女的關(guān)鍵字值，但它不 104530是二叉排序樹(shù)。2050清航考研例題n 一棵二 是二叉排序樹(shù)的（ ）條件是 任一結(jié)點(diǎn)的關(guān)鍵字值都大于的關(guān)鍵字值，小于右子女的關(guān)鍵字值。A. 充分但不必要B. 必要但不充分C. 充分且必要D. 既不