計(jì)算機(jī)應(yīng)用基礎(chǔ)1.4樹b

第第頁計(jì)算機(jī)應(yīng)用基礎(chǔ)1.4樹b計(jì)算機(jī)應(yīng)用基礎(chǔ)

第1章

數(shù)據(jù)結(jié)構(gòu)1065

1.1基本數(shù)據(jù)結(jié)構(gòu)與算法1.2線性表865

1.3棧和隊(duì)列

1.4樹和二叉樹1.5查找1.6內(nèi)部排序姓名學(xué)號(hào)成果班級(jí)機(jī)97.6

李紅976105995

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹和二叉樹1.4.1樹的定義和基本術(shù)語1.4.2二叉樹

1.4.3遍歷二叉樹

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，元素結(jié)點(diǎn)間存在明顯的分支和層次關(guān)系。現(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。A

T1E

BC

D

FG

H

I

J

K

L

T2

M

T3

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義概念：樹是n(n≥0)個(gè)結(jié)點(diǎn)構(gòu)成的有限集合。n=0為空樹；n≠0時(shí)，樹中結(jié)點(diǎn)應(yīng)當(dāng)滿意兩個(gè)條件(1)有且僅有一個(gè)特定的根的結(jié)點(diǎn)。(2)其余的n-1個(gè)結(jié)點(diǎn)可劃分為m(m0)個(gè)互不相交的有限集T1,T2,…,Tm,其中Ti又是一棵樹，稱為根的子樹。

示意圖：T1={B,E,F,J,K}T2={C,G}T3={D,H,I,L}

T1T2

T3

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)1)根結(jié)點(diǎn):沒有前驅(qū)的結(jié)點(diǎn)只有一個(gè),稱為根結(jié)點(diǎn)。2)雙親(父)結(jié)點(diǎn):樹中每個(gè)結(jié)點(diǎn)只有一個(gè)徑直前驅(qū),稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)或父結(jié)點(diǎn)。

3)孩子(子)結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根或者后繼結(jié)點(diǎn)數(shù)稱為該節(jié)點(diǎn)的孩子結(jié)點(diǎn)或子結(jié)點(diǎn)。

4)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn)):沒有子結(jié)點(diǎn)(后繼)的結(jié)點(diǎn)。

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)A

A:是根結(jié)點(diǎn),同時(shí)是B、C、D結(jié)點(diǎn)的父結(jié)點(diǎn)或雙親結(jié)點(diǎn)DHLI

BEJKF

CG

B:是E、F的父結(jié)點(diǎn)，E、F是B的子結(jié)點(diǎn)或孩子結(jié)點(diǎn)J、K、L、F、G、I:是葉子結(jié)點(diǎn)

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)5)兄弟：同一個(gè)雙親的孩子結(jié)點(diǎn)之間互稱兄弟。

6)堂兄弟：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。7)結(jié)點(diǎn)的祖先：結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支的全部結(jié)點(diǎn)。8)結(jié)點(diǎn)的子孫：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)

B的子孫為E、F、J、K。ABCD

B,C,D互為兄弟

G與E、F、H、I互為堂兄弟結(jié)點(diǎn)

EJK

F

G

HL

I

L的祖先為A、D、H。

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)9)結(jié)點(diǎn)的層次：從根開始定義起，根為第一層，根的孩子為第二層。假設(shè)某結(jié)點(diǎn)在第k層，那么其子樹的根就在第k+1層。10)結(jié)點(diǎn)的度:一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)(擁有后繼的個(gè)數(shù))。11)樹的度:全部結(jié)點(diǎn)度的最大值。12)樹的深度或高度

:樹中結(jié)點(diǎn)的最大層次稱為樹的深度。

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)ABEJKFCGHLDI

結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)L的層次：4結(jié)點(diǎn)的度:A的度為3;C的度為1F的度為0樹的度：3樹的深度：4

留意:一棵樹中,每個(gè)結(jié)點(diǎn)的度數(shù)之和=結(jié)點(diǎn)總數(shù)-1=樹中邊的條數(shù)

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.1樹的定義和基本術(shù)語1.樹的定義2.樹的基本概念(相關(guān)術(shù)語)

