2_4樹(shù)與二叉樹(shù)(4h)ppt課件

1、12.4.1 樹(shù)的基本概念樹(shù)的基本概念2.4.2 二叉樹(shù)及其基本性質(zhì)二叉樹(shù)及其基本性質(zhì)2.4.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2.4.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷2.4.5 二叉樹(shù)的應(yīng)用二叉樹(shù)的應(yīng)用2.4 2.4 樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)2內(nèi)容提要1.1.樹(shù)的定義樹(shù)的定義2.2.樹(shù)的基本概念樹(shù)的基本概念 結(jié)點(diǎn)、結(jié)點(diǎn)度、根、支、葉結(jié)點(diǎn) 子結(jié)點(diǎn)、父結(jié)點(diǎn)、兄弟結(jié)點(diǎn) 樹(shù)的度、路徑、長(zhǎng)度、深度 森林、有序、無(wú)序3內(nèi)容提要3.3.二叉樹(shù)二叉樹(shù) 二叉樹(shù)的定義二叉樹(shù)的定義 二叉樹(shù)的性質(zhì)（每層結(jié)點(diǎn)個(gè)數(shù)、總結(jié)點(diǎn)數(shù)）二叉樹(shù)的性質(zhì)（每層結(jié)點(diǎn)個(gè)數(shù)、總結(jié)點(diǎn)數(shù)） 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu): :順序存儲(chǔ)、記錄數(shù)組結(jié)構(gòu)

2、順序存儲(chǔ)、記錄數(shù)組結(jié)構(gòu)( (結(jié)點(diǎn)、左子、右子結(jié)點(diǎn)、左子、右子) )、鏈?zhǔn)酱鎯?chǔ)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表三叉鏈表）結(jié)構(gòu)（二叉鏈表三叉鏈表）4.4.特殊二叉樹(shù)特殊二叉樹(shù) 滿二叉樹(shù)（性質(zhì)）、完全二叉樹(shù)（性質(zhì)）、平衡二叉樹(shù)、滿二叉樹(shù)（性質(zhì)）、完全二叉樹(shù)（性質(zhì)）、平衡二叉樹(shù)、 二叉排序樹(shù)）二叉排序樹(shù)）5.5.二叉樹(shù)的遍歷操作（前序、中序、后序）二叉樹(shù)的遍歷操作（前序、中序、后序） 6.6.樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu): : 數(shù)組實(shí)現(xiàn)方法（雙親表示法）、鏈表實(shí)現(xiàn)方式（孩子表數(shù)組實(shí)現(xiàn)方法（雙親表示法）、鏈表實(shí)現(xiàn)方式（孩子表 示法）、二叉鏈表實(shí)現(xiàn)方式（孩子兄弟表示法）示法）、二叉鏈表實(shí)現(xiàn)方式（孩子兄弟表示法）7.7

3、.樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換42.4.1 樹(shù)的基本概念南京理工大學(xué)南京理工大學(xué)信息學(xué)院信息學(xué)院經(jīng)管院經(jīng)管院 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院自動(dòng)化學(xué)院自動(dòng)化學(xué)院210121022103張三張三李四李四王五王五理學(xué)院理學(xué)院樹(shù)形結(jié)構(gòu)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu)。在客觀世界中樹(shù)形結(jié)構(gòu)廣泛存在，并應(yīng)用于：n人類社會(huì)的族譜、家譜、行政 區(qū)域劃分管理；n各種社會(huì)組織機(jī)構(gòu)；n在計(jì)算機(jī)領(lǐng)域中，用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu)；n在OS中，文件系統(tǒng)、目錄等組織結(jié)構(gòu)也是用樹(shù)來(lái)表示的。567線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無(wú)前驅(qū)無(wú)前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無(wú)前驅(qū)無(wú)前驅(qū)) )最

4、后一個(gè)數(shù)最后一個(gè)數(shù)據(jù)元素?fù)?jù)元素( (無(wú)后繼無(wú)后繼) )多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無(wú)后繼無(wú)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )8一、樹(shù)的定義1（邏輯結(jié)構(gòu)）n樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)：Tree=（D，R）其中：D 是具有相同特性的n個(gè)數(shù)據(jù)元素的集合；R 是D上邏輯關(guān)系的集合，且滿足：n在D中存在唯一的稱為根的數(shù)據(jù)元素，沒(méi)有前件；nD中其余數(shù)據(jù)元素都有且只有一個(gè)前件；nD中所有元素，或有若干個(gè)互不相同的后件（子樹(shù)），或無(wú)后件（葉結(jié)點(diǎn)）； 則稱Tree為樹(shù)。9樹(shù)的定義2（遞歸結(jié)構(gòu)）n

