計算機應用基礎1.4樹b

第第頁計算機應用基礎1.4樹b計算機應用基礎

第1章

數據結構1065

1.1基本數據結構與算法1.2線性表865

1.3棧和隊列

1.4樹和二叉樹1.5查找1.6內部排序姓名學號成果班級機97.6

李紅976105995

計算機應用基礎

1.4樹和二叉樹1.4.1樹的定義和基本術語1.4.2二叉樹

1.4.3遍歷二叉樹

計算機應用基礎

1.4樹與二叉樹1.4.1樹的定義和基本術語樹型結構是一類重要的非線性數據結構，元素結點間存在明顯的分支和層次關系?，F實世界中，能用樹的結構表示的例子：學校的行政關系、書的層次結構、人類的家族血緣關系等。A

T1E

BC

D

FG

H

I

J

K

L

T2

M

T3

計算機應用基礎

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

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

T1T2

T3

計算機應用基礎

1.4樹與二叉樹1.4.1樹的定義和基本術語1.樹的定義2.樹的基本概念(相關術語)1)根結點:沒有前驅的結點只有一個,稱為根結點。2)雙親(父)結點:樹中每個結點只有一個徑直前驅,稱為該結點的雙親結點或父結點。

3)孩子(子)結點：一個結點的子樹的根或者后繼結點數稱為該節(jié)點的孩子結點或子結點。

4)葉子結點(終端結點):沒有子結點(后繼)的結點。

計算機應用基礎

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

A:是根結點,同時是B、C、D結點的父結點或雙親結點DHLI

BEJKF

CG

B:是E、F的父結點，E、F是B的子結點或孩子結點J、K、L、F、G、I:是葉子結點

計算機應用基礎

1.4樹與二叉樹1.4.1樹的定義和基本術語1.樹的定義2.樹的基本概念(相關術語)5)兄弟：同一個雙親的孩子結點之間互稱兄弟。

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

計算機應用基礎

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

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

B,C,D互為兄弟

G與E、F、H、I互為堂兄弟結點

EJK

F

G

HL

I

L的祖先為A、D、H。

計算機應用基礎

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

:樹中結點的最大層次稱為樹的深度。

計算機應用基礎

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

結點A的層次：1結點L的層次：4結點的度:A的度為3;C的度為1F的度為0樹的度：3樹的深度：4

留意:一棵樹中,每個結點的度數之和=結點總數-1=樹中邊的條數

計算機應用基礎

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

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

計算機應用基礎

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義定義：二叉樹是n(n0)個結點的有限集，它或為空樹二叉樹的五種基本形態(tài)(n=0),或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。特點：每個結點至多有二棵子樹(即不存在度大于2的結點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒

空二叉樹

僅有根結點

右子樹為空

左子樹為空

左右子樹均非空

計算機應用基礎

1.4樹與二叉樹1.4.2二叉樹21.二叉樹的定義2.二叉樹的性質8

13

4910

51112

61314

715

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

計算機應用基礎

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質葉子結點：n0=3CEB

A

DF

度為2的結點：n2=2

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

計算機應用基礎

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質滿二叉樹

定義：假如一個二叉樹深度為K,結點數為2k-1,那么稱為滿二叉樹特點：除最末一層外，每一層全部結點都有兩個子結點。1滿二叉樹23

48

5

6

7

9101112131415

計算機應用基礎

1.4樹與二

叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質

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

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

274657非完全二叉樹

3

8910

計算機應用基礎

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

計算機應用基礎

1.4樹與二叉樹1.4.2二叉樹1.二叉樹的定義2.二叉樹的性質8491025

1367

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

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

計算機應用基礎

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

489

510

6

7

5.依據性質5,可知最末葉子結點為10,其父結點是5,且該結點5是最末一個非葉子結點,那么從結點6~10均為葉子結點。(10-6+1)

返回

計算機應用基礎

6.設一棵二叉樹中有3個葉子結點，有8個度為1的結點，那么該二叉樹中總的結點數是______。A.12B.13C.14D.157.下面關于完全二叉樹的表達中，錯誤的選項是______。A.除了最末一層外，每一層上結點數均達到最大值B.可能缺少假設干個左右葉子結點C.完全二叉數

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

返回

計算機應用基礎

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