13)有序樹：假如將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的(即不能互換),那么稱該樹為有序樹。否那么為無序樹。在有序樹的最左邊的根稱為第一個(gè)孩子，最右邊的稱為最末一個(gè)孩子。14)森林：是m(m≥0)棵互不相交的樹的集合。對(duì)樹中根結(jié)點(diǎn)而言，其子樹的集合即為森林。由此，可用森林和樹相互遞歸的定義來描述樹。由于樹的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹的處理算法很繁復(fù)，所以引出二叉樹的爭(zhēng)論。返回

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛涠鏄涞奈宸N基本形態(tài)(n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒

空二叉樹

僅有根結(jié)點(diǎn)

右子樹為空

左子樹為空

左右子樹均非空

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹21.二叉樹的定義2.二叉樹的性質(zhì)8

13

4910

51112

61314

715

性質(zhì)1:二叉樹的第i層上至多有2i-1(i1)個(gè)結(jié)點(diǎn)。證明：依據(jù)二叉樹的特點(diǎn)，結(jié)論是顯著的。(用歸納法證明)。性質(zhì)2:深度為k的二叉樹中至多2k-1個(gè)結(jié)點(diǎn)。證明：深度為k的二叉樹最多有k層，依據(jù)性質(zhì)1,只要將第1層到第k層的最大結(jié)點(diǎn)數(shù)相加，就可得到整個(gè)二叉樹中結(jié)點(diǎn)的最大值。21-1+22-1+……+2k-1=2k-1(k1)

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質(zhì)葉子結(jié)點(diǎn)：n0=3CEB

A

DF

度為2的結(jié)點(diǎn)：n2=2

性質(zhì)3:對(duì)任何一棵二叉樹T,假如其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,那么n0=n2+1。證明：(1)結(jié)點(diǎn)總數(shù)n=n0+n1+n2(n1是度為1的結(jié)點(diǎn)數(shù))(2)由樹的性質(zhì)：n=B+1,有：n=n1+2*n2+1由(1)、(2)合并，可推出：最末得:n0=n2+1度為0的結(jié)點(diǎn)沒有下連的邊，度為1的結(jié)點(diǎn)下連的邊為1,度為2的結(jié)點(diǎn)下連的邊為2

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質(zhì)滿二叉樹

定義：假如一個(gè)二叉樹深度為K,結(jié)點(diǎn)數(shù)為2k-1,那么稱為滿二叉樹特點(diǎn)：除最末一層外，每一層全部結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。1滿二叉樹23

48

5

6

7

9101112131415

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二

叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質(zhì)

留意:滿二叉樹必是完全二叉樹；而完全二叉樹未必是滿二叉樹。

完全二叉樹定義:指深度為k的，有n個(gè)結(jié)點(diǎn)的，且每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。特點(diǎn):葉子結(jié)點(diǎn)只可能在最下面兩層上,且最下層葉子結(jié)點(diǎn)集中在樹的左部。任一結(jié)點(diǎn),右分支下子孫結(jié)點(diǎn)最大層次為h,那么左分支必為h或h+1。1124563

274657非完全二叉樹

3

8910

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質(zhì)性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為[log2n]+11證明：依據(jù)完全二叉樹的定義和性質(zhì)2可知，當(dāng)一棵完全1二叉樹的深度為k,結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，第k層最少有1個(gè)結(jié)232點(diǎn)，最多為滿，故有342k-1-1+1≤n≤2k-15674即2k-1≤n2k對(duì)不等式取對(duì)數(shù)，有深度為3的完全二叉樹結(jié)點(diǎn)深度為3的完全二叉樹結(jié)點(diǎn)數(shù)k-1≤log2k-1最少狀況是4,即2nk-1=3個(gè)數(shù)最多狀況是2k-1=7個(gè)由于k是整數(shù)，所以有k=[log2n]+1?！咀ⅲ捍颂庍\(yùn)算，為向下取整運(yùn)算】

計(jì)算機(jī)應(yīng)用基礎(chǔ)

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質(zhì)8491025

1367

性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹，從上至下和從左到右作用：很簡(jiǎn)單確定每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子和右子結(jié)點(diǎn)的位置。的順次對(duì)全部結(jié)點(diǎn)從1開始順次編號(hào)，那么對(duì)任意結(jié)點(diǎn)i有:1)i=1,該結(jié)點(diǎn)是根結(jié)點(diǎn)。否那么(i1),其雙親結(jié)點(diǎn)序號(hào)為i/2。2)假如2i≤n,其左孩子結(jié)點(diǎn)的序號(hào)為2i。如2、3、4、5結(jié)點(diǎn))假如2in,那么i結(jié)點(diǎn)，無左子結(jié)點(diǎn),顯著也沒右結(jié)點(diǎn)。

(如圖中6、7結(jié)點(diǎn))3)假如2i+1≤n,那么序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i+1(如2、3、4的右結(jié)點(diǎn)分別為5,7,9);假如2i+1n,那么序號(hào)為i的結(jié)點(diǎn)無右孩子結(jié)點(diǎn)。(如5、6、7)

計(jì)算機(jī)應(yīng)用基礎(chǔ)

練習(xí)1.在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多是______。A.4B.8C.32D.122.在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為______。A.32B.31C.16D.153.在深度為5的二叉樹中，至多有______個(gè)結(jié)點(diǎn)。A.32B.31C.16D.154.在具有10個(gè)結(jié)點(diǎn)的樹中，其邊的樹目為______。A.11B.10C.8D.95.設(shè)一棵完全二叉樹共有10個(gè)結(jié)點(diǎn)，那么在該二叉樹中的葉1子結(jié)點(diǎn)數(shù)為______。A.9B.5C.2D.423解答：BCBDB

489

510

6

7

5.依據(jù)性質(zhì)5,可知最末葉子結(jié)點(diǎn)為10,其父結(jié)點(diǎn)是5,且該結(jié)點(diǎn)5是最末一個(gè)非葉子結(jié)點(diǎn),那么從結(jié)點(diǎn)6~10均為葉子結(jié)點(diǎn)。(10-6+1)

返回

計(jì)算機(jī)應(yīng)用基礎(chǔ)

6.設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，那么該二叉樹中總的結(jié)點(diǎn)數(shù)是______。A.12B.13C.14D.157.下面關(guān)于完全二叉樹的表達(dá)中，錯(cuò)誤的選項(xiàng)是______。A.除了最末一層外，每一層上結(jié)點(diǎn)數(shù)均達(dá)到最大值B.可能缺少假設(shè)干個(gè)左右葉子結(jié)點(diǎn)C.完全二叉數(shù)

一般不是滿二叉數(shù)D.具有結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1解答：BB6.=n0+n1+n2=3+8+(3-1)(性質(zhì)3:n0=n2+1)

返回

計(jì)算機(jī)應(yīng)用基礎(chǔ)

8.在深度為7的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為___。(06.4月)A)32B)31C)64D)639.設(shè)樹T的度