5、樹(shù)是一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合T，有一個(gè)特定結(jié)點(diǎn)稱為根，其余結(jié)點(diǎn)分為m（m0）個(gè)互不相交的集合T1，T2，,Tm。每個(gè)集合又是一棵樹(shù)，被稱為這個(gè)根的子樹(shù)。n樹(shù)是一種遞歸結(jié)構(gòu)，可以包含一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)包含不相交的樹(shù)的指針（即子樹(shù)）。10二、樹(shù)的表示形式1. 1. 一般形式一般形式2. 2. 嵌套形式嵌套形式3. 3. 凹入形式凹入形式4. 4. 廣義表形式廣義表形式111. 一般形式 A(a)(a)只有根結(jié)點(diǎn)的樹(shù)只有根結(jié)點(diǎn)的樹(shù)ABCDEFKLGHIJM(b)(b)一般的樹(shù)一般的樹(shù)122. 嵌套形式 ACGBFEKLMHDJI13樹(shù)的表示(凹入形式)A B E KLCDFGHIJM14樹(shù)的表示(

6、廣義表形式)( A ( B ( E (K,L),F),C(G),D( H (M),I,J ) 第一層第一層第二層第二層第三層第三層第四層第四層15二、基本術(shù)語(yǔ)n結(jié)點(diǎn)：包括一個(gè)數(shù)據(jù)元素及若干個(gè)指向其它子樹(shù) 的分支；例如，A，B，C，D等。n葉結(jié)點(diǎn)：無(wú)后件結(jié)點(diǎn)為葉結(jié)點(diǎn)；如K，L，M。n根結(jié)點(diǎn)：無(wú)前件的結(jié)點(diǎn)為根；例如，A結(jié)點(diǎn)。n子結(jié)點(diǎn)：某結(jié)點(diǎn)后件為該結(jié)點(diǎn)的子結(jié)點(diǎn)；例如， 結(jié)點(diǎn)A的子結(jié)點(diǎn)為B，C，D。n父結(jié)點(diǎn)：某結(jié)點(diǎn)的前件稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)；例 如子結(jié)點(diǎn)C，B，D的父結(jié)點(diǎn)為A。16基本術(shù)語(yǔ)續(xù)n兄弟結(jié)點(diǎn)：同一父親的孩子之間互為兄弟結(jié)點(diǎn) （Sibling）；H，I，J互為兄弟。n路徑：結(jié)點(diǎn)的序列n1，n2

7、，,nk(K1)是一條路徑。n長(zhǎng)度：長(zhǎng)度等于路徑中結(jié)點(diǎn)數(shù)-1。n結(jié)點(diǎn)度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)數(shù)目；例如，A的度為3。n樹(shù)的度：樹(shù)中結(jié)點(diǎn)的最大度數(shù)；上述樹(shù)的度為3。n子樹(shù)：以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該 結(jié)點(diǎn)的一棵子樹(shù)。 17基本術(shù)語(yǔ)續(xù)n高度：從一結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑為該結(jié)點(diǎn)的高度；例如，結(jié)點(diǎn)A到M的高度為4。n深度：從根結(jié)點(diǎn)到某結(jié)點(diǎn)的路徑為該結(jié)點(diǎn)的深度； M的深度為4。n樹(shù)的深度：樹(shù)的最大層次稱為樹(shù)的深度。 n森林：0棵或多棵互不相交的樹(shù)的集合。對(duì)樹(shù)中每個(gè) 結(jié)點(diǎn)而言，其子樹(shù)的集合即為森林。n有序：如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有順序的（即不能互換），則稱該樹(shù)為有序樹(shù)。否則，稱為無(wú)序

