數(shù)據(jù)結(jié)構(gòu)C語言樹形結(jié)構(gòu)學習教案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)C語言樹形結(jié)構(gòu)語言樹形結(jié)構(gòu)第一頁，共115頁。7.1.1 7.1.1 樹的定義樹的定義 形式化定義：形式化定義： 樹：樹：T TK,RK,R。K K是包含是包含n n個結(jié)點個結(jié)點(ji din)(ji din)的的有窮集合有窮集合(n0),(n0),關(guān)系關(guān)系R R滿足以下條件滿足以下條件: : (1) (1)有且僅有一個結(jié)點有且僅有一個結(jié)點(ji din)k0K,(ji din)k0K,它對于它對于關(guān)系關(guān)系R R來說沒有前驅(qū)結(jié)點來說沒有前驅(qū)結(jié)點(ji din),(ji din),結(jié)點結(jié)點(ji din)k0(ji din)k0稱作樹的根。稱作樹的根。 (2

2、) (2)除結(jié)點除結(jié)點(ji din)k0(ji din)k0外外,K,K中的每個結(jié)點中的每個結(jié)點(ji (ji din)din)對于關(guān)系對于關(guān)系R R來說都有且僅有一個前驅(qū)結(jié)點來說都有且僅有一個前驅(qū)結(jié)點(ji (ji din)din)。 (3)K (3)K中每個結(jié)點中每個結(jié)點(ji din)(ji din)對于關(guān)系對于關(guān)系R R來說可以來說可以有多個后繼結(jié)點有多個后繼結(jié)點(ji din)(ji din)。第1頁/共115頁第二頁，共115頁。遞歸定義：遞歸定義： 樹是由樹是由n(n0)個結(jié)點組成個結(jié)點組成(z chn)的有限集合的有限集合(記為記為T)。其中。其中, 如果如果n=0,它是一棵

3、空樹它是一棵空樹,這是樹的特例；這是樹的特例； 如果如果n0,這這n個結(jié)點中存在個結(jié)點中存在(有僅存在有僅存在)一個結(jié)點一個結(jié)點作為樹的根結(jié)點作為樹的根結(jié)點,簡稱為根簡稱為根(root),其余結(jié)點可分為其余結(jié)點可分為m (m0)個互不相交的有限集個互不相交的有限集T1,T2,Tm,其中每一其中每一棵子集本身又是一棵符合本定義的樹棵子集本身又是一棵符合本定義的樹,稱為根稱為根root的的子樹。子樹。第2頁/共115頁第三頁，共115頁。7 . 1 . 2 7 . 1 . 2 樹 的 表 示樹 的 表 示(biosh)(biosh) (1) (1)樹形表示法。這是樹的最基本的表示樹形表示法。這是樹

4、的最基本的表示, ,使用一使用一棵 倒 置 的 樹 表 示 樹 結(jié) 構(gòu)棵 倒 置 的 樹 表 示 樹 結(jié) 構(gòu) , , 非 常 直 觀 和 形 象非 常 直 觀 和 形 象(xngxing)(xngxing)。下圖就是采用這種表示法。下圖就是采用這種表示法。 A C G J B E D F I H M K L 樹形表示法樹形表示法 第3頁/共115頁第四頁，共115頁。 (2)文氏圖表示法。使用集合以及集合文氏圖表示法。使用集合以及集合的包含關(guān)系描述的包含關(guān)系描述(mio sh)樹結(jié)構(gòu)。下圖樹結(jié)構(gòu)。下圖就是樹的文氏圖表示法。就是樹的文氏圖表示法。 H L D K I M C G J E B F

5、文氏圖表示法文氏圖表示法 A 第4頁/共115頁第五頁，共115頁。 (3)凹入表示法。使用凹入表示法。使用(shyng)線段的伸縮描線段的伸縮描述樹結(jié)構(gòu)。下圖是樹的凹入表示法。述樹結(jié)構(gòu)。下圖是樹的凹入表示法。第5頁/共115頁第六頁，共115頁。 (4)括號表示法。將樹的根結(jié)點寫在括號的左邊括號表示法。將樹的根結(jié)點寫在括號的左邊,除除根結(jié)點之外的其余根結(jié)點之外的其余(qy)結(jié)點寫在括號中并用逗號間隔結(jié)點寫在括號中并用逗號間隔來描述樹結(jié)構(gòu)。下圖是樹的括號表示法。來描述樹結(jié)構(gòu)。下圖是樹的括號表示法。 括號表示法括號表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 第6頁/共115

6、頁第七頁，共115頁。7.1.3 7.1.3 樹的基本術(shù)語樹的基本術(shù)語 1. 1. 結(jié)點的度與樹的度：樹中某個結(jié)點的度與樹的度：樹中某個(mu )(mu )結(jié)點結(jié)點的子樹的個數(shù)稱為該結(jié)點的度。樹中各結(jié)點的度的最大的子樹的個數(shù)稱為該結(jié)點的度。樹中各結(jié)點的度的最大值稱為樹的度值稱為樹的度, ,通常將度為通常將度為m m的樹稱為的樹稱為m m次樹。次樹。 2. 2. 分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非分支結(jié)點與葉結(jié)點：度不為零的結(jié)點稱為非終端結(jié)點終端結(jié)點, ,又叫分支結(jié)點。度為零的結(jié)點稱為終端結(jié)點或又叫分支結(jié)點。度為零的結(jié)點稱為終端結(jié)點或葉結(jié)點。在分支結(jié)點中葉結(jié)點。在分支結(jié)點中, ,每個結(jié)點的分

7、支數(shù)就是該結(jié)點的每個結(jié)點的分支數(shù)就是該結(jié)點的度。如對于度為度。如對于度為1 1的結(jié)點的結(jié)點, ,其分支數(shù)為其分支數(shù)為1,1,被稱為單分支結(jié)被稱為單分支結(jié)點；對于度為點；對于度為2 2的結(jié)點的結(jié)點, ,其分支數(shù)為其分支數(shù)為2,2,被稱為雙分支結(jié)點被稱為雙分支結(jié)點, ,其余類推。其余類推。第7頁/共115頁第八頁，共115頁。 3. 路徑與路徑長度：對于任意兩個結(jié)點路徑與路徑長度：對于任意兩個結(jié)點ki和和kj,若樹若樹中存在一個結(jié)點序列中存在一個結(jié)點序列ki,ki1,ki2,kin,kj,使得序列中除使得序列中除ki外的任一結(jié)點都是其在序列中的前一個結(jié)點的后繼外的任一結(jié)點都是其在序列中的前一個結(jié)點

