【正文】 棵子樹(shù)。 1．二叉樹(shù)的遞歸定義 二叉樹(shù) (BinaryTree)是 n(n≥ 0)個(gè)結(jié)點(diǎn)的有限集。 二叉 樹(shù) 二叉樹(shù)與樹(shù)有區(qū)別：樹(shù)至少應(yīng)有一個(gè)結(jié)點(diǎn)，而二叉樹(shù)可以為空；樹(shù)的子樹(shù)沒(méi)有順序，但如果二叉樹(shù)的根結(jié)點(diǎn)只有一棵子樹(shù)，必須明確區(qū)分它是左子樹(shù)還是右子樹(shù)，因?yàn)閮烧邔?gòu)成不同形態(tài)的二叉樹(shù)。它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 (1) 滿二叉樹(shù) (FullBinaryTree) 深度為 k， 且有 2k1個(gè)結(jié)點(diǎn)的 二叉樹(shù) 。 結(jié)點(diǎn)層序編號(hào)方法：從根結(jié)點(diǎn)起從上到下逐層（層內(nèi)從左到右）對(duì)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。 圖 611 完全二叉樹(shù) 完全二叉樹(shù)的特點(diǎn)： （ 1）每個(gè)結(jié)點(diǎn) i的左子樹(shù)的深度 Lhi其結(jié)點(diǎn) i的右子樹(shù)的深度 Rhi等于 0或 1，即葉結(jié)點(diǎn)只可能出現(xiàn)在層次最大或次最大的兩層上。 4 5 2 1 3 1 3 2 4 6 5 3 2 4 1 LH1=3 RH1=1 LH1 RH1=2 非完全二叉樹(shù) 非完全二叉樹(shù) LH2=0 RH2=1 LH2RH2=01=1 2．二叉樹(shù)的性質(zhì) 性質(zhì) 1 在二叉樹(shù)的第 i層上至多有 2i1 個(gè)結(jié)點(diǎn) (i≥1) 。 （ 深度一定，二叉樹(shù)的最大結(jié)點(diǎn)數(shù)也確定） 性質(zhì) 3 二叉樹(shù)中 ,終端結(jié)點(diǎn)數(shù) n0與度為 2的結(jié)點(diǎn)數(shù) n2有如下關(guān)系 : n0=n2+1 性質(zhì) 4 結(jié)點(diǎn)數(shù)為 n的完全二叉樹(shù)，其深度為 ?log2n? + l 性質(zhì) 5 在按層序編號(hào)的 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，任意一結(jié)點(diǎn)i(1≤i≤n) 有： ⑴ i=1時(shí)，結(jié)點(diǎn) i是樹(shù)的根；否則 ， 結(jié)點(diǎn) i的雙親為結(jié)點(diǎn) ? i/2 ? (i1) 。 ⑶ 2i+1＞ n時(shí)，結(jié)點(diǎn) i無(wú)右孩子；否則，結(jié)點(diǎn) i的右孩子為結(jié)點(diǎn)2i+1。 1．順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹(shù)的數(shù)據(jù)元素， 結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 0 這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹(shù)，既不浪費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、結(jié)點(diǎn)的雙親和左右孩子的存放位置，但對(duì)一般二叉樹(shù)，可能造成存儲(chǔ)空間的大量浪費(fèi)。 例如：深度為 k， 且只有 k個(gè)結(jié)點(diǎn)的右單枝樹(shù) ( 每個(gè)非葉結(jié)點(diǎn)只有右孩子 )，需 2k1個(gè)單元，即有 2k1k個(gè)單元被浪費(fèi)。常用的有： 二叉鏈表 三叉鏈表 線索鏈表 用空鏈域存放指向前驅(qū)或后繼的線索 由于二叉樹(shù)每個(gè)結(jié)點(diǎn)至多只有 2個(gè)孩子，分別為左孩子和右孩子。每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)表示為： 其中左鏈域 lchild為指向左孩子的指針，右鏈域 rchild為指向右孩子的指針，數(shù)據(jù)域 data表示結(jié)點(diǎn)的值。 L c h i l d d a t a r c h i l d對(duì)應(yīng)的結(jié)構(gòu)類型定義如下： typedef struct node { ElemType data。 struct node *rchild。 其中， tree是指向根結(jié)點(diǎn)的指針。若二叉樹(shù)為空，則root=NULL； 若結(jié)點(diǎn)的某個(gè)孩子不存在，則相應(yīng)的指針為空。其中只有 n1個(gè)用來(lái)指示結(jié)點(diǎn)的左、右孩子，其余的 n+1個(gè)指針域?yàn)榭铡＞褪侨骀湵怼? 二叉樹(shù)存儲(chǔ)方法的選擇，主要依賴于所要實(shí)施的各種運(yùn)算的頻度。T) 功能：初始化操作 (建立一棵空的二叉樹(shù) )。 （ 3） Parent(T,x) 功能：求二叉樹(shù) T中值為 x的結(jié)點(diǎn)的雙親。 （ 5） Rchild(T,x) 功能：求結(jié)點(diǎn)的右孩子。 （ 7） creatree(amp。root, str)： 功能：創(chuàng)建二叉樹(shù) T。 int top=1,k,j=0。 *b=NULL。 while(ch!=’\0’) { switch(ch) { case ’(’： top++。k=1,break。break。break。 pdata=ch。 pdata=ch。 if(*b==NULL) //為根結(jié)點(diǎn) *b=p。break。break。 ch=str[j]。這就引入了遍歷二叉樹(shù)的問(wèn)題，即如何按某條搜索路徑訪問(wèn)樹(shù)中的每一個(gè)結(jié)點(diǎn)，使得每一個(gè)結(jié)點(diǎn)僅切僅被訪問(wèn)一次。 遍歷對(duì)線性結(jié)構(gòu)是容易解決的。 遍歷二叉樹(shù)和線索二叉樹(shù) 訪問(wèn)是一種抽象操作，是對(duì)結(jié)點(diǎn)的某種處理，例如可以是求結(jié)點(diǎn)的度、或?qū)哟?、打印結(jié)點(diǎn)的信息，或做其他任何工作。 遍歷的次序： 假如以 L、 D、 R分別表示遍歷左子樹(shù)、遍歷根結(jié)點(diǎn)和遍歷右子樹(shù)，遍歷整個(gè)二叉樹(shù)則有 DLR、 LDR、 LRD、 DRL、 RDL、RLD六種遍歷方案。 1．遍歷方案 LDR 中序遍歷 ； LRD 后序遍歷 ； DLR 先序遍歷 1）中序遍歷二叉樹(shù) 算法思想 : 若二叉樹(shù)非空，則： 1）中序遍歷左子樹(shù) 2）訪問(wèn)根結(jié)點(diǎn) 3）中序遍歷右子樹(shù) 算法描述 : void Inorder (BiTree bt){ //bt為根結(jié)點(diǎn)指針 if( bt){//根非空 Inorder (btlchild) 。 } } 2）后序遍歷二叉樹(shù) 算法思想 : 若二叉樹(shù)非空，則： 1）后序遍歷左子樹(shù) 2）后序遍歷右子樹(shù) 3）訪問(wèn)根結(jié)點(diǎn) 算法描述 : void Postorder (BiTree bt){ //bt為根結(jié)點(diǎn)指針 if( bt){ Postorder (btlchild) 。 visit (bt data)； } } 3）先序遍歷二叉樹(shù) 算法思想 : 若二叉樹(shù)非空，則： 1）訪問(wèn)根結(jié)點(diǎn) 2）先序遍歷左子樹(shù) 3）先序遍歷右子樹(shù) 算法描述 : void Preorder (BiTree bt){ //bt為根結(jié)點(diǎn)指針 if( bt){//根非空 visit (btdata)； Preorder (btlchild) 。 } } 例：表達(dá)式 a+b (cd)e/f a c d e f － b ＋ － + 遍歷結(jié)果 : 中序 : a+b c d e / f 后序 : abcd + ef / 先序 : +a b cd / ef （ 1）先序遍歷的遞歸算法如下（假定結(jié)點(diǎn)的元素值為字符型）： include typedef char ElemType。 //定義結(jié)點(diǎn)值 struct node *lchild。 //定義右子結(jié)點(diǎn)指針 }BTree。 //輸出當(dāng)前結(jié)點(diǎn)值 preorder(rootlchild)。 //遞歸前序遍歷右子結(jié)點(diǎn) } return。 //遞歸中序遍歷左子結(jié)點(diǎn) printf(“%c\n”,rootdata)。 //遞歸中序遍歷右子結(jié)點(diǎn) } } (3) 后序遍歷的算法實(shí)現(xiàn) void postorder(BTree *root) //后序遍歷 { if(root!=NULL) //如果不是空結(jié)點(diǎn) { postorder(rootlchild)。 //遞歸后序遍歷右子結(jié)點(diǎn) printf(“%c\n”,rootdata)。}}} } 中序遍歷非遞歸算法 ,s為存儲(chǔ)二叉樹(shù)結(jié)點(diǎn)指針棧： 操作過(guò)程： 根結(jié)點(diǎn)先進(jìn)棧，左結(jié)點(diǎn)緊跟根后面進(jìn)棧 ,右結(jié)點(diǎn)在根出棧后入棧； 每個(gè)結(jié)點(diǎn)都要進(jìn)一次和出一次棧，并且總是訪問(wèn)棧頂元素， 因此，算法正確，時(shí)間復(fù)雜度為 O(n)。 從二叉樹(shù)的遍歷定義可知，三種遍歷算法的不同之處僅在于訪問(wèn)根結(jié)點(diǎn)和遍歷左右子樹(shù)的先后關(guān)系 。遍歷二叉樹(shù)的算法中的基本操作是訪問(wèn)結(jié)點(diǎn)，顯然，不論按那種方式進(jìn)行遍歷，對(duì)含 n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其時(shí)間復(fù)雜度均為 O(n)。最壞的情況下為 n， 則空間復(fù)雜度也為 O(n)。還可以在遍歷過(guò)程中生成結(jié)點(diǎn)，建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。先序序列中必須加入虛結(jié)點(diǎn)以示空指針的位置。 【 解】假設(shè)虛結(jié)點(diǎn)輸入時(shí)以空格字符表示，相應(yīng)的構(gòu)造算法為： void CreateBinTree (BTree **T) { //構(gòu)造二叉鏈表。 if((ch=getchar())==“ ”) *T=NULL。 //生成結(jié)點(diǎn) (*T)data=ch； CreateBinTree(amp。(*T)rchild)； //構(gòu)造右子樹(shù) } } 調(diào)用該算法時(shí)，應(yīng)將待建立的二叉鏈表的根指針的地址作為實(shí)參 。但是在二叉樹(shù)上只能找到結(jié)點(diǎn)的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷過(guò)程中才能得到，那么，如何保存遍歷二叉樹(shù)后動(dòng)態(tài)得到的線性序列，以便快速找到某個(gè)結(jié)點(diǎn)的直接前驅(qū)和后繼？ 2. 分析 ： n個(gè)結(jié)點(diǎn)有 n1個(gè)前驅(qū)和 n1個(gè)后繼； 一共有 2n個(gè)鏈域，其中： n+1個(gè)空鏈域， n1個(gè)指針域； 因此 , 可以用空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼。 3. 線索二叉樹(shù) ： 有效利用二叉鏈表中空的存儲(chǔ)空間，指定原有的孩子指針為空的域來(lái)存放指向前驅(qū)和后繼的信息，這樣的指針被稱為 “ 線索 ” 。 ⑴ 結(jié)點(diǎn)結(jié)構(gòu) 在二叉鏈表中增加 ltag 和 rtag 兩個(gè)標(biāo)志域 若結(jié)點(diǎn)有左子樹(shù)，則左鏈域 lchild指示其左孩子（ ltag= 0）； 否則，令左鏈域指示其前驅(qū)（ ltag=1）； 若結(jié)點(diǎn)有右子樹(shù)，則右鏈域 rchild指示其右孩子（ rtag= 0）； 否則，令右鏈域指示其后繼（ rtag= 1）； l t a g l c h i l d d a t a r c h i l d r t a g 中序、先序和后序線索二叉樹(shù)中所有實(shí)線均相同，所有結(jié)點(diǎn)的標(biāo)志位取值也完全相同，只是當(dāng)標(biāo)志位取 1時(shí)，不同的線索二叉樹(shù)將用不同的虛線表示。 0 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 10 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 1( a ) 中 序 線 索 樹(shù) ( b ) 先 序 線 索 樹(shù)r o o t r o o t0 A 00 10 B 1 0 C 01 D 0 1 E 1 1 F 11 G 1( c ) 后 序 線 索 樹(shù)r o o t圖 614 線索二叉樹(shù) 線索二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)可描述如下： struct node { ElemenType data。 //左標(biāo)志域 int rtag。 //左指針域 struct node *rchild。 同樣，線索二叉樹(shù)根據(jù)遍歷規(guī)則的不同，可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)、后序線索二叉樹(shù)。(*current)lchild, pre)。 //建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線索 (*current)ltag=1。 //建立前驅(qū)結(jié)點(diǎn)的后繼線索 (*pre)rtag=1。 thread(amp。 //右子樹(shù)線索化 } } BTree *creathread(BTree *b) //中序線索化二叉樹(shù) { BTree *pre,*root,*current。 //創(chuàng)建根結(jié)點(diǎn) rootdata=’r’。rootrtag=0。 //空二叉樹(shù) { rootlchild=root。 } else else { current=rootlchild=b。 pre=root。current,amp。 //中序遍歷線索化二叉樹(shù) prerchild=root。 rootrchild=pre。 } return root； } 樹(shù)和森林的遍歷