8、樹(shù)。18例：用樹(shù)結(jié)構(gòu)來(lái)表示算術(shù)表達(dá)式 n用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則如下： n表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。n運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的順序?yàn)閺淖蟮接遥?。n運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。例如：a*（bcd）e*h-g*f（s，t，xy） 192.4.2 二叉樹(shù)及其基本性質(zhì)n定義一：二叉樹(shù)是另一種樹(shù)形結(jié)構(gòu)： Binary_Tree =( D,R) 其中：D 是具有相同性質(zhì)的數(shù)據(jù)元素的集合； R 是在D上某個(gè)兩元關(guān)系的集合，且滿足：nD中存在唯一稱為根的數(shù)據(jù)元素，沒(méi)有前件；中存在唯一稱為根的數(shù)據(jù)元素，沒(méi)有前件；nD中其余元素都有且僅有一個(gè)

9、前件；中其余元素都有且僅有一個(gè)前件；n每個(gè)結(jié)點(diǎn)至多只有兩個(gè)子樹(shù)；每個(gè)結(jié)點(diǎn)至多只有兩個(gè)子樹(shù)；nD中元素，或有兩個(gè)互不相交后件，或無(wú)后件；中元素，或有兩個(gè)互不相交后件，或無(wú)后件；n左、右子樹(shù)分別又是一棵二叉樹(shù)。左、右子樹(shù)分別又是一棵二叉樹(shù)。一、定義20定義二 n個(gè)結(jié)點(diǎn)的集合（個(gè)結(jié)點(diǎn)的集合（n 0） T 的度的度 2 所有子樹(shù)都有左、右之分所有子樹(shù)都有左、右之分 （次序不能任意顛到）（次序不能任意顛到）v 二叉樹(shù)不一定是樹(shù)二叉樹(shù)不一定是樹(shù)v 二叉樹(shù)可以為空；而樹(shù)則不能為空；二叉樹(shù)可以為空；而樹(shù)則不能為空；v 二叉樹(shù)的結(jié)點(diǎn)最多只有兩個(gè)直接后件二叉樹(shù)的結(jié)點(diǎn)最多只有兩個(gè)直接后件v 二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)分左子

10、樹(shù)和右子樹(shù)，而樹(shù)則無(wú)此區(qū)分。二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)分左子樹(shù)和右子樹(shù)，而樹(shù)則無(wú)此區(qū)分。v 二叉樹(shù)是有序樹(shù)二叉樹(shù)是有序樹(shù) 二叉樹(shù)的度二叉樹(shù)的度=21,則結(jié)點(diǎn)i父結(jié)點(diǎn)的編號(hào)為i/2(取整)。29（2）完全二叉樹(shù)特點(diǎn): 葉結(jié)點(diǎn)只可能出現(xiàn)在層次最大的兩層上.n深度為k的二叉樹(shù)T，每層結(jié)點(diǎn)數(shù)目若滿足：n第i層(1 i k-1)上的結(jié)點(diǎn)個(gè)數(shù)均為2i-1i-1;n第k層從右邊連續(xù)缺若干個(gè)結(jié)點(diǎn)(即只能從右至左不間斷缺少); 稱這樣的樹(shù)為完全二叉樹(shù)。OOOOOO（a） 完全二叉樹(shù)OOOOO（b） 非完全二叉樹(shù)30完全二叉樹(shù)的性質(zhì)n設(shè)完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為n，深度為k，某結(jié)點(diǎn)編號(hào)為i（1 i n ），則有：n若若i1,

11、i1,則結(jié)點(diǎn)則結(jié)點(diǎn)i i的雙親結(jié)點(diǎn)的編號(hào)為的雙親結(jié)點(diǎn)的編號(hào)為i/2;i/2;n若若2 2* * i i n, n,則結(jié)點(diǎn)則結(jié)點(diǎn)i i 的左子結(jié)點(diǎn)的編號(hào)為的左子結(jié)點(diǎn)的編號(hào)為2 2* * i, i,否則否則, ,結(jié)點(diǎn)結(jié)點(diǎn)i i為葉結(jié)點(diǎn)為葉結(jié)點(diǎn); ;n若若2 2* * i +1 i +1 n, n,則結(jié)點(diǎn)則結(jié)點(diǎn)i i 的右子結(jié)點(diǎn)的編號(hào)為的右子結(jié)點(diǎn)的編號(hào)為2 2* *i+1,i+1,否則否則, ,結(jié)點(diǎn)結(jié)點(diǎn)i i為葉結(jié)點(diǎn)為葉結(jié)點(diǎn). .n同理,完全二叉樹(shù)也可以采用一維樹(shù)組作為存儲(chǔ)結(jié)構(gòu),且方法完全同滿二叉樹(shù),只不過(guò)n 2k -1 罷了.ni i 父結(jié)點(diǎn)：父結(jié)點(diǎn)：int(I/2)int(I/2)，n左子結(jié)點(diǎn)：