8、的后繼,則稱則稱該結(jié)點序列為由該結(jié)點序列為由ki到到kj的一條路徑的一條路徑,用路徑所通過的結(jié)點序用路徑所通過的結(jié)點序列列(ki,ki1,ki2,kj)表示這條路徑。路徑的長度等于路徑表示這條路徑。路徑的長度等于路徑所通過的結(jié)點數(shù)目減所通過的結(jié)點數(shù)目減1(即路徑上分支數(shù)目即路徑上分支數(shù)目)?？梢姟？梢?路徑就路徑就是從是從ki出發(fā)出發(fā)“自上而下自上而下”到達到達kj所通過的樹中結(jié)點序列。顯所通過的樹中結(jié)點序列。顯然然(xinrn),從樹的根結(jié)點到樹中其余結(jié)點均存在一條路從樹的根結(jié)點到樹中其余結(jié)點均存在一條路徑。徑。第8頁/共115頁第九頁，共115頁。 4. 4. 孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點

9、：在孩子結(jié)點、雙親結(jié)點和兄弟結(jié)點：在一棵樹中一棵樹中, ,每個結(jié)點的后繼每個結(jié)點的后繼, ,被稱作該結(jié)點的被稱作該結(jié)點的孩子結(jié)點孩子結(jié)點( (或子女結(jié)點或子女結(jié)點) )。相應地。相應地, ,該結(jié)點被該結(jié)點被稱作孩子結(jié)點的雙親結(jié)點稱作孩子結(jié)點的雙親結(jié)點( (或父母結(jié)點或父母結(jié)點) )。具。具有有(jyu)(jyu)同一雙親的孩子結(jié)點互為兄弟同一雙親的孩子結(jié)點互為兄弟結(jié)點。進一步推廣這些關(guān)系結(jié)點。進一步推廣這些關(guān)系, ,可以把每個結(jié)可以把每個結(jié)點的所有子樹中的結(jié)點稱為該結(jié)點的子孫結(jié)點的所有子樹中的結(jié)點稱為該結(jié)點的子孫結(jié)點點, ,從樹根結(jié)點到達該結(jié)點的路徑上經(jīng)過的從樹根結(jié)點到達該結(jié)點的路徑上經(jīng)過的所

10、有結(jié)點被稱作該結(jié)點的祖先結(jié)點。所有結(jié)點被稱作該結(jié)點的祖先結(jié)點。第9頁/共115頁第十頁，共115頁。 5. 結(jié)點的層次和樹的高度：樹中的每個結(jié)點都處結(jié)點的層次和樹的高度：樹中的每個結(jié)點都處在一定的層次上。結(jié)點的層次從樹根開始定義在一定的層次上。結(jié)點的層次從樹根開始定義,根結(jié)點根結(jié)點為第為第1層層,它的孩子結(jié)點為第它的孩子結(jié)點為第2層層,以此類推以此類推,一個結(jié)點所一個結(jié)點所在的層次為其雙親結(jié)點所在的層次加在的層次為其雙親結(jié)點所在的層次加1。樹中結(jié)點的。樹中結(jié)點的最大層次稱為樹的高度最大層次稱為樹的高度(或樹的深度或樹的深度)。 7. 有序樹和無序樹：若樹中各結(jié)點的子樹是按照有序樹和無序樹：若樹

11、中各結(jié)點的子樹是按照一定的次序從左向右安排一定的次序從左向右安排(npi)的的,且相對次序是不且相對次序是不能隨意變換的能隨意變換的,則稱為有序樹則稱為有序樹,否則稱為無序樹。否則稱為無序樹。第10頁/共115頁第十一頁，共115頁。 7. 森林：森林：n(n0)個互不相交的樹的集合稱個互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近為森林。森林的概念與樹的概念十分相近,因為因為(yn wi)只要把樹的根結(jié)點刪去就成了森林。只要把樹的根結(jié)點刪去就成了森林。反之反之,只要給只要給n棵獨立的樹加上一個結(jié)點棵獨立的樹加上一個結(jié)點,并把這并把這n棵樹作為該結(jié)點的子樹棵樹作為該結(jié)點的子樹,則森林

12、就變成了樹。則森林就變成了樹。第11頁/共115頁第十二頁，共115頁。7.1.4 7.1.4 樹的性質(zhì)樹的性質(zhì)性質(zhì)性質(zhì)1 1 樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1 1。 證明：根據(jù)證明：根據(jù)(gnj)(gnj)樹的定義樹的定義, ,在一棵樹中在一棵樹中, ,除樹根除樹根結(jié)點外結(jié)點外, ,每個結(jié)點有且僅有一個前驅(qū)結(jié)點。也就是說每個結(jié)點有且僅有一個前驅(qū)結(jié)點。也就是說, ,每每個結(jié)點與指向它的一個分支一一對應個結(jié)點與指向它的一個分支一一對應, ,所以除樹根之外的所以除樹根之外的結(jié)點數(shù)等于所有結(jié)點的分支數(shù)結(jié)點數(shù)等于所有結(jié)點的分支數(shù)( (度數(shù)度數(shù)),),從而可得樹中的結(jié)從

13、而可得樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加點數(shù)等于所有結(jié)點的度數(shù)加1 1。第12頁/共115頁第十三頁，共115頁。 性質(zhì)性質(zhì)2 度為度為m的樹中第的樹中第i層上至多有層上至多有mi-1個結(jié)點個結(jié)點,這里應這里應有有i1。 證明證明(采用數(shù)學歸納法采用數(shù)學歸納法) 對于第一層對于第一層,因為樹中的第一層上只有一個結(jié)點因為樹中的第一層上只有一個結(jié)點,即整個即整個樹的根結(jié)點樹的根結(jié)點,而由而由i=1代入代入mi-1,得得mi-1=m1-1=1,也同樣得到也同樣得到只有一個結(jié)點只有一個結(jié)點,顯然結(jié)論成立。顯然結(jié)論成立。 假設假設(jish)對于第對于第(i-1)層層(i1)命題成立命題成立,即度為即度為

