[電腦基礎(chǔ)知識(shí)]第7章 樹-文庫(kù)吧
2025-01-04 15:32 本頁面
【正文】 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 先序序列： A B D E H I C F 后序序列： D H I E B F G C A 中序序列： D B H E I A F C G 例： ? 最早提出遍歷問題是對(duì)存儲(chǔ)在計(jì)算機(jī)中的表達(dá)式求值。例如： (a+b*c)d/e。該表達(dá)式用二叉樹表示如圖 。當(dāng)我們對(duì)此二叉樹進(jìn)行先序、中序、后序遍歷時(shí)，便可獲得表達(dá)式的前綴、 中綴、 后綴書寫形式： – 前綴： +a*bc/de – 中綴： a+b*cd/e – 后綴： abc*+de/ ? 其中中綴形式是算術(shù)表達(dá)式的通常形式，只是沒有括號(hào)。 前綴表達(dá)式稱為波蘭表達(dá)式。算術(shù)表達(dá)式的后綴表達(dá)式被稱作逆波蘭表達(dá)式。 在計(jì)算機(jī)內(nèi)， 使用后綴表達(dá)式易于求值。 /edcb＋*－a圖 算術(shù)式的樹表示 樹的表示法 1 3 2 10 9 4 5 8 7 6 圖 樹 父結(jié)點(diǎn)數(shù)組表示法 0 1 1 2 2 5 5 5 3 3 1 2 3 4 5 6 7 8 9 10 兒子鏈表表示法 . . . . . . . . . . 2 4 5 ^ 10 ^ 3 ^ 9 8 ^ 7 6 1 2 3 4 5 6 7 8 9 10 header ? 左兒子右兄弟表示法 A C B F D E I H G A ^ C ^ B ^ F ^ E ^ ^ D ^ G ^ H ^ I ^ 二叉樹 ? 定義 ： 二叉樹是 n(n=0)個(gè)結(jié)點(diǎn)的有限集合，此集合或者為空集（ n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。 ? 特點(diǎn) ： （即二叉樹中不存在度大于 2的結(jié)點(diǎn) )。 。 ，分別稱之為左子樹和右子樹 ,其次序不能任意顛倒。 二叉樹的 5種基本形態(tài)： (a) (b) (c) (d) (e) 二叉樹與樹和有序樹的區(qū)別 ? 特別要注意： 二叉 樹 不是 樹的特殊情況，它們是兩個(gè)不同的概念。 b c d e a c d e b a a b c d e (a) (b) (c) A． 樹中結(jié)點(diǎn)的最大度數(shù)沒有限制 ， 二叉樹結(jié)點(diǎn)最大度數(shù)為 2。 B． 樹的結(jié)點(diǎn)無左 、 右之分 ， 二叉樹的結(jié)點(diǎn)子樹有明確的左 、 右之分 。 樹 二叉樹 二叉樹的性質(zhì) ① 高度為 h=0的二叉樹至少有 h+1個(gè)結(jié)點(diǎn)。 ② 高度不超過 h的二叉樹至多有 2h+11個(gè)結(jié)點(diǎn)。 ③ 含有 n=1個(gè)結(jié)點(diǎn)的二叉樹的高度至多為n1。 ④ 含有 n=1個(gè)結(jié)點(diǎn)的二叉樹的高度至少為[logn]，因此其高度為 Ω(logn)。 ? 性質(zhì) 5：在二叉樹的第 i層上至多有 2i個(gè)結(jié)點(diǎn) (i=0)。 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 第二層上 (i=2)，有 22=4個(gè)結(jié)點(diǎn)。 第三層上 (i=3)，有 23=8個(gè)結(jié)點(diǎn)。 兩種特殊形態(tài)的二叉樹 滿二叉樹：一棵高度為 h且由 2h+11個(gè)結(jié)點(diǎn)的二 叉樹稱為滿二叉樹。 4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 特點(diǎn)： 1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且葉子都在最下一層。 完全二叉樹 高度為 k的 ， 有 n個(gè)結(jié)點(diǎn)的二叉樹 ， 當(dāng)且僅當(dāng)每一個(gè)結(jié)點(diǎn)都與高度為 k的滿二叉樹中編號(hào)從 1至 n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí) ， 稱為完全二叉樹 （ 也稱為近似滿二叉樹 ） 完全二叉樹 4 2 3 1 6 7 8 9 10 11 12 5 ? 特點(diǎn)： （ 1）葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)； （ 2）對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫最大層次為 L，則其左分支下的子孫最大層次必為 L或 L+1。 1 2 3 4 5 7 1 2 3 6 7 (b)非完全二叉樹 (c)非完全二叉樹 （ b）、（ c）是 2棵非完全二叉樹。滿二叉樹是完全二叉樹的特例。 1 2 3 4 5 6 (a)完全二叉樹 ? 對(duì)一棵完全二叉樹，有： 于 2； ； ，反之不然，在完全二叉樹中，若某個(gè)結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。 完全二叉樹 4 2 3 1 6 7 8 9 10 11 12 5 ADT 二叉樹 ? 二叉樹的基本運(yùn)算 ① BinaryInit( ):創(chuàng)建一棵空二叉樹 ② BinaryEmpty(T):判斷一棵二叉樹 T是否為空 ③ Root(T):返回二叉樹 T的根結(jié)點(diǎn)標(biāo)號(hào) ④ MakeTree(x,T,L,R):以 x為根結(jié)點(diǎn)元素，分別以 L和 R為左、右子樹構(gòu)建一棵新的二叉樹 T。 ⑤ BreakTree(T,L,R) ⑥ PreOrder(visit,t) ⑦ InOrder(visit,t) ⑧ PostOrder(visit,t) ⑨ PreOut(T) ⑩ InOut(T) 11 PostOut
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1