數(shù)據(jù)結構C語言樹形結構學習教案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、個結點個結點(ji din)的的m次樹的高度為次樹的高度為h,若若在該樹中前在該樹中前h-1層都是滿的層都是滿的,即每一層的結點即每一層的結點(ji din)數(shù)都數(shù)都等于等于mi-1個個(1ih-1),第第h層層(即最后一層即最后一層)的結點的結點(ji din)數(shù)可能滿數(shù)可能滿,也可能不滿也可能不滿,則該樹具有最小的高度。其高度則該樹具有最小的高度。其高度h可可計算如下：計算如下：第15頁/共115頁第十六頁，共115頁。根據(jù)樹的性質根據(jù)樹的性質(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)結論得證。結論得證。111 mmh11 mmh第16頁/共115頁第十七頁，共115頁。 例例7.1 含含n個結點的三次樹的最小高度個結點的三次樹的最小高度(god)是多少？是多少？ 解：設含解：設含n個結點的個結點的(為完全三次樹時高度為完全三次樹時高度(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)分為三大類：分為三大類： 第一類第一類, ,尋找滿足某種特定關系的結點尋找滿足某種特定關系的結點, ,如尋找當如尋找當前結點的雙親結點等；前結點的雙親結點等； 第二類第二類, ,插入或刪除某個結點插入或刪除某個結點, ,如在樹的當前結點如在樹的當前結點上插入一個新結點或刪除當前結點的第上插入一個新結點或刪除當前結點的第i i個孩子結點個孩子結點等；等； 第三類第三類, ,遍歷樹中每個結點遍歷樹中每個

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

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

21、 , 同 時 在 每 個 結 點 中 附 設同 時 在 每 個 結 點 中 附 設(fsh)(fsh)一個偽指針指示其雙親結點的位置。一個偽指針指示其雙親結點的位置。 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)存儲結構示意圖存儲結構示意圖第21頁/共115頁第二十二頁，共115頁。2. 孩子孩子(hi zi)鏈存儲結構鏈存儲結構 孩子孩子(hi zi)鏈存儲結構可按樹的度鏈存儲結構可按樹的度(即樹中所有結點度即樹中所有結點度的最大值的最大值)設計結點的孩子

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

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

24、性質(xngzh)(xngzh)7.2.3 7.2.3 二叉樹與樹、森林之間的轉換二叉樹與樹、森林之間的轉換第24頁/共115頁第二十五頁，共115頁。7.2.1 7.2.1 二叉樹概念二叉樹概念 二叉樹也稱為二叉樹也稱為(chn wi)(chn wi)二次樹或二分樹二次樹或二分樹, ,它是有限它是有限的結點集合的結點集合, ,這個集合或者是空這個集合或者是空, ,或者由一個根結點和兩棵互或者由一個根結點和兩棵互不相交的稱為不相交的稱為(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 din)(ji din)都有左孩子結點都有左孩子結點(ji din)(ji din)和右孩子結點

26、和右孩子結點(ji (ji din),din),并且葉結點并且葉結點(ji din)(ji din)都集中在二叉樹的都集中在二叉樹的最下一層最下一層, ,這樣的二叉樹稱為滿二叉樹。下圖所示就這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫M二叉樹的結點是一棵滿二叉樹?？梢詫M二叉樹的結點(ji (ji din)din)進行連續(xù)編號進行連續(xù)編號, ,約定編號從樹根為約定編號從樹根為1 1開始開始, ,按照按照層數(shù)從小到大、同一層從左到右的次序進行。圖中每層數(shù)從小到大、同一層從左到右的次序進行。圖中每個結點個結點(ji din)(ji din)外邊的數(shù)字為對該結點外邊的數(shù)字為對該結點(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頁。 若二叉樹中最多只有最下面兩層的結點的度數(shù)可以若二叉樹中最多只有最下面兩層的結點的度數(shù)可以小于小于2,2,并且最下面一層的葉結點并且最下面一層的葉結點 都依次都依次(yc)(yc)排列排列在該層最左邊的位置上在該層最左邊的位置上, ,則這樣的二叉樹稱為完全二叉則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二樹。如下圖所示為一棵完全二

28、叉樹。同樣可以對完全二叉樹中每個結點進行連續(xù)編號叉樹中每個結點進行連續(xù)編號, ,編號的方法同滿二叉樹編號的方法同滿二叉樹相同。圖中每個結點外邊的數(shù)字為對該結點的編號。相同。圖中每個結點外邊的數(shù)字為對該結點的編號。 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 二叉樹性質二叉樹性質 性質性質1 1 非空二叉樹上葉結點數(shù)等于雙分支結點非空二叉樹上葉結點數(shù)等于雙分支結點數(shù)加數(shù)加1 1。 證明：設二叉樹上葉結點數(shù)為證明：設二叉樹上葉結點數(shù)為n0,n0,單分支結點單分支結

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

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

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

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

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

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

35、兄弟結點和相鄰的樹。般的樹的根結點不存在兄弟結點和相鄰的樹。第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)轉換為二叉樹的過程轉換為二叉樹的過程第36頁/共115頁第三十七頁，共115頁。2. 2. 二叉樹還原二叉樹還原(hun yun)(hun yun)為森林、樹為森林、樹 (1) (1)對于一棵二叉樹中任一結點對于一棵二叉樹中任一結點(ji din)k0,(ji din)k0,沿沿著著k1k1右孩子結點右孩子結點(ji din)(ji d

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

37、 (4) (4)將圖形規(guī)整化將圖形規(guī)整化, ,使各結點使各結點(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)結構結構 7.3.1 7.3.1 二叉樹的順序存儲結構二叉樹的順序存儲結構(jigu) (jigu) 7.3.2 7.3

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

39、起始下標為0)0)。樹中各結點的。樹中各結點的編號與等高度的完全二叉樹中對應位置上結點的編號編號與等高度的完全二叉樹中對應位置上結點的編號相同。相同。 利用利用(lyng)(lyng)二叉樹的性質二叉樹的性質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順序存儲結構順序存儲結構(jigu)第41頁/共115頁第四十二頁，共115頁。7.3.2 7.3.2 二叉樹的鏈式存儲二叉樹的鏈式存儲(c

40、n ch)(cn ch)結構結構 在二叉樹的鏈接存儲在二叉樹的鏈接存儲(cn ch)(cn ch)中中, ,結點的結構如下結點的結構如下: : 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)左孩子結點和右孩子結點左孩子結點和右孩子結點( (即左、右即左、右子樹的根結點子樹的根結點) )的存儲的存儲(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)結構結構 第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 din),(ji din),并且每個結點并且每個結點(ji din)(ji din)僅被訪問僅被訪問一次的過程。它是最基本的運算一次的過程。它是最基本的運算, ,是二叉樹中所有其他是二叉樹中所有其他運算的基礎。運算的基礎。第45頁/共115頁第四十六頁，共1

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