14、m的的樹中第樹中第(i-1)層上至多有層上至多有mi-2個結(jié)點個結(jié)點,則根據(jù)樹的度的定義則根據(jù)樹的度的定義,度度為為m的樹中每個結(jié)點至多有的樹中每個結(jié)點至多有m個孩子結(jié)點個孩子結(jié)點,所以第所以第i層上的結(jié)層上的結(jié)點數(shù)至多為第點數(shù)至多為第(i-1)層上結(jié)點數(shù)的層上結(jié)點數(shù)的m倍倍,即至多為即至多為mi-2m=mi-1個個,這與命題相同這與命題相同,故命題成立。故命題成立。第13頁/共115頁第十四頁，共115頁。 性質(zhì)性質(zhì)3 高度高度(god)為為h的的m次樹至多有次樹至多有 個結(jié)點。個結(jié)點。 證明：由樹的性質(zhì)證明：由樹的性質(zhì)2可知可知,第第i層上最多結(jié)點數(shù)為層上最多結(jié)點數(shù)為mi-1(i=1,2,

15、h),顯然當高度顯然當高度(god)為為h的的m次樹次樹(即度為即度為m的的樹樹)上每一層都達到最多結(jié)點數(shù)時上每一層都達到最多結(jié)點數(shù)時,整個整個m次樹具有最多結(jié)次樹具有最多結(jié)點數(shù)點數(shù),因此有：因此有：整 個 樹 的 最 多 結(jié) 點 數(shù)整 個 樹 的 最 多 結(jié) 點 數(shù) = 每 一 層 最 多 結(jié) 點 數(shù) 之 和每 一 層 最 多 結(jié) 點 數(shù) 之 和=m0+m1+m2+mh-1 = 。11 mmh11 mmh第14頁/共115頁第十五頁，共115頁。 性質(zhì)性質(zhì)4 具有具有n個結(jié)點個結(jié)點(ji din)的的m次樹的最小高度為次樹的最小高度為logm(n(m-1)+1)。 證明：設具有證明：設具有n

16、個結(jié)點個結(jié)點(ji din)的的m次樹的高度為次樹的高度為h,若若在該樹中前在該樹中前h-1層都是滿的層都是滿的,即每一層的結(jié)點即每一層的結(jié)點(ji din)數(shù)都數(shù)都等于等于mi-1個個(1ih-1),第第h層層(即最后一層即最后一層)的結(jié)點的結(jié)點(ji din)數(shù)可能滿數(shù)可能滿,也可能不滿也可能不滿,則該樹具有最小的高度。其高度則該樹具有最小的高度。其高度h可可計算如下：計算如下：第15頁/共115頁第十六頁，共115頁。根據(jù)樹的性質(zhì)根據(jù)樹的性質(zhì)(xngzh)3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m為底取對數(shù)后得：為底取對數(shù)后得：h-1logm(n(m

17、-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整數(shù)只能取整數(shù),所以所以 h=logm(n(m-1)+1)結(jié)論得證。結(jié)論得證。111 mmh11 mmh第16頁/共115頁第十七頁，共115頁。 例例7.1 含含n個結(jié)點的三次樹的最小高度個結(jié)點的三次樹的最小高度(god)是多少？是多少？ 解：設含解：設含n個結(jié)點的個結(jié)點的(為完全三次樹時高度為完全三次樹時高度(god)最最小小)的三次樹的最小高度的三次樹的最小高度(god)為為h,則有：則有： 1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2 3h-12n+13

18、h 即：即：h= log3(2n+1)第17頁/共115頁第十八頁，共115頁。7.1.5 7.1.5 樹的基本樹的基本(jbn)(jbn)運運算算 樹的運算主要樹的運算主要(zhyo)(zhyo)分為三大類：分為三大類： 第一類第一類, ,尋找滿足某種特定關(guān)系的結(jié)點尋找滿足某種特定關(guān)系的結(jié)點, ,如尋找當如尋找當前結(jié)點的雙親結(jié)點等；前結(jié)點的雙親結(jié)點等； 第二類第二類, ,插入或刪除某個結(jié)點插入或刪除某個結(jié)點, ,如在樹的當前結(jié)點如在樹的當前結(jié)點上插入一個新結(jié)點或刪除當前結(jié)點的第上插入一個新結(jié)點或刪除當前結(jié)點的第i i個孩子結(jié)點個孩子結(jié)點等；等； 第三類第三類, ,遍歷樹中每個結(jié)點遍歷樹中每個

19、結(jié)點, ,這里著重介紹。這里著重介紹。第18頁/共115頁第十九頁，共115頁。 樹的遍歷運算是指按某種方式訪問樹中的每一個樹的遍歷運算是指按某種方式訪問樹中的每一個(y )結(jié)點且每一個結(jié)點且每一個(y )結(jié)點只被訪問一次。樹的遍結(jié)點只被訪問一次。樹的遍歷運算的算法主要有先根遍歷和后根遍歷兩種。注意歷運算的算法主要有先根遍歷和后根遍歷兩種。注意,下面的先根遍歷和后根遍歷算法都是遞歸的。下面的先根遍歷和后根遍歷算法都是遞歸的。 1. 先根遍歷先根遍歷 先根遍歷過程為：先根遍歷過程為： (1)訪問根結(jié)點；訪問根結(jié)點； (2)按照從左到右的次序先根遍歷根結(jié)點的每一棵子按照從左到右的次序先根遍歷根結(jié)點

20、的每一棵子樹。樹。 第19頁/共115頁第二十頁，共115頁。2. 后根遍歷后根遍歷 后根遍歷過程為：后根遍歷過程為： (1)按照從左到右的次序后根遍歷根結(jié)點按照從左到右的次序后根遍歷根結(jié)點(ji din)的每的每一棵子樹；一棵子樹； (2)訪問根結(jié)點訪問根結(jié)點(ji din)。第20頁/共115頁第二十一頁，共115頁。7.1.6 7.1.6 樹的存儲樹的存儲(cn ch)(cn ch)結(jié)結(jié)構(gòu)構(gòu)1. 1. 雙親存儲結(jié)構(gòu)雙親存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu)這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu), ,用一組連續(xù)空用一組連續(xù)空間 存 儲 樹 的 所 有 結(jié) 點間 存 儲 樹 的 所 有 結(jié) 點 ,