12、2*i n，右子結(jié)點(diǎn)：2*i+1 n31（3）二叉排序樹(shù)定義一n二叉排序樹(shù)n或者是空二叉樹(shù)；或者是空二叉樹(shù)；n或者是：或者是：n左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；n右子樹(shù)上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；右子樹(shù)上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值；n左、右子樹(shù)本身又是一棵二叉排序樹(shù)。左、右子樹(shù)本身又是一棵二叉排序樹(shù)。 n最后一句話可否去掉？n區(qū)別與有序樹(shù)32二叉排序樹(shù)定義（二）nX是二叉排序樹(shù)T中的一個(gè)結(jié)點(diǎn)；n所有的左后裔小于X；n所有的右后裔大于等于X；nT可以為空樹(shù)；nT稱為二叉排序樹(shù)。104712141814（a）二叉排序/p>

13、137（b）非二叉排序樹(shù)332.4.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 一、順序存儲(chǔ)（一維數(shù)組）n用數(shù)組存放 存儲(chǔ)描述為： #define MAXSIZE 100； typedef TElemType SBTreeMAXSIZE； SBTree bt；n查找不便。a1 a2 a3 a4 . an34滿二叉樹(shù)存儲(chǔ)舉例1432476 1 2 3 4 4 6 71 2 3 4 4 6 7第第i i個(gè)結(jié)點(diǎn)就存放在第個(gè)結(jié)點(diǎn)就存放在第i i個(gè)位置上；個(gè)位置上；第第i i個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i1)i1)的父結(jié)點(diǎn)就存放在第的父結(jié)點(diǎn)就存放在第 i/2i/2個(gè)位置個(gè)位置; ;第第i i個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i i 2 2k-1k-1 -

14、 1)- 1)的左子結(jié)點(diǎn)就存放在第的左子結(jié)點(diǎn)就存放在第2 2* *i i的個(gè)位置的個(gè)位置; ;右子存放在第右子存放在第2 2* *i+1i+1位置位置. .35二、記錄數(shù)組結(jié)構(gòu)n存儲(chǔ)結(jié)構(gòu)描述: #define MAXSIZE 100; typedef struct SBNode TElemType data ; int Lchild,Rchild; SBNode; typedef structSBNode nodesMAXSIZE; SBTree;36舉例1 2 62 3 43 0 44 0 04 0 06 0 0結(jié)點(diǎn)結(jié)點(diǎn) 左子左子 右子右子126344特點(diǎn)特點(diǎn):找子方便找子方便,找父結(jié)點(diǎn)不找

15、父結(jié)點(diǎn)不便便.37三、二叉鏈表存儲(chǔ)結(jié)構(gòu)data leftprightp左指針左指針 數(shù)據(jù)數(shù)據(jù) 右指針右指針ABCDEFGABDCEFG特點(diǎn)特點(diǎn): 找子易找子易, 找父難找父難.38四、三叉鏈表存儲(chǔ)結(jié)構(gòu)左指針左指針 數(shù)據(jù)數(shù)據(jù) 父結(jié)點(diǎn)父結(jié)點(diǎn) 右指針右指針parent datarightpABCDEFGleftp特點(diǎn)特點(diǎn): 找子、找父都易。找子、找父都易。CABDEGF392.4.4 二叉樹(shù)的遍歷n遍歷（Traversing）是樹(shù)形結(jié)構(gòu)的一種重要運(yùn)算，即按一定的次序系統(tǒng)地訪問(wèn)結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。n遍歷的方法很多，常用的有：n前序法（前序法（PreOrder）n中序法（中序法（I

