《樹與二叉樹 》PPT課件.ppt

,第八章 樹與二叉樹,1.樹的定義及其基本概念,2.二叉樹的基本概念和存儲結(jié)構(gòu),3.二叉樹的遍歷,4.線索二叉樹的概念及其遍歷,6.哈夫曼樹及其構(gòu)造方法,7.樹與森林,5.二叉排序樹,8.1 樹的概念和基本術(shù)語,一、樹的定義 樹是由 n (n 0) 個結(jié)點的有限集合。如果 n = 0，稱為空樹；如果 n 0，則 有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)； 當n 1，除根以外的其它結(jié)點劃分為 m (m 0) 個互不相交的有限集 T1, T2 , Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。,根,子樹,特點：樹中至少有一個結(jié)點根 樹中各子樹是互不相交的集合,二、樹的表示,1樹形結(jié)構(gòu)表示法,2. 凹入法表示法,3. 嵌套集合表示法（文氏圖表示法）,4.廣義表表示法（括號表現(xiàn)法） 對樹結(jié)構(gòu)，廣義表表示法可表示為： (A(B(E(J，K，L)，F(xiàn))，C(G)，D(H(M)，I),分支(branch)：結(jié)點之間的二元關(guān)系（序偶）。 結(jié)點(node)：一個數(shù)據(jù)元素及指向其子樹的分支。 結(jié)點的度(degree)：結(jié)點擁有的子樹個數(shù)。 葉結(jié)點(leaf)：度為零的結(jié)點。 分支結(jié)點(branch node):有后繼的結(jié)點稱為分支結(jié)點。 兒子(sons)：結(jié)點x的子樹的根。 父親(parent):結(jié)點x的前驅(qū)結(jié)點稱為x的父親。 兄弟(brother)：同一父親的結(jié)點的子女結(jié)點。 祖先(ancestor)：根到該結(jié)點路徑上的所有結(jié)點。 子孫(descendant)：某結(jié)點為根的子樹上的任意結(jié)點。 堂兄弟(cousin):父親是兄弟關(guān)系或堂兄弟關(guān)系的結(jié)點。,結(jié)點層次(level)：從根開始，根為第一層，根的子女為第二層，以此類推。 樹的深度（高度）(depth)：樹中結(jié)點的最大層次數(shù) 樹的度：一棵樹中最大的結(jié)點度數(shù)。 結(jié)點按層編號（層中編號）：將樹中結(jié)點按從上層到下層，同層從左到右的次序排成一個線性序列，依次給他們編以連續(xù)的自然數(shù)。 祖輩（上層）：層號比結(jié)點x小的結(jié)點，稱為x的祖輩。 后輩（下層）：層號比結(jié)點x大的結(jié)點，稱為x的后輩。 有序樹：若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。 無序樹：若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。 森林(forest)：m(m 0)棵互不相交的樹。,三、樹的基本術(shù)語,1層,2層,4層,3層,height = 4,A,C,G,B,D,E,F,K,L,H,M,I,J,結(jié)點 結(jié)點的度 葉結(jié)點 分支結(jié)點,子女 雙親 兄弟,祖先 子孫 結(jié)點層次,樹的深度 樹的度 有序樹 無序樹 森林,結(jié)點A的度：3 結(jié)點B的度：2 結(jié)點M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結(jié)點A的孩子：B，C，D 結(jié)點B的孩子：E，F(xiàn),結(jié)點I的父親：D 結(jié)點L的父親：E,結(jié)點B，C，D為兄弟 結(jié)點K，L為兄弟,樹的度：3,結(jié)點A的層次：1 結(jié)點M的層次：4,樹的深度：4,結(jié)點F，G為堂兄弟 結(jié)點A是結(jié)點F，G的祖先,8.2 二叉樹 (Binary Tree),定義:,五種形態(tài):,一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。,特點:,每個結(jié)點至多只有兩棵子樹（二叉樹中 不存在度大于2的結(jié)點）,二叉樹的基本操作,（1）creat_tree(bt,str) 根據(jù)二叉樹的括號表示法str建立一棵二叉樹bt。 （2）disptree(bt) 以凹入法顯示一棵二叉樹bt。 （3）depth_bttree(bt) 求一棵二叉樹bt的深度。 （4）count_bttree(bt) 求一棵二叉樹bt的結(jié)點個數(shù)。 （5）leafcount_bttree(bt) 求一棵二叉樹bt的葉子結(jié)點個數(shù)。 （6）nleafcount_bttree(bt) 求一棵二叉樹bt 的非葉子結(jié)點個數(shù)。,性質(zhì)1 在二叉樹的第 i 層上至多有 2i 1個結(jié)點。(i 1) 證明用歸納法 證明：當i=1時，只有根結(jié)點，2 i-1=2 0=1。 假設(shè)對所有j，ij1，命題成立，即第j層上至多有2 j-1 個結(jié)點。 由歸納假設(shè)第i-1 層上至多有 2i 2個結(jié)點。 由于二叉樹的每個結(jié)點的度至多為2，故在第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2* 2i 2= 2 i-1。,二叉樹的性質(zhì),性質(zhì)2 深度為 k 的二叉樹至多有 2k -1個結(jié)點(k 1)。 證明：由性質(zhì)1可見，深度為k的二叉樹的最大結(jié)點數(shù)為,性質(zhì)3 對任何一棵二叉樹T, 如果其葉結(jié)點數(shù)為 n0, 度為2的結(jié)點數(shù)為 n2,則n0n21. 證明：若度為1的結(jié)點有 n1 個，總結(jié)點個數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定義1 滿二叉樹 (Full Binary Tree) 一棵深度為k且有2k -1個結(jié)點的二叉樹稱為滿二叉樹。,兩種特殊形態(tài)的二叉樹,非完全二叉樹,定義2 完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為h，則共有h層。除第 h 層外，其它各層 (0 h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。,完全二叉樹,性質(zhì)4 具有 n (n 0) 個結(jié)點的完全二叉樹的深度為log2(n) 1 證明： 設(shè)完全二叉樹的深度為 h，則根據(jù)性質(zhì)2和完全二叉樹的定義有 2h1 - 1 n 2h - 1或 2h1 n 2h 取對數(shù) h1 log2n h，又h是整數(shù)， 因此有 h = log2(n) 1,性質(zhì)5 如將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號 1, 2, , n，則有以下關(guān)系： 若i = 1, 則 i 無雙親 若i 1, 則 i 的雙親為(i /2) 若2*i n, 則 i 無左孩子,否則其左孩子是結(jié)點2i. 若2*i+1n,則結(jié)點i無右孩子,否則其右孩子為結(jié)點2*i+1,完全二叉樹 一般二叉樹 的順序表示 的順序表示,8.3 二叉樹的存儲結(jié)構(gòu),一、順序表示,二、鏈表表示,二叉樹鏈表表示的示例,二叉樹 二叉鏈表 三叉鏈表,typedef struct btnode struct btnode *lchild; int data; struct btnode *rchild; bitnode,*bitree;,二叉鏈表的定義,若一個二叉樹含有n個結(jié)點，則它的二叉鏈表中必含有2n個指針域，其中必有n+1個空鏈域。 證明：邊數(shù)e=n-1;即非空鏈域為n-1個，則空鏈域為2n-(n-1)=n+1個。,三、二叉鏈表的遞歸創(chuàng)建及其基本操作的實現(xiàn),char s= ,a,b,c,d, , ,e,f,g, , , , ,h,I; root =creat_tree(s,1); bitree creat_tree(char *s,int p) bitree new; if(sp= |p15) return NULL; else new=(bitree)malloc(sizeof(bitree); new-data=sp; new-lchild=creat_tree(s,2*p); new-rchile=creat_tree(s,2*p+1); return new; ,8.4 二叉樹遍歷,樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。 設(shè)訪問根結(jié)點記作 V 遍歷根的左子樹記作 L 遍歷根的右子樹記作 R 則可能的遍歷次序有 前序 VLR 中序 LVR 后序 LRV,中序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作； 否則 中序遍歷左子樹 (L)； 訪問根結(jié)點 (V)； 中序遍歷右子樹 (R)。 遍歷結(jié)果 a + b * c - d - e / f,中序遍歷 (Inorder Traversal),void inorder (bitree bt) if (bt!= NULL ) inorder ( bt-lchild ); printf(“ %c”,bt-data); inorder ( bt-rchild ); ,中序遍歷二叉樹的遞歸算法,前序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作； 否則 訪問根結(jié)點 (V)； 前序遍歷左子樹 (L)； 前序遍歷右子樹 (R)。 遍歷結(jié)果 - + a * b - c d / e f,前序遍歷 (Preorder Traversal),前序遍歷二叉樹的遞歸算法 void preorder (bitree bt) if (bt!= NULL ) printf(“ %c”,bt-data); preorder ( bt-lchild ); preorder (bt-rchild ); ,后序遍歷二叉樹算法的定義： 若二叉樹為空，則空操作； 否則 后序遍歷左子樹 (L)； 后序遍歷右子樹 (R)； 訪問根結(jié)點 (V)。 遍歷結(jié)果 a b c d - * + e f / -,后序遍歷 (Postorder Traversal),后序遍歷二叉樹的遞歸算法： void postorder (bitree bt) if ( bt != NULL ) postorder ( bt-lchild ); postorder ( bt-rchild ); printf(“ %c”,bt-data); ,非遞歸實現(xiàn)先序遍歷二叉樹 利用一個一維數(shù)組作為棧，來存儲二叉鏈表中結(jié)點，算法思想為： 1、從二叉樹根結(jié)點開始，先將根結(jié)點入棧。 2、然后將棧頂結(jié)點出棧，輸出結(jié)點的值，同時判斷該結(jié)點有沒有右子樹，有則將右子樹的根結(jié)點入棧；再判斷有沒有左子樹，有則將左子樹的根結(jié)點入棧。如果棧不空則重復第2步，直到棧為空。,void preorder (bitree root) bitree p, stack100; int top=-1; /top為棧頂指針 if(root!=NULL) top+; stacktop=root;/將根結(jié)點壓入棧內(nèi) while(top!=-1) p=stacktop; top-; printf(“%d ”,p-data); if(p-rchild!=NULL) stack+top=p-rchlid; /壓右子樹 if(p-lchild!=NULL) stack+top=p-lchild; /壓左子樹 ,非遞歸實現(xiàn)中序遍歷二叉樹 同樣利用一個一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點，算法思想為： 1、將所指的結(jié)點的左子樹入棧，其下面的左子樹也入棧 2、彈出一個結(jié)點并輸出，判斷其是否有右子樹，有則入棧，再轉(zhuǎn)到第1步，沒有右子樹則判斷棧是否為空，不空則彈出一個結(jié)點，轉(zhuǎn)回第2步，為空則結(jié)束。,void inorder ( bitree root) bitree p=root,stack100; /s為一個棧，top為棧頂指針 int top=-1; do while(p!=NULL) top+; stacktop=p; p=p-lchild; if(top=0) p=stacktop; top-; printf(“%d ”,p-data); p=p-rchild; while(p!=NULL|top=0); ,非遞歸實現(xiàn)后序遍歷二叉樹 在后序遍歷中，當搜索指針指向某一個結(jié)點時，不能馬上進行訪問，而先要遍歷左子樹，所以此結(jié)點應先進棧保存，當遍歷完它的左子樹后，再次回到該結(jié)點，還不能訪問它，還需先遍歷其右子樹,所以該結(jié)點還必須再次進棧，只有等它的右子樹遍歷完后，再次退棧時，才能訪問該結(jié)點。 為了區(qū)分同一結(jié)點的三次進棧及出棧，引入一個棧次數(shù)的標志，一個元素第一次進棧標志為1，第二次進標志為2，第三次進棧標志為3，并將標志同時存入棧中，當出棧的元素的標志為3時，才輸出此結(jié)點。,struct forpost int sign; bitnode *treenode; void postorder(bitnode *root) forpost stack100,p,q; int top=0,i; p.treenode=root; p.sign=1; stacktop=p; top+;/將根結(jié)點入棧,while(top!=0) top-; p=stacktop; if(p.treenode!=NULL) if(p.sign=1) q.treenode=p.treenode; q.sign=2; stacktop+=q; q.treenode=p.treenode-lchild; q.sign=1; stacktop+=q; if(p.sign=2) q.treenode=p.treenode; q.sign=3; stacktop+=q; q.treenode=p.treenode-rchild; q.sign=1; stacktop+=q; if(p.sign=3) printf(“%dt”,p.treenode-data); ,線索二叉樹的引入： 對二叉樹遍歷的過程實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化的操作。以二叉鏈表為存儲結(jié)構(gòu)時,結(jié)點的左右孩子可以直接找到,但不能直接找到結(jié)點的前驅(qū)和后繼,而結(jié)點的前驅(qū)和后繼只有在遍歷二叉樹的過程中才能得到。 用二叉鏈表表示的二叉樹中,n個結(jié)點的二叉樹有n+1個空鏈域，可利用這些空鏈域存儲結(jié)點的前驅(qū)或后繼。,8.5 線索二叉樹 (Threaded Binary Tree),ltag=0, lchild為左孩子指針 ltag=1, lchild為前驅(qū)線索 rtag=0, rchild為右孩子指針 rtag=1, rchild為后繼線索,typedef struct bithrnode elemtype data; /*數(shù)據(jù)域*/ struct bithrnode *lchild，*rchild; /*左右指針*/ ptrtag ltag,rtag;/*左右標志*/ bithrnode,*bithrtree;,線索二叉樹 中結(jié)點的定義,線索二叉樹的創(chuàng)建和遍歷,中序構(gòu)造線索二叉樹算法思想: 對二叉樹一邊中序遍歷一邊建線索,若訪問結(jié)點的左孩子為空,建立前趨線索;若右孩子為空,建立后繼線索。 并且在二叉樹的線索鏈表上也添加一個頭結(jié)點，并令其lchild域的指針指向二叉樹的根結(jié)點，其rchild域的指針指向中序序列的最后一個結(jié)點；反之，令二叉樹的中序序列的第一個結(jié)點的lchild域指針和最后一個結(jié)點rchild域的指針均指向頭結(jié)點。,先序序列為：ABCD,中序序列為：BADC,后序序列為：BDCA,void inthread(bithrtree p,bithrtree pre) if(p) inthread(p-lchild,pre)/左子樹線索化 if(p-lchild=NULL) p-ltag=1; p-lchild=pre;/產(chǎn)生前驅(qū) if(p-rchild=NULL) pre-rtag=1; pre-rchild=p;/產(chǎn)生后繼 pre=p;/保持pre指向p的前驅(qū) inthread(p-rchild,pre);/右子樹線索化 ,遍歷中序線索二叉樹算法思想： 先判斷指針域是用作線索還是指向子樹，再決定是否進行遞歸調(diào)用。 bithrtree inorder_thread(bithrtree t) bithrtree thrt,pre,p; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0;thrt-rtag=1; thrt-rchild=thrt; if(t=NULL) thrt-lchild=thrt; else p=thrt-lchild=t; thrt-ltag=0; pre=thrt; inthread(p,pre); pre-rtag=1; thrt-rchild=pre; thrt-rtag=1; return thrt;,8.6 二叉排序樹,二叉排序樹（二叉查找樹）是一種特殊的二叉樹，一般二叉樹中只區(qū)分左、右子樹，但不區(qū)分結(jié)點的順序，在二叉排序樹中，所有結(jié)點都是有序的。 特征： （1）若它左子樹非空，則左子樹上的所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字。 （2）若它右子樹非空，則右子樹上所有結(jié)點的關(guān)鍵字均大于根結(jié)點的關(guān)鍵字。 （3）左、右子樹本身各又是一個二叉排序樹。,利用二叉排序樹進行查找，算法比較簡單 如想查找數(shù)據(jù)6，先和根5比較，轉(zhuǎn)到右子樹上查找，再比較7，轉(zhuǎn)左子樹上，就找到了6。即為查找算法中的二分查找法。,二叉查找樹的查找 bitree binary_traverse_search(bitree p,int v) while(p!=NULL) if(p-data=value) return p; else if(p-datav) p=p-lchild; else p=p-rchild; return NULL; ,main() bitree root=NULL,p; int v,s16=0,5,4,7,2,0,6,8,1,3,0,0,0,0,0,0; root=creat_tree(s,1); printf(“請輸入要查找的結(jié)點的值：n”); scanf(“%d”, ,8.7 哈夫曼樹 (Huffman Tree),一、哈夫曼 (Huffman)樹,又稱最優(yōu)樹,是一類帶權(quán)路徑長度最短的樹 1路徑和路徑長度 在一棵樹中，從一個結(jié)點往下可以達到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。 若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。 2結(jié)點的權(quán)及帶權(quán)路徑長度 若將樹中結(jié)點賦予一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。 結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。,3樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和， 記為wpl= ，其中n 為葉子結(jié)點數(shù)目，wi為第i 個葉子結(jié)點的權(quán)值，li 為第i 個葉子結(jié)點的路徑長度。,WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35,帶權(quán)路徑長度達到最小,哈夫曼樹,樹的帶權(quán)路徑長度達到最小的二叉樹即為哈夫曼樹。 在哈夫曼樹中，權(quán)值大的結(jié)點離根最近。,(1) 由給定的 n 個權(quán)值 w0, w1, w2, , wn-1，構(gòu)造具有 n 棵擴充二叉樹的森林 F = T0, T1, T2, , Tn-1 ，其中每棵擴充二叉樹 Ti 只有一 個帶權(quán)值 wi 的根結(jié)點, 其左、右子樹均為空。,二、哈夫曼樹的構(gòu)造算法,(2) 重復以下步驟, 直到 F 中僅剩下一棵樹為止： 在 F 中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。 在 F 中刪去這兩棵二叉樹。 把新的二叉樹加入 F。,哈夫曼樹的構(gòu)造過程,例 w=5, 29, 7, 8, 14, 23, 3, 11,三、哈夫曼樹的應用-哈夫曼編碼,在傳送電文時,總是希望傳送的時間盡可能短，如果每個字符設(shè)計長度不等的編碼，且能讓出現(xiàn)頻率高的采用盡可能短的編碼，則傳送的電文長度就會縮短。 例如：需要傳送的電文為“ABACCDA”,如果設(shè)計A、B、C、D的編碼分別為0 、00、1和01，則上述7個字符的電文就轉(zhuǎn)換成為長度為9個字符串“000011010”。,前綴編碼：設(shè)計長短不等的編碼，必須使任何一個字符都不是另一個字符的前綴，這樣保證譯碼的唯一性。,哈夫曼編碼,主要用途是實現(xiàn)數(shù)據(jù)壓縮。,設(shè)給出一段報文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各字符出現(xiàn)概率為 C:2/18, A:7/18, S:4/18, T:5/18 ,化整為 2, 7, 4, 5 。 若給每個字符以等長編碼 A : 00 T : 10 C : 01 S : 11 則總編碼長度為 ( 2+7+4+5 ) * 2 = 36.,若按各個字符出現(xiàn)的概率不同而給予不等長編碼，盡可能減少總編碼長度。 各字符出現(xiàn)概率為 2, 7, 4, 5 。以它們?yōu)楦魅~結(jié)點上的權(quán)值, 建立哈夫曼樹。左分支賦 0，右分支賦 1，得哈夫曼編碼(變長編碼)。,CAST CAST SAT AT A TASA A : 0 T : 10 C : 110 S : 111 它的總編碼長度：7*1+5*2+( 2+4 )*3 = 35。比等長編碼的情形要短。 總編碼長度正好等于哈夫 曼樹的帶權(quán)路徑長度WPL。 哈夫曼編碼是一種無前綴 編碼(都由葉結(jié)點組成,路徑 不會重復)。解碼時不會混淆。 哈夫曼編碼: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 等長編碼: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100,#define MAX 50 typedef struct char data; int weight; int parent; int left; int right; int flag;huffnode; huffnode ht2*MAX;,int select(int i) int k=32767,j,q; for(j=0;j=i;j+) if(htj.weightk,void creat_hufftree(int n) int i,k,l,r; for(i=0;i2*n-1;i+) hti.parent=hti.left=hti.right=hti.flag=-1; for(i=n;i2*n-1;i+) l=select(i-1); r=select(i-1); htl.parent=i ; htr.parent=i; hti.weight=htl.weight+htr.weight; hti.left=l; hti.right=r; ,哈夫曼編碼算法： 在建好的哈夫曼樹中求哈夫曼編碼，實質(zhì)上就是從葉結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值。 這樣求得的碼是從低位到高位，可以設(shè)置一結(jié)構(gòu)體數(shù)組huffcode來存放各字符的哈夫曼編碼。其結(jié)構(gòu)如下：,其中cd是一維數(shù)組用來存放編碼，start表示該編碼在數(shù)組cd中的開始位置。對于第i個字符，它的編碼存放在huffcodei.cd中的從huffcodei.start到n的分量上。,typedef struct char cdMAX; int start;huffcode; huffcode hcdMAX;,w parent l r flag,0 1 2 3 4 5 6,creat_huffcode(int n) int i,f,c; huffcode d; for(i=0;in;i+) d.start=n+1; c=i; f=hti.parent; while(f!=-1) if(htf.left=c) d.cd-d.start=0; else d.cd-d.start=1; c=f; f=htf.parent; hcdi=d; ,void display_huffcode(int n) int i,k; printf(“輸出哈夫曼編碼：n”); for(i=0;in;i+) printf(“%c:”,hti.data); for(k=hcdi.start;k=n;k+) printf(“%c”,hcdi.cdk); printf(“n”); ,一、樹的存儲結(jié)構(gòu) 1、雙親表示：以一組連續(xù)空間存儲樹的結(jié)點，同時在結(jié)點中附設(shè)一個指針，存放雙親結(jié)點在鏈表中的位置。該方法利用每個結(jié)點只有一個雙親的特點，可以很方便求結(jié)點的雙親，但不方便求結(jié)點的孩子。,8.8 樹與森林,用雙親表示實現(xiàn)的樹定義,typedef struct char data; int parent; ptnode; typedef struct ptnode nodesMAXSIZE; int nodenum; pttree;,A,B,C,D,E,F,G,2、孩子表示法(多重鏈表),第一種解決方案 等數(shù)量的鏈域 (d為樹的度),第二種解決方案 孩子鏈表,將每個結(jié)點的孩子鏈在該結(jié)點之后組成鏈表，再將所有頭結(jié)點組成一個線性表。,孩子表示法的存儲結(jié)構(gòu)類型定義,typedef struct cnode int child; struct cnode *next; childlink; typedef struct char data; childlink *headptr; ctnode; /*表頭向量中結(jié)點結(jié)構(gòu)*/ typedef struct ctnode nodesMAXSIZE; /*表頭向