[計(jì)算機(jī)軟件及應(yīng)用]棧的應(yīng)用和串圖(編輯修改稿)
2024-11-12 23:17 本頁面
【文章內(nèi)容簡(jiǎn)介】 (0,1,0,1,0,0,0,1,1) D． (0,1,0,1,0,1,0,1,1 ) A C A 樹的定義和基本術(shù)語 二叉樹 樹 樹的定義和基本運(yùn)算 1. 定義 樹是一種常用的非線性結(jié)構(gòu)。我們可以這樣定義：樹是 n（ n≥0）個(gè)結(jié)點(diǎn)的有限集合。若 n=0，則稱為空樹；否則，有且僅有一個(gè)特定的結(jié)點(diǎn)被稱為根，當(dāng) n1時(shí)，其余結(jié)點(diǎn)被分成 m（ m0）個(gè)互不相交的子集 T1， T2， ...， Tm，每個(gè)子集又是一棵樹。 由此可以看出，樹的定義是遞歸。 樹還有其他的表示形式 :： 1以嵌套集合的形式表示； 2以廣義表的形式表示； 3 以凹入法表示（類似書的編目） K L M E F G H I J B C D A A ? (a) (b) (c) 基本術(shù)語 結(jié)點(diǎn)： 包含一個(gè)數(shù)據(jù)元素及若干指向其子樹根的分支。 結(jié)點(diǎn)的度 ：結(jié)點(diǎn)擁有的子樹數(shù)，即結(jié)點(diǎn)的分支數(shù)。 終端結(jié)點(diǎn)（葉子）： 度為 0的結(jié)點(diǎn)。 非終端結(jié)點(diǎn) ： 度不為 0的結(jié)點(diǎn)。 結(jié)點(diǎn)的層次 ： 樹中根結(jié)點(diǎn)的層次為 1，根結(jié)點(diǎn)子樹的根為第 2層，以此類推。 樹的度： 樹中所有結(jié)點(diǎn)度的最大值。 樹的深度： 樹中結(jié)點(diǎn)的最大層次。 有序樹、無序樹 ： 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。 森林： 是 m（ m≥0）棵互不相交的樹的集合。 在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系又可以用家族關(guān)系描述，定義如下： 孩子、雙親 ： 結(jié)點(diǎn)子樹的根稱為這個(gè)結(jié)點(diǎn)的孩子，而這個(gè)結(jié)點(diǎn)又被稱為孩子的雙親。 子孫 ： 以某結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)都被稱為是該結(jié)點(diǎn)的子孫。 祖先 ： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。 兄弟 ： 同一個(gè)雙親的孩子之間互為兄弟。 堂兄弟 ： 雙親在同一層的結(jié)點(diǎn)互為堂兄弟。 問題 1：圖中結(jié)點(diǎn)個(gè)數(shù)和分支之間的關(guān)系？ 問題 2：圖中某個(gè)結(jié)點(diǎn)的度數(shù)和從它 引出 的分支之間的關(guān)系？ 假設(shè) B為上圖所表的樹中分支（直線段）的個(gè)數(shù)， ni 表示度為 i的結(jié)點(diǎn)的個(gè)數(shù)， n為結(jié)點(diǎn)總數(shù)，顯然有 n=B+1, n=n0+n1+n2…n k, B=n0*0+n1*1+n2*2+…n k*k, 例如： . 設(shè)樹 T的度為 4，其中度為 1， 2， 3和 4的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2， 1， 1 則 T中的葉子數(shù)為（ ） A． 5 B． 6 C． 7 D． 8 D n=B+1, n=n0+n1+n2…n k, B=n0*0+n1*1+n2*2+…n k*k, B= n0*0+1*4+2*2+3*1+4*1=15, n=B+1=16, 而 n=n0+4+2+1+1=n0+8=16, n0=8 二叉樹 二叉樹的定義和基本運(yùn)算 1. 定義 定義：二叉樹是另一種樹形結(jié)構(gòu)。它與樹形結(jié)構(gòu)的區(qū)別是： （ 1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹； （ 2）子樹有左右之分。 二叉樹也可以用遞歸的形式定義。即：二叉樹是 n（ n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng) n=0時(shí)，稱為空二叉樹；當(dāng) n0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)作為左子集，另一個(gè)作為右子集，每個(gè)子集又是一個(gè)二叉樹。 G H D E F B C A 例如： 二叉樹的 5種形態(tài)： 248。 (a) (b) (c) (d) (e) 二叉樹的第 1層只有一個(gè)根結(jié)點(diǎn)，所以， i=1時(shí)， 2i1=211=20=1成立。 假設(shè)對(duì)所有的 j， 1≤ji成立，即第 j層上最多有 2j1個(gè)結(jié)點(diǎn)成立。若 j=i1，則第 j層上最多有 2j1=2i2個(gè)結(jié)點(diǎn)。由于在二叉樹中，每個(gè)結(jié)點(diǎn)的度最大為 2，所以可以推導(dǎo)出第 i層最多的結(jié)點(diǎn)個(gè)數(shù)就是第 i1層最多結(jié)點(diǎn)個(gè)數(shù)的 2倍，即 2i2*2=2i1。 2．二叉樹的性質(zhì) 二叉樹具有下列 5個(gè)重要的性質(zhì)。 【 性質(zhì) 1】 在二叉樹的第 i層上最多有 2i1個(gè)結(jié)點(diǎn)（ i≥1）。 【 性質(zhì) 2】 深度為 K的二叉樹最多有 2K1個(gè)結(jié)點(diǎn)（ K≥ 1）。 qqaaSnn???1*1由性質(zhì) 1可以得出， 1至 K層各層最多的結(jié)點(diǎn)個(gè)數(shù)分別為：20,21,22,23,...,2K1。這是一個(gè)以 2為比值的等比數(shù)列，前 n項(xiàng)之和的計(jì)算公式為： 其中 a1為第一項(xiàng)， an為第 n項(xiàng)， q為比值?？梢缘玫?，該數(shù)列前 K項(xiàng)之和為： 12212*1202????? KK【 性質(zhì) 3】 對(duì)于任意一棵二叉樹 BT，如果度為 0的結(jié)點(diǎn)個(gè)數(shù)為 n0，度為 2的結(jié)點(diǎn)個(gè)數(shù)為 n2，則 n0=n2+1。 證明：假設(shè)度為 1的結(jié)點(diǎn)個(gè)數(shù)為 n1，結(jié)點(diǎn)總數(shù)為 n， B為二叉樹中的分支數(shù)。 因?yàn)樵诙鏄渲?，所有結(jié)點(diǎn)的度均小于或等于 2，所以結(jié)點(diǎn)總數(shù)為： n=n0+n1+n2 （ 1） 再查看一下分支數(shù)。在二叉樹中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有一個(gè)從上向下的分支指向，所以，總的結(jié)點(diǎn)個(gè)數(shù) n與分支數(shù) B之間的關(guān)系為： n=B+1。 又因?yàn)樵诙鏄渲?，度?1的結(jié)點(diǎn)產(chǎn)生 1個(gè)分支，度為 2的結(jié)點(diǎn)產(chǎn)生 2個(gè)分支，所以分支數(shù) B可以表示為： B=n1+2n2。 將此式代入上式，得： n=n1+2n2+1 （ 2） 用（ 1）式減去（ 2）式，并經(jīng)過調(diào)整后得到： n0=n2+1。 滿二叉樹： 如果一個(gè)深度為 K的二叉樹擁有 2K1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1