數(shù)據(jù)結構樹的定義和基本術語課件

1、1、樹的定義和基本術語 基本概念樹：n o 個結點的集合，根、其余結點分為 m = 0 個集合，每一個集合本身又是一棵樹（子樹）度、葉子、父結點、兒子結點、祖先結點、層次、深度（或高度）有序樹及無序樹森林 m = 0 棵互不相交樹的集合其它表示方法： ( A(B(L,E),C(F),D(G(I),H)書上還介紹了兩種，請參考。ABCDEFGHILE、G：高度為 4 、度為 3 的樹(有的書稱之為 3 次樹)2、二叉樹2、性質：性質1：在二叉樹的第 i 層上至多有 2 i-1個結點BCDEFLA1層：結點個數(shù) 21-1=20 個2層：結點個數(shù) 22-1=21 個3層：結點個數(shù) 23-1=22 個

2、性質2：深度為 K 的二叉樹至多有2 k- 1 個結點性質3：二叉樹的葉子結點數(shù) n0 等于度為 2 的結點數(shù)n2 + 1 CEFLA1、定義空或有一個根，根有左子樹、右子樹；而左右子樹本身又是二叉樹。和樹的區(qū)別：可為空，左右子樹有序，不可顛倒。性質4：具有 n 個結點的完全二叉樹的深度為 log2n + 12、二叉樹BCDEFLAPSQRUBCDEFLAPSQRXUWV滿二叉樹:每層結點數(shù)最多完全二叉樹: 滿二叉樹 或 從滿二叉樹最底層從右向左 依次去掉若干結點形成的2、二叉樹BCDEFLAPSQRU性質5：對一棵有 n 個結點的完全二叉樹按照從第一層（根所在的層次到最后一層，并且 每一層都

3、按照從左到右的次序進行編號。根結點的編號為 1，最后一個結點的編號 為 n。 1：對任何一個編號為 i 的結點而言，它的左兒子的編號為 2i( 若 2i = n) ,而右兒子的 編號為 2i+1(若 2i +1 = n)。 2：對任何一個編號為 j 的結點而言，它的父親結點的的編號為 j/2 。根結點無父結 點。1211109876543212、二叉樹3、二叉樹的存儲結構： 順序存儲結構： 一般情況：ABCDEFGHIL# define MAX_SIZE 10typedef struct BiTNode TELemType data; int lchild; int rchild; BitTN

4、ode;typdef BitTNode SqBiTreeMAX_SIZE; SqBiTree bt; A 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1I -1 -1L -1 4 0123456789rchild lchilddata 應用范圍：適用于二叉樹上的結點個數(shù)已知，或不支持動態(tài)存儲分配的高級語言。2、二叉樹3、二叉樹的存儲結構： 順序存儲結構： 特殊情況：# define MAX_SIZE 11typedef struct BiTNode TELemType data; int lchild; int rchild; Bit

5、TNode;typedef BitTNode SqBiTreeMAX_SIZE; SqBiTree bt; A 2 3 B 4 5 C 6 7 D 8 9 E 10 0 F 0 0 G 0 0 H 0 0I 0 0L 0 0012345678910rchild lchilddata 應用范圍：適用于完全二叉樹，且結點個數(shù)已知。DCGEFBAHIL2、二叉樹3、二叉樹的存儲結構： 順序存儲結構： 特殊情況：若不是完全二叉樹，許多數(shù)據(jù)場為空，不合算。如下例所示：# define MAX_SIZE 10typedef TELemType SqBiTreeMAX_SIZE; SqBiTree bt;

6、A B HI 0123456789DBAHI2、二叉樹3、二叉樹的存儲結構： 鏈接存儲結構： 僅定義結點的類型即可。ABCDEFGHILtypedef struct BiTNode TELemType data; struct BiTNode * lchild; struct BiTNode * rchild; BitTNode, * BiTree;BiTree p; data lchild rchild標準形式：（二叉鏈表）data lchild rchild parenttypedef struct BiTNode TELemType data; struct BiTNode * lchi

7、ld; struct BiTNode * rchild; struct BiTNode * parent; BitTNode, * BiTree;BiTree p; 廣義標準形式：（三叉鏈表）3、遍歷二叉樹和線索二叉樹BCDELAXW1、遍歷二叉樹：設 N 代表根節(jié)點，L 代表左子樹，R 代表右子樹。 a. 前序分析：結點的左兒子、左孫子、左后代、 將連續(xù)輸出。結點的右兒子將在結點、結點的左 NLR 子樹全部輸出之后才輸出。 b. 中序分析：最先輸出的結點是根結點的最左的左后代。將二叉樹中的結點投影到水平軸線上，則得到 LNR 中序遍歷的序列。 c. 后序分析：根結點（或子樹的根結點）將在它的

8、左、右子樹的結點輸出之后。因此，根結點（或子樹 LRN 的根結點）在中序序列中的序號等于它的左右子樹的結點個數(shù) 左右子樹中的最先被訪 問的結點的序號。注意，結點、右父親、右祖父、 將連續(xù)輸出。前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXWB L E A C W X D3、遍歷二叉樹和線索二叉樹BCDELA1、遍歷二叉樹：續(xù)前序的程序實現(xiàn)：1、根結點進棧2、結點出棧，被訪問3、結點的右、左兒子（非空）進棧4、反復執(zhí)行 2、3 ，至?？諡橹?。前序：A、L、B、E、C、De.g:A出棧訪問L出棧訪問B出棧訪問E出棧訪問C出

9、棧訪問D出棧訪問后，?？战Y束A進棧C、L進棧E、B進棧D進棧3、遍歷二叉樹和線索二叉樹1、遍歷二叉樹：續(xù)中序的程序實現(xiàn)：1、結點（初始時是根結點）進棧，沿左指針查找左兒子。2、若有左兒子，返回第一步。3、若無左兒子，判?？?？空則結束。非空，棧頂結點出棧 訪問。轉向右子樹，返回1。e.g:BCDELAXW中序：B、L、E、 A、C、W、 X、Dinitstack(s);push(s,t); / t 是根結點while (!stackempty(s) while (Gettop(s,p) & p ) / 有值且非空時 push(s, p-lchild)； / null 值可能進棧 pop (s,p

10、); / 空指針退棧 if (!stackempty(s) / 訪問結點，向右一步 pop(s, p); visit( p-data); push(s,p-rchild); 3、遍歷二叉樹和線索二叉樹1、遍歷二叉樹：設根結點初始時非空后序算法：1、結點（初始時為根）進棧（正值），沿左指針查找左兒子 2、左兒子非空，返回1。 3、退棧。若為正值轉 4 ，否則轉 5。 4、負值進棧轉向右子樹，如右兒子非空，則轉向 1；空轉向 3。 5、訪問結點（應恢復正值），返回 3 6、反復 1 到 5 ，至?？諡橹埂?e.g:BCDELAXWinitstack(s); p = t; / t 是根結點的地址，如

11、圖為下標1do while ( p != 0 ) / 有值且非空時 push(s, p)；p = nodep.lchild; if (!stackempty(s) pop(s, p); if ( p 0 ) push(s, -p); p = nodep.rchild; ; else p= - p; visit( nodep.data ); p = 0; while ( !stackempty(s) )后序：B、E、L、X、 W、D、C、A0123Lchild dada rchildnode數(shù)組AL3245C06/ 結點p輸出之后，必須找到其父結點(在棧頂)，故 p=0 跳過while循環(huán)。ED

12、00W0845678BX00000703、遍歷二叉樹和線索二叉樹1、線索二叉樹：為什么采用線索二叉樹：二叉樹中的空指針場多達 n + 1 個。簡單證明：設二叉樹中結點的總數(shù)為 n，度為 2 的結點總數(shù)為 n2 ?？罩羔槇鲇梅娇虼?。增加了方 框結點的二叉樹稱之為擴展二叉樹。在該二叉樹之中，原來的 n 個結點全部成為度為 2 的結 點，方框結點成為葉子。根據(jù)二叉樹的性質 3 ，原命題得證。e.g: n = 8 的二叉樹BCDELAXWBCDELAXW擴展二叉樹怎樣利用這 n + 1 個空指針場？中序穿線樹后序穿線樹3、遍歷二叉樹和線索二叉樹1、線索二叉樹：中序穿線樹（中序線索二叉樹）的實現(xiàn)：在二

13、叉樹的結點的標準形式中，增加兩個標志域，用于區(qū)別是否是穿線。如下所 示：其中 data 為數(shù)據(jù)場，ltag = 0 時，lchild 場指向本結點的真正的左兒子 ltag = 1 時，lchild 場指向本結點的按中序遍歷序列的前驅結點(穿線) rtag = 0 時，rchild 場指向本結點的真正的右兒子 rtag = 1 時，rchild 場指向本結點的按中序遍歷序列的后繼結點(穿線) e.g: n = 6 的二叉樹BCDELA中序穿線樹Lchild ltag data rtag rchild BCDELA無前驅結點無后繼結點3、遍歷二叉樹和線索二叉樹1、線索二叉樹：中序穿線樹中的結點的數(shù)

14、據(jù)結構：BCDELA無前驅結點無后繼結點00000011111111ALBECD新增頭結點表示1:穿線0:實際兒子3、遍歷二叉樹和線索二叉樹1、線索二叉樹：在中序穿線樹上進行中序遍歷、不用堆棧的的算法及程序要點：1、最先輸出最左的結點2、結點無右后件，則該結點的中序的后繼結點，由右兒子的指針場給出。但要注意以下情況：BCDELA無前驅結點無后繼結點3、結點有右兒子，則該結點的中序的后繼結點，是它的右子樹中的最左的結點。4、最先輸出的結點無前驅結點，最后輸出的結點無后繼結點。BDELA指向當前結點指向后繼結點3、遍歷二叉樹和線索二叉樹1、線索二叉樹：在中序穿線樹上進行中序遍歷、不用堆棧的程序實現(xiàn)

15、Status inorderTraverse_Thr(BiThrTree T, status( * Visit ) (TElemType e ) ) p = T- lchild; while ( P != T ) while ( p-Ltag = Link ) p = p-lchid; / Link 表示有實在的兒子 Visit ( p- data); while ( p-rtag = Thread & p-rchid != T ) p = p-rchid ; Visit ( p- data) ; p = p-rchid ; return OK;指向當前結點指向后繼結點BDELA/ 注意：p

16、是根結點的地址，T 為頭結點地址BCDELA無前驅結點無后繼結點01新增頭結點T4、樹和森林1、樹的存儲結構標準形式：樹中的每個結點除有數(shù)據(jù)場之外，還有 K 個指針場；其中 K 為樹的度數(shù)。1、數(shù)據(jù)場第一個兒子結點的地址第二個兒子結點的地址第 K 個兒子結點的地址父親結點的地址廣義標準形式：在標準形式的基礎上，再增加指向父親結點的指針場。 E.g: 度數(shù) K 3 的樹ABCDEFGHILA 1 2 3 -1B 9 4 -1 0C 5 -1 -1 0D 6 7 -1 0E -1 -1 -1 1F -1 -1 -1 2G 8 -1 -1 3H -1 -1 -1 3I -1 -1 -1 6P -1

17、-1 -1 -1 0123456789-1 表示空缺點：空指針場太多，多達 ( K -1 ) n + 1 個。改進：結點中設立度數(shù)場， 指針場依度數(shù)定。但 操作麻煩。 采用左兒子、兄弟表 示法。用數(shù)組表示左圖的樹 4、樹和森林1、樹的存儲結構左兒子、兄弟表示法：樹中的每個結點有數(shù)據(jù)場、指向它的第一棵子樹樹根的指針場、指向它的兄弟結點的指針場。實質上是用二叉樹表示一棵樹。數(shù)據(jù)場第一棵子樹根結點的地址下一個親兄弟結點的地址 E.g: 度數(shù) K 3 的樹ABCDEFGHIL A B C D E F G H L I 4、樹和森林2、樹、森林于二叉樹的轉換樹轉換成相對應的二叉樹：1、保留每個結點的最左面

18、的分支，其余分支都被刪除。2、同一父結點下面的結點成為它的左方結點的兄弟。 E.g: 度數(shù) K 3 的樹ABCDEFGHILABCDEFGHILABCDEFGHIL4、樹和森林2、樹、森林于二叉樹的轉換森林轉換成相對應的二叉樹：增加一個虛擬的根結點，它的兒子為各棵樹的根。那么，就變成了樹轉換成二叉樹的問題。 E.g: 3 棵分別以B、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHILA 相應的二叉樹4、樹和森林2、樹、森林于二叉樹的轉換森林轉換成相對應的二叉樹：增加一個虛擬的根結點，它的兒子為各棵樹的根。那么，就變成了樹轉換成二叉樹的問題。 E.g: 3 棵分別以B、 C

19、、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHIL 相應的二叉樹4、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷：1、類似于二叉樹的前序遍歷：NLR；N:根；L：左子樹（第一棵子樹）， R：其余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹2、類似于二叉樹的后序遍歷：LRN：L：左子樹（第一棵子樹），R：其 余的那些子樹，遍歷方向由第二棵子樹至最后一棵子樹， N:根NBCDEFGHILA T1 T2 T3LR前序：A、B、L、E、C、F、D、G、I、H后序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序遍歷：前序遍歷類似于樹的前序遍歷。增

20、加一個虛擬的根結點，它的兒子為各棵樹的根。那么對這棵樹進行前序遍歷，即得到森林的前序序列（不含樹根結點）中序遍歷類似于樹的后序遍歷。增加一個虛擬的根結點，它的兒子為各棵樹的根。那么對這棵樹進行后序遍歷，即得到森林的中序遍歷（去掉樹根結點） 注意：在森林中通常稱為中序遍歷, 如稱之為后序遍歷更合理(和樹一致)。前序：B、L、E、C、F、D、G、I、H中序：L、E、B、F、C、I、G、H、DBCDEFGHILABCDEFGHIL4、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷序列和相應的二叉樹的前序、中序遍歷序列一一對應：前序序列和對應的二叉樹的前序序列完全一致。E、G：左圖的樹的根 A，及它的兒

21、子結點 B、C、D 在樹的 的前序序列和相應的二叉樹中前序序列中的序號。 根 A: 11 結點 B： 22 結點 C： 55 結點 D： 77BCDEFGHILAABCDEFGHIL以 C 為例：在樹中： 序號 根節(jié)點數(shù) 第一棵子樹的結點數(shù) 1 5在二叉樹中： 序號 根節(jié)點數(shù) 左兒子數(shù)左兒子子樹結點數(shù) 1 54、樹和森林3、樹、森林的遍歷樹的前序、后序遍歷序列和相應的二叉樹的前序、中序遍歷序列一一對應：后序序列和對應的二叉樹的中序序列完全一致。E、G：左圖的樹的根 A，及它的兒子結點 B、C、D 在樹的 的后序序列和相應的二叉樹的中序序列中的序號。 根 A: 1010 結點 B： 33 結點

22、C： 55 結點 D： 99BCDEFGHILAABCDEFGHIL后序：L、E、B、F、C、I、G、H、D、A以 C 為例：在樹中： 序號 第一棵子樹的結點數(shù) C 的子樹的結點數(shù) 1 5在二叉樹中： 序號 B 的左子樹的結點數(shù) B 的結點數(shù) C 的左子樹結點數(shù) 1 5中序：L、E、B、F、C、I、G、H、D、A4、樹和森林3、樹、森林的遍歷森林的前序、中序（當作后序更好理解）和相應的二叉樹的前序、中序遍歷序列一一對應 E.g: 3 棵分別以B、 C、D為根的樹BCDEFGHILBCDEFGHILABCDEFGHILA 相應的二叉樹6、赫夫曼樹及其應用1、最優(yōu)二叉樹（赫夫曼樹） 路徑長度：結點

23、之間的樹枝的總數(shù)樹的路徑長度：從根到每一結點的路徑長度之和樹的帶權路徑長度：葉子結點的帶權路徑長度之和。設有 n 片葉子，它們的權值分別 為 w1、w2、.wn， 相應的路徑長度分別為 L1、L2、.Ln。 則樹的帶權路徑長度可記為： nWPL = wklk k=1EGHLLEHGEGHL777524442255WPL=36WPL=46WPL=35最優(yōu)二叉樹或赫夫曼樹：樹的帶權路徑長度 WPL 最小的二叉樹。6、赫夫曼樹及其應用1、最優(yōu)二叉樹（赫夫曼樹） 赫夫曼算法（產(chǎn)生最優(yōu)二叉樹的算法）的實現(xiàn)：1、給定一個具有 n 個權值 w1,w2,wn 的結點的集合 F = T1,T2,Tn 。2、初始

24、時，設 A F。3、執(zhí)行 i = 1 至 n-1 次循環(huán)，在每次循環(huán)時，做以下事情：從當前集合中選取權值最小、次最小的兩個結點，以 這兩個結點作為內(nèi)部結 點 bi 的左右兒子，bi 的權值為其左右兒子權值之和。在集合中刪除這兩個權 值最小、次最小的結點。這樣，在集合 A 中，結點個數(shù)便減少了一個。 e.g: 權值（此處為使用概率）分別為 2, 7, 4, 5 的結點集合 F C, A, S, T 已知。 請利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。C, 2A, 7S, 4T, 51、A=b1,6A, 7T, 5S, 4C, 22、A=b1,6A, 7S, 4C, 2b2,11 T, 53、A=b3,184

25、、A=6、赫夫曼樹及其應用2、赫夫曼編碼 赫夫曼算法用于通信中的字符的編碼。將權值當著使用概率。赫夫曼樹的左分支 標記為 1，而右分枝標記為 0；這從根到每一個葉子結點（字符）的路經(jīng)上標記的字符組成的字 符串，即為該字符的赫夫曼編碼。 e.g: 權值（此處為使用概率）分別為 2, 7, 4, 5 的結點集合 F C, A, S, T 已知。 請利用赫夫曼算法產(chǎn)生最優(yōu)二叉樹。b1,6A, 7S, 4C, 2b2,11T, 5b3,18111000赫夫曼編碼：A：0T：10C：110S ：111赫夫曼編碼優(yōu)點： 占用二進制位少e.g: 左圖發(fā)送長度為 n 的字符串，等長表示需 2n 個比特。因共有

26、四個字符，表示每個字符需 二個 比特。 采用赫夫曼編碼后，總的比特數(shù) 35n/18, 因： A：1*7n /18 T： 2*5n /18 S： 3*4n /18 C：3*2n /18 7、回溯法與樹的遍歷1、回溯法簡介：求最優(yōu)解、全部解答、一組解答的常用辦法，也 可用窮舉法求解。窮舉法：羅列所有可能性，得出解答?？赡芤?指數(shù)爆炸問題。 回溯法：搜索、試探、回溯；類似于樹的前序周 游。用約束函數(shù)削減結點。2、回溯法的形式描述：解表示成 n 元組（x1,x2,xn）的形式， xi 取自 初值集合 si 先構造部分向量 （x1,x2,xi）, 一旦發(fā)現(xiàn)該向量 不合要求，則不必考慮（xi+1 , ,

27、xi+2, xn）； 削減結點，提高效率。用約束函數(shù)判斷是否合乎要求，滿足約束函數(shù)可 繼續(xù)構造下去（即：xi+1 , ,xi+2, xn）；反之 ，則不必再構造（被剪枝）。約束函數(shù)：顯約束：xi 的取值范圍 隱約束：各 xi 之間的關系。 e.g：四后問題：在 4 行 4 列的國際象棋棋 盤上尋找所有互不相互攻擊的四個皇 后的位置。 解：設解向量為 x1 ,x2 , x3 ,x4 ；且下標 i 代表該皇后所在的行數(shù)，xi 代表所在 的列數(shù)。 顯約束：xi ：1、2、3、4 隱約束： xi != xk /列數(shù)不等 i != k /行數(shù)不等 xi - i != xk - k /不可同在主 / 對角

28、線上 xi + i != xk + k /不可同在次 / 對角線上7、回溯法與樹的遍歷皇后皇后皇后皇后皇后皇后皇后皇后 i = k /行數(shù)等xi = xk /列數(shù)等 xi - i = xk - k / 同在主/ 對角線上xi + i = xk + k /同在次 / 對角線上3、皇后相互攻擊的情況分析：7、回溯法與樹的遍歷4、皇后相互攻擊的情況分析：Void nqueen( int n); / 求解 n 后問題的所有解 x( 1) = 0 ; k = 1 ; / 第 k 個皇后被放置在第 k 行， x( k ) 列 while ( k 0 ) x( k ) = x( k ) + 1; / 考察下

29、一列 while ( (x( k ) = n ) & （ (k 行、 x(k)列的皇后同 ( 1 行、 x(1)列)， ( 2行、 x(2)列)，( k-1行、 x(k-1)列的皇后沖突時 ) / 用約束函數(shù) x( k ) = x( k ) + 1 ； / 移到下一列 if (x( k ) = n ) / 發(fā)現(xiàn)一個新的可放位置 (k 行、 x(k) 列if ( k =n ) PRINT ( 1、 x(1)，( 2、x(2) 至 ( n、x(n ); / 一個解，得到n個后的位置else k = k + 1; x( k ) = 0 ； / 在下一行尋找合適行、列放置皇后 else k = k-1

30、; / 回溯，回退一行 7、回溯法與樹的遍歷4、四皇后問題解答樹的遍歷過程： e.g: 在 （1行 、1列）的皇后的遍歷過程(1、1)(2、1)(2、2)(2、3)(2、4)(3、1)(3、2)(3、3)(3、4)(4、1)(4、2)(4、3)(4、4)(3、1)(3、2)(3、3)(3、4)皇后皇后皇后8、樹的計數(shù)1、二叉樹的確定 前序（后序） 中序 唯一確定一棵二叉樹 e.g: 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C確定過程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部為 A 的左子樹 上的所有結點， A 的右部為 A 的右子 樹中的所有

31、結點。 4、根據(jù) A 的左子樹的所有結點的前序序 列確定 A 的左子樹的根節(jié)點，它是 A 的左兒子。 5、根據(jù) A 的右子樹的所有結點的前序序 列確定 A 的右子樹的根節(jié)點，它是 A 的右兒子。 6、 在左、右子樹中反復以上過程。至所有 結點處理完畢。結束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: B、D、E、F 中序: D、B、E、F 前序: E、F 中序: E、FA D、B、E、F CA D、E、FCBABCD E、F8、樹的計數(shù)1、二叉樹的確定 前序（后序） 中序 唯一確定一棵二叉樹 e.g:

32、前序: A、B、D、E、F、C 中序: D、B、E、F、A、C確定過程: 1、 定根 A 2、在中序序列中找到 A 3、中序序列中的 A 的左部為 A 的左子樹 上的所有結點， A 的右部為 A 的右子 樹中的所有結點。 4、根據(jù) A 的左子樹的所有結點的前序序 列確定 A 的左子樹的根節(jié)點，它是 A 的左兒子。 5、根據(jù) A 的右子樹的所有結點的前序序 列確定 A 的右子樹的根節(jié)點，它是 A 的右兒子。 6、 在左、右子樹中反復以上過程。至所有 結點處理完畢。結束 前序: A、B、D、E、F、C 中序: D、B、E、F、A、C 前序: A、B、D、E、F、C 中序: D、B、E、F、A、CE

33、F 前序: B、D、E、F 中序: D、B、E、F 前序: E、F 中序: E、FA D、B、E、F CA D、E、FCBABCD8、樹的計數(shù)1、互不相似的二叉樹的棵數(shù)的計算 計算要點: 設二叉樹的前序的序列 為 1、2、3 n 不同的中序序列的對應 著不同樹形的二叉樹 不同的中序序列的總數(shù) 是不同樹形的二叉樹的 總和不同的中序序列在中序 周游時和相應的進出棧 序列一一對應。 不同的進出棧序列的總 數(shù)是不同樹形的二叉樹 的總和 實例：e.g: 當 二叉樹的結點個數(shù) n = 3 前序序列為 1、2、3 時1231231231231231、進棧2、進棧3、進棧3、出棧2、出棧1、出棧1、進棧2、進

34、棧2、出棧3、進棧3、出棧1、出棧1、進棧2、進棧2、出棧1、出棧3、進棧3、出棧1、進棧1、出棧2、進棧3、進棧2、出棧3、出棧1、進棧1、出棧2、進棧2、出棧3、進棧3、出棧8、樹的計數(shù)1、互不相似的二叉樹的棵數(shù)的計算 實例：e.g: 當 二叉樹的結點個數(shù) n = 3 前序序列為 1、2、3 時1231231231231231、進棧2、進棧3、進棧3、出棧2、出棧1、出棧1、進棧2、進棧2、出棧3、進棧3、出棧1、出棧1、進棧2、進棧2、出棧1、出棧3、進棧3、出棧1、進棧1、出棧2、進棧3、進棧2、出棧3、出棧1、進棧1、出棧2、進棧2、出棧3、進棧3、出棧 進出棧序列總數(shù)的計算為2n

35、個方格中放置 3 個 1 的組合數(shù) 不合理的序列總數(shù)e.g: n = 3 時，6格放置3個 1 的序列情況：1 代表進棧，0 表示出棧 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0合理不合理8、樹的計數(shù)1、互不相似的二叉樹的棵數(shù)的計算 進出棧序列總數(shù)的計算為2n 個方格中放置 n 個 1 的組合數(shù) 不合理的序列總數(shù)e.g: n = 3 時，6格放置3個 1 的序列情況：1 代表進棧，0 表示出棧 1 1 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0

36、 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0合理不合理n = 3 時，6 格放置 3 個 1 的序列情況： 3 序列總數(shù) 2 3 3 1不合理的序列總數(shù)： 2 3因此，n = 3 時進出棧序列的總數(shù)為： 3 3 + 1 2 32 3推廣到結點數(shù)為 n 時的進出棧序列總數(shù)： nn + 1 2 nn + 18、樹的計數(shù)2、推論：結點數(shù)為 n + 1 時的互不相似的有序樹總數(shù)和結點數(shù)為 n 時的互不相似的二叉樹的總數(shù)相等。12312312312312302311230123013201320E.g: n = 4 的所有樹 形只需考慮以下二叉樹的棵數(shù)即可023112301230132013208、樹的計數(shù) 結點數(shù)為 n 時的互不相似的