16、nOrder）n后序法（后序法（PostOrder）40一、前序法（PreOrder）n方法描述：n從根結(jié)點(diǎn)從根結(jié)點(diǎn)a開(kāi)始訪問(wèn)，開(kāi)始訪問(wèn)，n接著訪問(wèn)左子結(jié)點(diǎn)接著訪問(wèn)左子結(jié)點(diǎn)b，n最后訪問(wèn)右子結(jié)點(diǎn)最后訪問(wèn)右子結(jié)點(diǎn)c。n即：根根左子左子右子右子abcA 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)B 先序遍歷左子樹(shù)先序遍歷左子樹(shù)C 先序遍歷右子樹(shù)先序遍歷右子樹(shù)41二、中序法（InOrder）n方法描述：n從左子結(jié)點(diǎn)從左子結(jié)點(diǎn)b開(kāi)始訪問(wèn)，開(kāi)始訪問(wèn)，n接著訪問(wèn)根結(jié)點(diǎn)接著訪問(wèn)根結(jié)點(diǎn)a，n最后訪問(wèn)右子結(jié)點(diǎn)最后訪問(wèn)右子結(jié)點(diǎn)c。n即：根根左子左子右子右子abcA 中序遍歷左子樹(shù)中序遍歷左子樹(shù)B 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)C 中序遍歷右子樹(shù)

17、中序遍歷右子樹(shù)42三、后序法（PostOrder）n方法描述：n從左子結(jié)點(diǎn)從左子結(jié)點(diǎn)b開(kāi)始訪問(wèn)，開(kāi)始訪問(wèn)，n接著訪問(wèn)右子結(jié)點(diǎn)接著訪問(wèn)右子結(jié)點(diǎn)c，n最后訪問(wèn)根結(jié)點(diǎn)最后訪問(wèn)根結(jié)點(diǎn)a。n即：根根左子左子右子右子abcA 后序遍歷左子樹(shù)后序遍歷左子樹(shù)B 后序遍歷右子樹(shù)后序遍歷右子樹(shù)C 訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn)43二叉樹(shù)的遍歷舉例oooooooooABCDEFGHI前序遍歷序列：前序遍歷序列：中序遍歷序列：中序遍歷序列：后序遍歷序列：后序遍歷序列：A B D E G C F H ID B G E A C H F ID G E B H I F C A 44四、二叉樹(shù)遍歷算法 二叉鏈表描述 struct tno