21、 , 同 時 在 每 個 結(jié) 點 中 附 設同 時 在 每 個 結(jié) 點 中 附 設(fsh)(fsh)一個偽指針指示其雙親結(jié)點的位置。一個偽指針指示其雙親結(jié)點的位置。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 樹的雙親樹的雙親(shungqn)(shungqn)存儲結(jié)構(gòu)示意圖存儲結(jié)構(gòu)示意圖第21頁/共115頁第二十二頁，共115頁。2. 孩子孩子(hi zi)鏈存儲結(jié)構(gòu)鏈存儲結(jié)構(gòu) 孩子孩子(hi zi)鏈存儲結(jié)構(gòu)可按樹的度鏈存儲結(jié)構(gòu)可按樹的度(即樹中所有結(jié)點度即樹中所有結(jié)點度的最大值的最大值)設計結(jié)點的孩子

22、設計結(jié)點的孩子(hi zi)結(jié)點指針域個數(shù)。下圖結(jié)點指針域個數(shù)。下圖(a)的樹對應的孩子的樹對應的孩子(hi zi)鏈存儲結(jié)構(gòu)如圖鏈存儲結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B C D E F G (b) 樹的孩子鏈存儲樹的孩子鏈存儲(cn ch)(cn ch)結(jié)結(jié)構(gòu)示意圖構(gòu)示意圖第22頁/共115頁第二十三頁，共115頁。3. 孩子兄弟鏈存儲結(jié)構(gòu)孩子兄弟鏈存儲結(jié)構(gòu) 孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設計三個域：孩子兄弟鏈存儲結(jié)構(gòu)是為每個結(jié)點設計三個域：一個一個(y )數(shù)據(jù)元素域數(shù)據(jù)元素域,一個一個(y )該結(jié)點的第一個該結(jié)點的第一個(y )孩子結(jié)點指針域孩子結(jié)點指針

23、域,一個一個(y )該結(jié)點的下一個該結(jié)點的下一個(y )兄弟結(jié)點指針域。下圖兄弟結(jié)點指針域。下圖(a)的樹對應的孩子兄的樹對應的孩子兄弟鏈存儲結(jié)構(gòu)如圖弟鏈存儲結(jié)構(gòu)如圖(b)所示。所示。 A B C F D E (a) G A B D C E G F (b) 樹的孩子兄弟鏈存儲樹的孩子兄弟鏈存儲(cn ch)(cn ch)結(jié)構(gòu)示意圖結(jié)構(gòu)示意圖第23頁/共115頁第二十四頁，共115頁。7 . 2 7 . 2 二 叉 樹 概 念二 叉 樹 概 念(ginin)(ginin)和性質(zhì)和性質(zhì) 7.2.1 7.2.1 二叉樹概念二叉樹概念(ginin)(ginin)7.2.2 7.2.2 二叉樹性質(zhì)二叉樹

24、性質(zhì)(xngzh)(xngzh)7.2.3 7.2.3 二叉樹與樹、森林之間的轉(zhuǎn)換二叉樹與樹、森林之間的轉(zhuǎn)換第24頁/共115頁第二十五頁，共115頁。7.2.1 7.2.1 二叉樹概念二叉樹概念 二叉樹也稱為二叉樹也稱為(chn wi)(chn wi)二次樹或二分樹二次樹或二分樹, ,它是有限它是有限的結(jié)點集合的結(jié)點集合, ,這個集合或者是空這個集合或者是空, ,或者由一個根結(jié)點和兩棵互或者由一個根結(jié)點和兩棵互不相交的稱為不相交的稱為(chn wi)(chn wi)左子樹和右子樹的二叉樹組成。左子樹和右子樹的二叉樹組成。 二叉樹的定義是一種遞歸定義。二叉樹的定義是一種遞歸定義。第25頁/共1

25、15頁第二十六頁，共115頁。 二叉樹有五種基本形態(tài)二叉樹有五種基本形態(tài), ,如下如下(rxi)(rxi)圖所示圖所示, ,任何復雜的二叉樹都是這五種基本形態(tài)的復合。任何復雜的二叉樹都是這五種基本形態(tài)的復合。第26頁/共115頁第二十七頁，共115頁。 從定義看到,二叉樹是一種(y zhn)特殊的樹,其表示法也與樹的表示法一樣,有樹形表示法、文氏圖表示法、凹入表示法和括號表示法等。第27頁/共115頁第二十八頁，共115頁。 在一棵二叉樹中在一棵二叉樹中, ,如果所有分支結(jié)點如果所有分支結(jié)點(ji din)(ji din)都有左孩子結(jié)點都有左孩子結(jié)點(ji din)(ji din)和右孩子結(jié)點

26、和右孩子結(jié)點(ji (ji din),din),并且葉結(jié)點并且葉結(jié)點(ji din)(ji din)都集中在二叉樹的都集中在二叉樹的最下一層最下一層, ,這樣的二叉樹稱為滿二叉樹。下圖所示就這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫M二叉樹的結(jié)點是一棵滿二叉樹?？梢詫M二叉樹的結(jié)點(ji (ji din)din)進行連續(xù)編號進行連續(xù)編號, ,約定編號從樹根為約定編號從樹根為1 1開始開始, ,按照按照層數(shù)從小到大、同一層從左到右的次序進行。圖中每層數(shù)從小到大、同一層從左到右的次序進行。圖中每個結(jié)點個結(jié)點(ji din)(ji din)外邊的數(shù)字為對該結(jié)點外邊的數(shù)字為對該結(jié)點(j

27、i (ji din)din)的編號。的編號。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿二叉樹滿二叉樹 第28頁/共115頁第二十九頁，共115頁。 若二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可以若二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可以小于小于2,2,并且最下面一層的葉結(jié)點并且最下面一層的葉結(jié)點 都依次都依次(yc)(yc)排列排列在該層最左邊的位置上在該層最左邊的位置上, ,則這樣的二叉樹稱為完全二叉則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二樹。如下圖所示為一棵完全二

28、叉樹。同樣可以對完全二叉樹中每個結(jié)點進行連續(xù)編號叉樹中每個結(jié)點進行連續(xù)編號, ,編號的方法同滿二叉樹編號的方法同滿二叉樹相同。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編號。相同。圖中每個結(jié)點外邊的數(shù)字為對該結(jié)點的編號。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 第29頁/共115頁第三十頁，共115頁。7.2.2 7.2.2 二叉樹性質(zhì)二叉樹性質(zhì) 性質(zhì)性質(zhì)1 1 非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加數(shù)加1 1。 證明：設二叉樹上葉結(jié)點數(shù)為證明：設二叉樹上葉結(jié)點數(shù)為n0,n0,單分支結(jié)點單分支結(jié)