44、uchng)是：是：(1)(1)后序遍歷左子樹；后序遍歷左子樹；(2)(2)后序遍歷右子樹；后序遍歷右子樹；(3)(3)訪問根結點。訪問根結點。第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)根結點根結點* */ / 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); /*訪問根結點訪問根結點*/ 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); /*訪問根結點訪問根結點*/ 第50頁/共115頁第五十一頁，共115頁。 例例7.2 假設二叉樹采用假設二叉樹采用(ciyng)二叉鏈存儲結構存儲二叉鏈存儲結構存儲,試試設計一個算法設計一個算法,輸出一棵給定二叉樹的所有葉子結點。輸出一棵給定二叉樹的所有葉子結點。 解：輸出一棵二叉樹的

47、所有葉子結點的遞歸模型解：輸出一棵二叉樹的所有葉子結點的遞歸模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：輸出：輸出*b結點的結點的data域域 若若*b為葉子結點為葉子結點 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生成對應的鏈生成對應的鏈式存儲結構。式存儲結構。 (2) (2)查找結點查找結點FindNode(FindNode(* *b,x)b,x)：在二叉樹：在二叉樹b b中尋中尋找找datadata域值為域值為x x的結點的結點, ,并返回指向該結點的指針。并返回指向該結點的指針。 ( 3 ) ( 3 ) 找 孩 子 結 點找 孩 子 結 點 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)：分別求二叉樹中結點：分別求二叉樹中結點* *p p的左孩子結點的左孩子結點和右孩子結點。和右孩子結點。第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)建的結點作為雙親：則將前面剛創(chuàng)建的結點作為雙親結點進棧結點進棧, ,并置并置(bn zh)k=1,(bn zh)k=1,表示其后創(chuàng)建的結點將作表示其后創(chuàng)建的結點將作為這個結點的左孩子結點；為這個結點的左孩子結點； 若若ch=)ch=)：表示棧中結點的左右

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

53、孩子結點。如此循環(huán)直到環(huán)直到strstr處理完畢。算法中使用一個棧處理完畢。算法中使用一個棧StSt保存雙親結點保存雙親結點,top,top為其棧指針為其棧指針,k,k指定其后處指定其后處理的結點是雙親結點理的結點是雙親結點( (保存在棧中保存在棧中) )的左孩子的左孩子結點結點(k=1)(k=1)還是右孩子結點還是右孩子結點(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)結點結點*/ case ):top-;break; case ,:k=2; break; /*為孩子為孩子(hi zi)結點右結點結點右結點*/第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 din)*/ b=p; else /*已建立二叉樹根結點已建立二叉樹根結點(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、叉樹鏈式存儲結構的過程如下表所示。建立二叉樹鏈式存儲結構的過程如下表所示。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素A建立建立A結點結點,b指向該結點指向該結點空空(A結點進棧結點進棧,k=1AB建立建立B結點結點,因因k=1,將其作為將其作為A結點的左結點的左孩子結點孩子結點A(B結點進棧結點進棧,k=1ABD建立建立D結點結點,因因k=1,將其作為將其作為B結點的左結點的左孩子結點孩子結點AB第60頁/共115頁第六十一頁，共115頁。ch算法執(zhí)行的操作算法執(zhí)行的操作St中元素中元素(D結點進棧結點進棧,k=1ABD,k=2ABDG建立建立E結點結點,因因k=2,將其作為將其作為D結

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

58、成(shn chn)的二叉樹的二叉樹第62頁/共115頁第六十三頁，共115頁。 (2)查找結點查找結點FindNode(*b,x) 采用先序遍歷遞歸算法查找值為采用先序遍歷遞歸算法查找值為x的結點。找到后返回的結點。找到后返回(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)找孩子結點找孩子結點LchildNode(p)和和RchildNode(p) 直接直接(zhji)返回返回*p結點的左孩子結點或右孩子結點的指結點的左孩子結點或右孩子結點的指針。算法如下：針。算法如下： 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