18、de intdata； struct tnode *lchild， *rchild ； ； typedef struct tnode TNODE;定義結(jié)點(diǎn)數(shù)據(jù)類型定義結(jié)點(diǎn)數(shù)據(jù)類型45二叉樹(shù)遍歷算法 1.遞歸、前序法程序n頭指針為頭指針為BT的二叉樹(shù)的前序遍歷。的二叉樹(shù)的前序遍歷。PROCEDURE PRETRAV(BT)IF(BT0) THENOUTPUT(V(BT);PRETRAV(L(BT);PRETRAV(R(BT)RETURN前序遍歷二叉樹(shù)的序列為：前序遍歷二叉樹(shù)的序列為： A B C D E FABCDEF46二叉樹(shù)遍歷算法 1.遞歸、前序法程序void preorder_t (TN

19、ODE *root) if ( root != NULL ) printf(“%d n”,root-data); if (root-lc!=NULL) preorder_t(root-lc); if (root-rc!=NULL) preorder_t(root-rc); 前序遍歷二叉樹(shù)的序列為：前序遍歷二叉樹(shù)的序列為： A B C D E FABCDEF47二叉樹(shù)二叉樹(shù)遍遍歷算法（遞歸、前序法程序驗(yàn)證）歷算法（遞歸、前序法程序驗(yàn)證）n打印打印A An取取A A . .左子左子(B)(B)n打印打印B Bn取取B B . .左子左子(C)(C)n打印打印C Cn取取C C . .左子左子( (

20、空空) )n取取C C . .右子右子( (空空) ) n取取B B . .右子右子(D)(D)n打印打印D Dn取取D D . .左子左子(E)(E)n打印打印E En取取E E . .左子左子( (空空) )n取取E E . .右子右子( (空空) )n取取D D . .右子右子(F)(F)n打印打印F Fn取取F F . .左子左子( (空空) )n取取F F . .右子右子( (空空) )n取取A A . .右子右子( (空空) )n結(jié)束結(jié)束A AB BC CD DE EF FABCDEF482.非遞歸算法-前序法n算法步驟算法步驟: :nstep1 step1 初始化初始化, ,置棧

21、為空置棧為空(top=-1),(top=-1), 工作變量工作變量p p指向指向root;root;nstep2 pstep2 p非空非空(p!=NULL)(p!=NULL) 或棧非空或棧非空(top!=-1)(top!=-1)循環(huán)循環(huán); ;nstep3 pstep3 p非空循環(huán)非空循環(huán); ; 訪問(wèn)訪問(wèn)p(p(打印打印p-data);p-data);nstep4 step4 當(dāng)前元素進(jìn)棧當(dāng)前元素進(jìn)棧,p,p取取p-lc(p-lc(進(jìn)左子樹(shù)進(jìn)左子樹(shù));); 執(zhí)行執(zhí)行step3step3；nstep4 pstep4 p為空，棧非空，則出棧，為空，棧非空，則出棧， p p取取p-rcp-rc（進(jìn)右子

22、樹(shù)）（進(jìn)右子樹(shù)）, ,返回返回step2.step2.49#define N mvoid preorder_t(TNODE * root) TNODE *p, *stackN; int top=-1; p=root; while (p!= NULL)|(top!= -1) while ( p!=NULL) printf(“%dn”,p-data);/訪問(wèn)節(jié)點(diǎn)訪問(wèn)節(jié)點(diǎn) top +; stacktop=p; /進(jìn)棧進(jìn)棧 p=p-lc; /進(jìn)左子樹(shù)進(jìn)左子樹(shù) if ( top !=-1) p=stacktop; top - - ; /出棧出棧 p=p-rc;/進(jìn)右子樹(shù)進(jìn)右子樹(shù) ABCDEF50二叉樹(shù)二

23、叉樹(shù)遍遍歷算法（非遞歸、前序法程序驗(yàn)證）歷算法（非遞歸、前序法程序驗(yàn)證）n打印打印A AnA A進(jìn)棧，取進(jìn)棧，取A A . .左子左子( B )( B )n打印打印B BnB B進(jìn)棧，取進(jìn)棧，取B B . .左子左子( C )( C )n打印打印 C CnC C 進(jìn)棧，進(jìn)棧， 取取C C . .左子左子( ( 空空 ) )nC C 退棧，退棧， 取取C C . .右子右子( ( 空空 ) )nB B 退棧，退棧， 取取 B B . .右子右子( D )( D )n打印打印 D D nD D進(jìn)棧，取進(jìn)棧，取D D . .左子左子( E )( E )n打印打印E EnE E進(jìn)棧，取進(jìn)棧，取E E

24、. .左子左子( ( 空空 ) )nE E退棧，退棧， 取取E E . .右子右子( ( 空空) )nD D退退棧，取棧，取D D . .右子右子( F )( F )n打印打印F FnF F進(jìn)棧，取進(jìn)棧，取F F . .左子左子( ( 空空 ) )nF F退棧，退棧， 取取F F . .右子右子( ( 空空) )nA A退退棧，取棧，取A A . .右子右子( ( 空空 ) )n結(jié)束結(jié)束FEDCBAABCDEF51 2.5.5樹(shù)的應(yīng)用一、表達(dá)式樹(shù)n在計(jì)算機(jī)中對(duì)表達(dá)式進(jìn)行分析和計(jì)算是一項(xiàng)重要的任務(wù)；在計(jì)算機(jī)中對(duì)表達(dá)式進(jìn)行分析和計(jì)算是一項(xiàng)重要的任務(wù)；n表達(dá)式可以用有序樹(shù)表示；表達(dá)式可以用有序樹(shù)表示

25、；n樹(shù)處理不方便，可以轉(zhuǎn)化為二叉樹(shù)處理；樹(shù)處理不方便，可以轉(zhuǎn)化為二叉樹(shù)處理；n轉(zhuǎn)化原則：轉(zhuǎn)化原則：n有序樹(shù)有序樹(shù)T的結(jié)點(diǎn)與二叉樹(shù)的結(jié)點(diǎn)與二叉樹(shù)BT的結(jié)點(diǎn)一一對(duì)應(yīng)；的結(jié)點(diǎn)一一對(duì)應(yīng)；n有序樹(shù)有序樹(shù)T中某個(gè)結(jié)點(diǎn)中某個(gè)結(jié)點(diǎn)N的第一個(gè)子結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)N1,在二叉樹(shù)在二叉樹(shù)BT中為對(duì)應(yīng)結(jié)點(diǎn)中為對(duì)應(yīng)結(jié)點(diǎn)N的的左子結(jié)點(diǎn)；左子結(jié)點(diǎn)；n其他子結(jié)點(diǎn)，在二叉樹(shù)其他子結(jié)點(diǎn)，在二叉樹(shù)BT中被依次鏈接成一串起始于中被依次鏈接成一串起始于N1的右子結(jié)點(diǎn)。的右子結(jié)點(diǎn)。52表達(dá)式線性化n將表達(dá)式用有序樹(shù)表示；n將表達(dá)式樹(shù)轉(zhuǎn)化為二叉樹(shù)；n對(duì)對(duì)應(yīng)的二叉樹(shù)進(jìn)行中序遍歷，其遍歷序列即為表達(dá)式的波蘭表達(dá)式；n前序遍歷為波蘭表達(dá)式。53

26、表達(dá)式處理規(guī)則表達(dá)式處理規(guī)則分析：分析：每個(gè)葉結(jié)點(diǎn)為運(yùn)算對(duì)象；每個(gè)葉結(jié)點(diǎn)為運(yùn)算對(duì)象；每個(gè)非葉結(jié)點(diǎn)為運(yùn)算符；每個(gè)非葉結(jié)點(diǎn)為運(yùn)算符；每個(gè)子樹(shù)對(duì)應(yīng)一個(gè)子表達(dá)式。每個(gè)子樹(shù)對(duì)應(yīng)一個(gè)子表達(dá)式。見(jiàn)運(yùn)算數(shù)入棧見(jiàn)運(yùn)算數(shù)入棧見(jiàn)運(yùn)算符，取兩個(gè)棧頂元素運(yùn)算后再壓棧；見(jiàn)運(yùn)算符，取兩個(gè)棧頂元素運(yùn)算后再壓棧；直到處理結(jié)束。直到處理結(jié)束。54表達(dá)式樹(shù)應(yīng)用舉例（6）遇）遇-，a+b*（c-d） 和和e/f出棧，運(yùn)算后再壓棧出棧，運(yùn)算后再壓棧。（6）a+b*（c-d）- e/f（2） c - d b a（2）遇）遇-，c d 出棧，出棧， 運(yùn)算后再壓棧；運(yùn)算后再壓棧；（3） b*（c-d） a（3）遇）遇*，（，（c - d）和

27、）和 b 出棧，出棧， 運(yùn)算后再壓棧；運(yùn)算后再壓棧；（5）e/fa+b*（c-d）（5）遇）遇/，f e 出棧，出棧， 運(yùn)算后再壓棧；運(yùn)算后再壓棧；（1）（1） a b c d 入棧入棧dcbaa+b*（c-d）（4）（4）（4）遇）遇+，b*（c-d）和）和a出棧，出棧， 運(yùn)算后再壓棧運(yùn)算后再壓棧；a+b*（c-d）fe55二、Huffman(哈夫曼）樹(shù)（1）Huffman樹(shù)的定義（2）構(gòu)造Huffman樹(shù)（3）Huffman編碼（4）Huffman編碼的譯碼561. Huffman樹(shù)的定義nHuffman樹(shù)也稱為最優(yōu)樹(shù)，是一類帶權(quán)路徑最短的二叉樹(shù)。n樹(shù)的帶權(quán)路徑長(zhǎng)度定義為： WPL = w

28、kLkk = 1n 其中：其中： n 是樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù) wi 是第是第i個(gè)結(jié)點(diǎn)的權(quán)值個(gè)結(jié)點(diǎn)的權(quán)值 Li 是第是第i個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度 57Huffman樹(shù)舉例n以下有三棵樹(shù)：（a）abcd7424WPLa =7x2+4x2+2x2+4x2 = 34（b）acbd7424WPLb =7x3+4x3+2x1+4x2 = 43（c）abcd7424 WPLc = 7x1+4x2+2x3+4x3 = 33 l事實(shí)證明按哈夫曼樹(shù)構(gòu)造二叉樹(shù)，可得到很好的特性，應(yīng)用于實(shí)際問(wèn)題，事實(shí)證明按哈夫曼樹(shù)構(gòu)造二叉樹(shù)，可得到很好的特性，應(yīng)用于實(shí)際問(wèn)題，可提高處理效率?？商岣咛幚硇省?

29、8應(yīng)用舉例n由統(tǒng)計(jì)規(guī)律可知，考試成績(jī)的分布符合正態(tài)分布：-1 1 0 分?jǐn)?shù)分?jǐn)?shù) 059 60 69 70 79 80 89 90 100比例數(shù)比例數(shù) 0.06 0.14 0.40 0.30 0.10 l根據(jù)正態(tài)分布規(guī)律，在根據(jù)正態(tài)分布規(guī)律，在60 89分之間的同學(xué)占分之間的同學(xué)占84%，而不及格和優(yōu)，而不及格和優(yōu)秀成績(jī)的同學(xué)是少數(shù)。秀成績(jī)的同學(xué)是少數(shù)。59將百分制轉(zhuǎn)換成五分制n判定樹(shù)比較：a60?a70?a80?a90?不及格 及及格格 中等 良良好好 優(yōu)優(yōu)秀秀YYYYNNNN不及格不及格 中中等等(A)a80?a70?a90?a60? 優(yōu)優(yōu)秀秀 良良好好 中中等等 及及格格不及格不及格YYY