29、點數(shù)為數(shù)為n1,n1,雙分支結(jié)點數(shù)為雙分支結(jié)點數(shù)為n2,n2,則總結(jié)點數(shù)則總結(jié)點數(shù)=n0+n1+n2=n0+n1+n2。在一棵二叉樹中在一棵二叉樹中, ,所有結(jié)點的分支數(shù)所有結(jié)點的分支數(shù)( (即度數(shù)即度數(shù)) )應等于應等于單分支結(jié)點數(shù)加上雙分支結(jié)點數(shù)的單分支結(jié)點數(shù)加上雙分支結(jié)點數(shù)的2 2倍倍, ,即總的分支數(shù)即總的分支數(shù)=n1+2n2=n1+2n2。 由于二叉樹中除根結(jié)點以外由于二叉樹中除根結(jié)點以外, ,每個結(jié)點都有惟一每個結(jié)點都有惟一的一個分支指向的一個分支指向(zh xin)(zh xin)它它, ,因此二叉樹中有：總因此二叉樹中有：總的分支數(shù)的分支數(shù)= =總結(jié)點數(shù)總結(jié)點數(shù)-1-1。 由上

30、述三個等式可得：由上述三個等式可得：n1+2n2=n0+n1+n2-1n1+2n2=n0+n1+n2-1即：即：n0=n2+1n0=n2+1第30頁/共115頁第三十一頁，共115頁。 性質(zhì)性質(zhì)2 非空二叉樹上第非空二叉樹上第i層上至多有層上至多有2i-1個結(jié)點個結(jié)點(ji din),這里應有這里應有i1。 由樹的性質(zhì)由樹的性質(zhì)2可推出?？赏瞥觥?性質(zhì)性質(zhì)3 高度為高度為h的二叉樹至多有的二叉樹至多有2h-1個結(jié)點個結(jié)點(ji din)(h1)。 由樹的性質(zhì)由樹的性質(zhì)3可推出?？赏瞥觥５?1頁/共115頁第三十二頁，共115頁。 性質(zhì)性質(zhì)4 對完全二叉樹中編號為對完全二叉樹中編號為i的結(jié)點的結(jié)

31、點(1in,n1,n為結(jié)點數(shù)為結(jié)點數(shù))有：有： (1)若若in/2,即即2in,則編號為則編號為i的結(jié)點為分支結(jié)點的結(jié)點為分支結(jié)點,否則為葉子結(jié)點。否則為葉子結(jié)點。 (2)若若n為奇數(shù)為奇數(shù),則每個分支結(jié)點都既有左孩子則每個分支結(jié)點都既有左孩子(hi zi)結(jié)點結(jié)點,也有右孩子也有右孩子(hi zi)結(jié)點；若結(jié)點；若n為偶數(shù)為偶數(shù),則編號最大的則編號最大的分支結(jié)點分支結(jié)點(編號為編號為)只有左孩子只有左孩子(hi zi)結(jié)點結(jié)點,沒有右孩子沒有右孩子(hi zi)結(jié)點結(jié)點,其余分支結(jié)點都有左、右孩子其余分支結(jié)點都有左、右孩子(hi zi)結(jié)點。結(jié)點。第32頁/共115頁第三十三頁，共115頁。

32、 (3)若編號為若編號為i的結(jié)點有左孩子結(jié)點的結(jié)點有左孩子結(jié)點,則左孩子結(jié)點的編號則左孩子結(jié)點的編號為為2i；若編號為；若編號為i的結(jié)點有右孩子結(jié)點的結(jié)點有右孩子結(jié)點,則右孩子結(jié)點的編號則右孩子結(jié)點的編號為為(2i+1)。 (4)除樹根結(jié)點外除樹根結(jié)點外,若一個若一個(y )結(jié)點的編號為結(jié)點的編號為i,則它的雙則它的雙親結(jié)點的編號為親結(jié)點的編號為i/2,也就是說也就是說,當當i為偶數(shù)時為偶數(shù)時,其雙親結(jié)點其雙親結(jié)點的編號為的編號為i/2,它是雙親結(jié)點的左孩子結(jié)點它是雙親結(jié)點的左孩子結(jié)點,當當i為奇數(shù)時為奇數(shù)時,其雙其雙親結(jié)點的編號為親結(jié)點的編號為(i-1)/2,它是雙親結(jié)點的右孩子結(jié)點。它是雙

33、親結(jié)點的右孩子結(jié)點。第33頁/共115頁第三十四頁，共115頁。 性質(zhì)性質(zhì)5 具有具有n個個(n0)結(jié)點的完全結(jié)點的完全(wnqun)二二叉樹的高度為叉樹的高度為log2(n+1)或或log2n+1。 由完全由完全(wnqun)二叉樹的定義和樹的性質(zhì)二叉樹的定義和樹的性質(zhì)3可推可推出。出。第34頁/共115頁第三十五頁，共115頁。7.2.3 7.2.3 二叉樹與樹、森林二叉樹與樹、森林(snln)(snln)之之間的轉(zhuǎn)換間的轉(zhuǎn)換1森林森林(snln)、樹轉(zhuǎn)換為二叉樹、樹轉(zhuǎn)換為二叉樹 (1)在所有相鄰兄弟結(jié)點在所有相鄰兄弟結(jié)點(森林森林(snln)中每棵樹的根結(jié)中每棵樹的根結(jié)點可看成是兄弟結(jié)點

34、點可看成是兄弟結(jié)點)之間加一水平連線。之間加一水平連線。 (2)對每個非葉結(jié)點對每個非葉結(jié)點k,除了其最左邊的孩子結(jié)點外除了其最左邊的孩子結(jié)點外,刪去刪去k與其他孩子結(jié)點的連線。與其他孩子結(jié)點的連線。 (3)所有水平線段以左邊結(jié)點為軸心順時針旋轉(zhuǎn)所有水平線段以左邊結(jié)點為軸心順時針旋轉(zhuǎn)45度。度。 通過以上步驟通過以上步驟,原來的森林原來的森林(snln)就轉(zhuǎn)換為一棵二叉就轉(zhuǎn)換為一棵二叉樹。一般的樹是森林樹。一般的樹是森林(snln)中的特殊情況中的特殊情況,由一般的樹由一般的樹轉(zhuǎn)換的二叉樹的根結(jié)點的右孩子結(jié)點始終為空轉(zhuǎn)換的二叉樹的根結(jié)點的右孩子結(jié)點始終為空,原因是一原因是一般的樹的根結(jié)點不存在

35、兄弟結(jié)點和相鄰的樹。般的樹的根結(jié)點不存在兄弟結(jié)點和相鄰的樹。第35頁/共115頁第三十六頁，共115頁。 A B C D E F G H I A B E F G C D H I (a) (c) A B C D E F G H I (b) 將森林將森林(snln)轉(zhuǎn)換為二叉樹的過程轉(zhuǎn)換為二叉樹的過程第36頁/共115頁第三十七頁，共115頁。2. 2. 二叉樹還原二叉樹還原(hun yun)(hun yun)為森林、樹為森林、樹 (1) (1)對于一棵二叉樹中任一結(jié)點對于一棵二叉樹中任一結(jié)點(ji din)k0,(ji din)k0,沿沿著著k1k1右孩子結(jié)點右孩子結(jié)點(ji din)(ji d

36、in)的右子樹方向搜索所有右的右子樹方向搜索所有右孩子結(jié)點孩子結(jié)點(ji din),(ji din),即搜索結(jié)點即搜索結(jié)點(ji din)(ji din)序列序列k2,k3,km,k2,k3,km,其中其中ki+1ki+1為為kiki的右孩子結(jié)點的右孩子結(jié)點(ji (ji din)(1idin)(1im),kmm),km沒有右孩子結(jié)點沒有右孩子結(jié)點(ji din)(ji din)。 (2) (2)刪去刪去k1,k2,kmk1,k2,km之間連線。之間連線。 (3) (3)若若k1k1有雙親結(jié)點有雙親結(jié)點(ji din)k,(ji din)k,則連接則連接k k與與ki(2im)ki(2im)。

37、 (4) (4)將圖形規(guī)整化將圖形規(guī)整化, ,使各結(jié)點使各結(jié)點(ji din)(ji din)按層次按層次排列。排列。第37頁/共115頁第三十八頁，共115頁。 A D H B F C G E A B D C F E H G (a) (c) A B D C F E H G (b) 將一棵二叉樹還原將一棵二叉樹還原(hun yun)(hun yun)為樹的過程為樹的過程第38頁/共115頁第三十九頁，共115頁。7.3 7.3 二叉樹存儲二叉樹存儲(cn (cn ch)ch)結(jié)構(gòu)結(jié)構(gòu) 7.3.1 7.3.1 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu)(jigu) (jigu) 7.3.2 7.3

38、.2 二叉樹的鏈式存儲二叉樹的鏈式存儲(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu)第39頁/共115頁第四十頁，共115頁。7.3.1 7.3.1 二叉樹的順序存儲結(jié)構(gòu)二叉樹的順序存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：二叉樹的順序存儲結(jié)構(gòu)中結(jié)點的存放次序是：對該樹中每個結(jié)點進行編號對該樹中每個結(jié)點進行編號, ,其編號從小到大的順序其編號從小到大的順序就是結(jié)點存放在連續(xù)存儲單元的先后次序。若把二叉就是結(jié)點存放在連續(xù)存儲單元的先后次序。若把二叉樹存儲到一維數(shù)組中樹存儲到一維數(shù)組中, ,則該編號就是下標值加則該編號就是下標值加1(1(注注意意,C/C+,C/C+語言中數(shù)組的起始下標為語言中數(shù)組的

39、起始下標為0)0)。樹中各結(jié)點的。樹中各結(jié)點的編號與等高度的完全二叉樹中對應位置上結(jié)點的編號編號與等高度的完全二叉樹中對應位置上結(jié)點的編號相同。相同。 利用利用(lyng)(lyng)二叉樹的性質(zhì)二叉樹的性質(zhì)4 4。第40頁/共115頁第四十一頁，共115頁。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉樹完全二叉樹 A B C D E F G H I J K123456789101112131415順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)(jigu)第41頁/共115頁第四十二頁，共115頁。7.3.2 7.3.2 二叉樹的鏈式存儲二叉樹的鏈式存儲(c

40、n ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu) 在二叉樹的鏈接存儲在二叉樹的鏈接存儲(cn ch)(cn ch)中中, ,結(jié)點的結(jié)構(gòu)如下結(jié)點的結(jié)構(gòu)如下: : typedef struct node typedef struct node ElemType data;ElemType data; struct node struct node * *lchild,lchild,* *rchild;rchild; BTNode; BTNode; 其中其中,data,data表示值域表示值域, ,用于存儲用于存儲(cn ch)(cn ch)對應的數(shù)對應的數(shù)據(jù)元素據(jù)元素,lchild,lchild和和rchildr

41、child分別表示左指針域和右指針域分別表示左指針域和右指針域, ,用用于分別存儲于分別存儲(cn ch)(cn ch)左孩子結(jié)點和右孩子結(jié)點左孩子結(jié)點和右孩子結(jié)點( (即左、右即左、右子樹的根結(jié)點子樹的根結(jié)點) )的存儲的存儲(cn ch)(cn ch)位置。位置。第42頁/共115頁第四十三頁，共115頁。 A B C E F D G A B C D E F G (a) (b) 二叉樹及其鏈式存儲二叉樹及其鏈式存儲(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu) 第43頁/共115頁第四十四頁，共115頁。7.4 7.4 二叉樹的遍歷二叉樹的遍歷(bin l)(bin l)7.4.1 7.4.1 二叉

42、樹遍歷二叉樹遍歷(bin l)(bin l)的概念的概念7.4.2 7.4.2 二叉樹遍歷二叉樹遍歷(bin l)(bin l)遞歸遞歸算法算法第44頁/共115頁第四十五頁，共115頁。7.4.1 7.4.1 二叉樹遍歷的概念二叉樹遍歷的概念 二叉樹的遍歷是指按照一定次序訪問樹中所二叉樹的遍歷是指按照一定次序訪問樹中所有結(jié)點有結(jié)點(ji din),(ji din),并且每個結(jié)點并且每個結(jié)點(ji din)(ji din)僅被訪問僅被訪問一次的過程。它是最基本的運算一次的過程。它是最基本的運算, ,是二叉樹中所有其他是二叉樹中所有其他運算的基礎。運算的基礎。第45頁/共115頁第四十六頁，共1