30、NNNNYY(B)l若輸入若輸入1 1萬(wàn)個(gè)數(shù)據(jù)，按萬(wàn)個(gè)數(shù)據(jù)，按A A的判定過(guò)程進(jìn)行操作，約需比較的判定過(guò)程進(jìn)行操作，約需比較3.23.2萬(wàn)次，而萬(wàn)次，而按按B B比較比較, ,則僅需則僅需2.22.2萬(wàn)次。萬(wàn)次。602. 構(gòu)造Huffman樹(shù)構(gòu)造構(gòu)造Huffman樹(shù)算法步驟：樹(shù)算法步驟：1）將）將n個(gè)帶權(quán)值個(gè)帶權(quán)值wi（in）的結(jié)點(diǎn)構(gòu)成）的結(jié)點(diǎn)構(gòu)成n棵二叉樹(shù)的集合棵二叉樹(shù)的集合T=T1，T2，Tn，每棵二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。每棵二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。2）在）在T中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹(shù)，構(gòu)成一個(gè)新的二叉樹(shù)，其根中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹(shù)，構(gòu)成一個(gè)新的二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值

31、取左右子樹(shù)權(quán)值之和；結(jié)點(diǎn)的權(quán)值取左右子樹(shù)權(quán)值之和；3）在）在T中刪除這兩棵樹(shù)，將新構(gòu)成的樹(shù)加入到中刪除這兩棵樹(shù)，將新構(gòu)成的樹(shù)加入到T中；中；4）重復(fù)）重復(fù)2）、）、3）步的操作，直到）步的操作，直到T中只含一棵樹(shù)為止，該樹(shù)就是中只含一棵樹(shù)為止，該樹(shù)就是Huffman樹(shù)。樹(shù)。61構(gòu)造Huffman樹(shù)舉例n以權(quán)值分別為7，4，2，4的結(jié)點(diǎn)a、b、c、d構(gòu)造Huffman樹(shù)。T= a b c d cdT3246bT3T26410bT26410cd2417aT2710T1617a7T1bT3T241017a7T1b410cd264（d）T= T1 （c）T= a T2 （b）T= a b T3 （a）

32、T= a b c d 代入代入T2代入代入T3代入代入T1623. Huffman編碼n編碼：用二進(jìn)制數(shù)的不同組合來(lái)表示字符的方法。n前綴編碼：一種非等長(zhǎng)度的編碼(任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴)。 a0b01cd011編碼：編碼：A（0） B（10） C（110） D（111）方法約定：方法約定：1）左分支為）左分支為02）右分支為）右分支為13）由葉到根路徑上字符組成的）由葉到根路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼。二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼。nHuffman編碼：一種非等長(zhǎng)度的編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造Huffman樹(shù)，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為Huffman編碼。63Huffman編碼舉例n在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn)在某系統(tǒng)