43、15頁。 1. 1. 先序遍歷先序遍歷先序遍歷二叉樹的過程是：先序遍歷二叉樹的過程是：(1)(1)訪問訪問(fngwn)(fngwn)根結(jié)點；根結(jié)點；(2)(2)先序遍歷左子樹；先序遍歷左子樹；(3)(3)先序遍歷右子樹。先序遍歷右子樹。2. 2. 中序遍歷中序遍歷中序遍歷二叉樹的過程是：中序遍歷二叉樹的過程是：(1)(1)中序遍歷左子樹；中序遍歷左子樹；(2)(2)訪問訪問(fngwn)(fngwn)根結(jié)點；根結(jié)點；(3)(3)中序遍歷右子樹。中序遍歷右子樹。第46頁/共115頁第四十七頁，共115頁。 3. 3. 后序遍歷后序遍歷后序遍歷二叉樹的過程后序遍歷二叉樹的過程(guchng)(g

44、uchng)是：是：(1)(1)后序遍歷左子樹；后序遍歷左子樹；(2)(2)后序遍歷右子樹；后序遍歷右子樹；(3)(3)訪問根結(jié)點。訪問根結(jié)點。第47頁/共115頁第四十八頁，共115頁。7.4.2 7.4.2 二叉樹遍歷遞歸算法二叉樹遍歷遞歸算法 由二叉樹的三種遍歷過程直接得到如下三種遞歸算由二叉樹的三種遍歷過程直接得到如下三種遞歸算法如下：法如下： void PreOrder(BTNode void PreOrder(BTNode * *b) b) / /* *先序遍歷的遞歸先序遍歷的遞歸算法算法* */ / if (b!=NULL) if (b!=NULL) printf(%c ,b-d

45、ata); / printf(%c ,b-data); /* *訪問訪問(fngwn)(fngwn)根結(jié)點根結(jié)點* */ / PreOrder(b-lchild); PreOrder(b-lchild); PreOrder(b-rchild); PreOrder(b-rchild); 第48頁/共115頁第四十九頁，共115頁。 void InOrder(BTNode *b) /*中序遍歷的遞歸算法中序遍歷的遞歸算法(sun f)*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ InOrder(b-rch

46、ild); 第49頁/共115頁第五十頁，共115頁。 void PostOrder(BTNode *b) /*后序后序(hu x)遍歷遞歸遍歷遞歸算法算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*訪問根結(jié)點訪問根結(jié)點*/ 第50頁/共115頁第五十一頁，共115頁。 例例7.2 假設二叉樹采用假設二叉樹采用(ciyng)二叉鏈存儲結(jié)構(gòu)存儲二叉鏈存儲結(jié)構(gòu)存儲,試試設計一個算法設計一個算法,輸出一棵給定二叉樹的所有葉子結(jié)點。輸出一棵給定二叉樹的所有葉子結(jié)點。 解：輸出一棵二叉樹的

47、所有葉子結(jié)點的遞歸模型解：輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b結(jié)點的結(jié)點的data域域 若若*b為葉子結(jié)點為葉子結(jié)點 f(b)：f(b-lchild);f(b-rchild) 其他情況其他情況第51頁/共115頁第五十二頁，共115頁。 void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf

48、(b-rchild); 第52頁/共115頁第五十三頁，共115頁。7.5 7.5 二叉樹的基本二叉樹的基本(jbn)(jbn)運算及其運算及其實現(xiàn)實現(xiàn)7.5.1 7.5.1 二叉樹的基本二叉樹的基本(jbn)(jbn)運算運算概述概述7.5.2 7.5.2 二叉樹的基本運算算法二叉樹的基本運算算法(sun (sun f)f)實現(xiàn)實現(xiàn)第53頁/共115頁第五十四頁，共115頁。7.5.1 7.5.1 二叉樹的基本運算概述二叉樹的基本運算概述 歸納起來歸納起來, ,二叉樹有以下基本運算：二叉樹有以下基本運算： (1) (1)創(chuàng)建二叉樹創(chuàng)建二叉樹CreateBTNode(CreateBTNode(

49、* *b,b,* *str)str)：根據(jù)：根據(jù)(gnj)(gnj)二叉樹括號表示法的字符串二叉樹括號表示法的字符串* *strstr生成對應的鏈生成對應的鏈式存儲結(jié)構(gòu)。式存儲結(jié)構(gòu)。 (2) (2)查找結(jié)點查找結(jié)點FindNode(FindNode(* *b,x)b,x)：在二叉樹：在二叉樹b b中尋中尋找找datadata域值為域值為x x的結(jié)點的結(jié)點, ,并返回指向該結(jié)點的指針。并返回指向該結(jié)點的指針。 ( 3 ) ( 3 ) 找 孩 子 結(jié) 點找 孩 子 結(jié) 點 L c h i l d N o d e ( p )L c h i l d N o d e ( p ) 和和RchildNode

50、(p)RchildNode(p)：分別求二叉樹中結(jié)點：分別求二叉樹中結(jié)點* *p p的左孩子結(jié)點的左孩子結(jié)點和右孩子結(jié)點。和右孩子結(jié)點。第54頁/共115頁第五十五頁，共115頁。 (4)求高度求高度BTNodeDepth(*b)：求二叉樹：求二叉樹b的的高度。若二叉樹為空高度。若二叉樹為空,則其高度為則其高度為0；否則；否則,其高度其高度等于左子樹與右子樹中的最大高度加等于左子樹與右子樹中的最大高度加l。 (5)輸出輸出(shch)二叉樹二叉樹DispBTNode(*b)：以括號表示法輸出以括號表示法輸出(shch)一棵二叉樹。一棵二叉樹。第55頁/共115頁第五十六頁，共115頁。7.5.

51、2 7.5.2 二叉樹的基本運算算法實現(xiàn)二叉樹的基本運算算法實現(xiàn) (1) (1)創(chuàng)建二叉樹創(chuàng)建二叉樹CreateBTNode(CreateBTNode(* *b,b,* *str)str) 用用chch掃描采用括號表示法表示二叉樹的字符串。掃描采用括號表示法表示二叉樹的字符串。分以下幾種情況：分以下幾種情況： 若若ch=(ch=(：則將前面剛創(chuàng)建的結(jié)點作為雙親：則將前面剛創(chuàng)建的結(jié)點作為雙親結(jié)點進棧結(jié)點進棧, ,并置并置(bn zh)k=1,(bn zh)k=1,表示其后創(chuàng)建的結(jié)點將作表示其后創(chuàng)建的結(jié)點將作為這個結(jié)點的左孩子結(jié)點；為這個結(jié)點的左孩子結(jié)點； 若若ch=)ch=)：表示棧中結(jié)點的左右

52、孩子結(jié)點處：表示棧中結(jié)點的左右孩子結(jié)點處理完畢理完畢, ,退棧；退棧； 若若ch=,ch=,：表示其后創(chuàng)建的結(jié)點為右孩子結(jié)：表示其后創(chuàng)建的結(jié)點為右孩子結(jié)點；點；第56頁/共115頁第五十七頁，共115頁。 其他情況其他情況, ,表示要創(chuàng)建一個結(jié)點表示要創(chuàng)建一個結(jié)點, ,并根并根據(jù)據(jù)k k值建立它與棧中結(jié)點之間的聯(lián)系值建立它與棧中結(jié)點之間的聯(lián)系, ,當當k=1k=1時時, ,表示這個結(jié)點作為表示這個結(jié)點作為(zuwi)(zuwi)棧中結(jié)點棧中結(jié)點的左孩子結(jié)點的左孩子結(jié)點, ,當當k=2k=2時時, ,表示這個結(jié)點作為表示這個結(jié)點作為(zuwi)(zuwi)棧中結(jié)點的右孩子結(jié)點。如此循棧中結(jié)點的右

53、孩子結(jié)點。如此循環(huán)直到環(huán)直到strstr處理完畢。算法中使用一個棧處理完畢。算法中使用一個棧StSt保存雙親結(jié)點保存雙親結(jié)點,top,top為其棧指針為其棧指針,k,k指定其后處指定其后處理的結(jié)點是雙親結(jié)點理的結(jié)點是雙親結(jié)點( (保存在棧中保存在棧中) )的左孩子的左孩子結(jié)點結(jié)點(k=1)(k=1)還是右孩子結(jié)點還是右孩子結(jié)點(k=2)(k=2)。第57頁/共115頁第五十八頁，共115頁。 void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=N

54、ULL; /*建立的二叉樹初始時為空建立的二叉樹初始時為空*/ ch=strj; while (ch!=0) /*str未掃描完時循環(huán)未掃描完時循環(huán)*/ switch(ch) case (:top+;Sttop=p;k=1; break; /*為左孩子為左孩子(hi zi)結(jié)點結(jié)點*/ case ):top-;break; case ,:k=2; break; /*為孩子為孩子(hi zi)結(jié)點右結(jié)點結(jié)點右結(jié)點*/第58頁/共115頁第五十九頁，共115頁。 d e f a u l t : p = ( B T N o d e *)malloc(sizeof(BTNode); p-data=ch

55、;p-lchild=p-rchild=NULL; if (b=NULL) /*p為二叉樹的根結(jié)點為二叉樹的根結(jié)點(ji din)*/ b=p; else /*已建立二叉樹根結(jié)點已建立二叉樹根結(jié)點(ji din)*/ switch(k) c a s e 1 : S t t o p -lchild=p;break; c a s e 2 : S t t o p -rchild=p;break; j+;ch=strj; 第59頁/共115頁第六十頁，共115頁。 例如例如, ,對于括號對于括號(kuho)(kuho)表示串表示串A(B(D(,G),C(E,F),A(B(D(,G),C(E,F),建立二

56、叉樹鏈式存儲結(jié)構(gòu)的過程如下表所示。建立二叉樹鏈式存儲結(jié)構(gòu)的過程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素A建立建立A結(jié)點結(jié)點,b指向該結(jié)點指向該結(jié)點空空(A結(jié)點進棧結(jié)點進棧,k=1AB建立建立B結(jié)點結(jié)點,因因k=1,將其作為將其作為A結(jié)點的左結(jié)點的左孩子結(jié)點孩子結(jié)點A(B結(jié)點進棧結(jié)點進棧,k=1ABD建立建立D結(jié)點結(jié)點,因因k=1,將其作為將其作為B結(jié)點的左結(jié)點的左孩子結(jié)點孩子結(jié)點AB第60頁/共115頁第六十一頁，共115頁。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素(D結(jié)點進棧結(jié)點進棧,k=1ABD,k=2ABDG建立建立E結(jié)點結(jié)點,因因k=2,將其作為將其作為D結(jié)

57、結(jié)點的右孩子結(jié)點點的右孩子結(jié)點ABD)退棧一次退棧一次AB)退棧一次退棧一次A,k=2AC建立建立C結(jié)點結(jié)點,因因k=2,將其作為將其作為A結(jié)結(jié)點的右孩子結(jié)點點的右孩子結(jié)點A(C結(jié)點進棧結(jié)點進棧,k=1ACE建立建立E結(jié)點結(jié)點,因因k=1,將其作為將其作為C結(jié)結(jié)點的左孩子結(jié)點點的左孩子結(jié)點AC,k=2AC第61頁/共115頁第六十二頁，共115頁。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素F建立建立F結(jié)點結(jié)點,因因k=2,將其作為將其作為C結(jié)點結(jié)點的右孩子結(jié)點的右孩子結(jié)點AC)退棧一次退棧一次A)退棧一次退棧一次空空ch掃描完畢掃描完畢算法結(jié)束算法結(jié)束 A B C D E F G 生成生

58、成(shn chn)的二叉樹的二叉樹第62頁/共115頁第六十三頁，共115頁。 (2)查找結(jié)點查找結(jié)點FindNode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的結(jié)點。找到后返回的結(jié)點。找到后返回(fnhu)其指針其指針,否則返回否則返回(fnhu)NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b,ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; else p=FindNode(b-lchild,x); if (p!=NU

59、LL) return p; else return FindNode(b-rchild,x); 第63頁/共115頁第六十四頁，共115頁。 (3)找孩子結(jié)點找孩子結(jié)點LchildNode(p)和和RchildNode(p) 直接直接(zhji)返回返回*p結(jié)點的左孩子結(jié)點或右孩子結(jié)點的指結(jié)點的左孩子結(jié)點或右孩子結(jié)點的指針。算法如下：針。算法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; 第64頁/共115頁第六十五頁，共115頁。(4)求高度求高

60、度BTNodeDepth(*b)求二叉樹的高度的遞歸模型求二叉樹的高度的遞歸模型(mxng)f()如下：如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情況其他情況對應的算法如下：對應的算法如下：第65頁/共115頁第六十六頁，共115頁。int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); /*空樹的高度空樹的高度(god)為為0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子樹的高度求左子樹的高度(god)為為lchilddep*/ rchild