第6章樹(shù)與二叉樹(shù)-wenkub
2022-11-04 15:07:05 本頁(yè)面
【正文】 ENT (i) 是節(jié)點(diǎn) ?i/2? 。 特點(diǎn)：每一層上的節(jié)點(diǎn)數(shù)都達(dá)到了最大節(jié)點(diǎn)數(shù)。 ?性質(zhì) (2)：深度為 k的二叉樹(shù)至多有 2k1個(gè)節(jié)點(diǎn)（ k ≥ 1）。child) 遍歷樹(shù) tree各元素，并用visit代表的操作處理元素?cái)?shù)據(jù) 在樹(shù) tree中求節(jié)點(diǎn) elem的父節(jié)點(diǎn)，并將結(jié)果放入parent中 說(shuō)明 :在樹(shù) tree中求節(jié)點(diǎn) parent的第 order個(gè)子節(jié)點(diǎn)，并將結(jié)果放入 child中 treeSetChild(tree,parent,order,child) } 在樹(shù) tree中設(shè)置節(jié)點(diǎn)parent的第 order個(gè)子節(jié)點(diǎn)，待設(shè)置的值已經(jīng)放入 child中 二叉樹(shù) 二叉樹(shù)的定義與基本運(yùn)算 二叉樹(shù)是一個(gè)集合 T；它可以是空集 ， 也可以是一個(gè)由節(jié)點(diǎn)組成的有限集 。tree) treeEmpty(tree) treeWidth(tree) 創(chuàng)建一棵樹(shù) tree 銷(xiāo)毀一棵已有的樹(shù)tree 創(chuàng)建一棵樹(shù) tree 判樹(shù)是否為空 求樹(shù)的度 treeDepth(tree) treeRoot(tree) treeInsert(amp。 () 對(duì)應(yīng)于 D{r}的劃分 ,H{r,x1,r,x2,…,r,xm}有惟一的一個(gè)劃分H1,H2,…,Hm(m0),對(duì)任意 j?k(1≤ j,k≤ m)有Hj∩ Hk=Ф,且對(duì)任意的 i(1≤ i≤ m),Hi是 Di上的二元關(guān)系 ,(Di,{Hi})是一棵符合本定義的樹(shù) ,稱(chēng)為根 r的子樹(shù)。 AB C DE F GHBGFHDECAABCDEFHG( b ) 文式圖表示方法( a ) 倒置的樹(shù)形圖表示方法 ( c ) 凹入表的表示方法圖6 . 2 樹(shù)形結(jié)構(gòu)中分支與層次特性的表示本書(shū)中描述 樹(shù)形結(jié)構(gòu) 的方式 樹(shù)的基本術(shù)語(yǔ) ?節(jié)點(diǎn) ?節(jié)點(diǎn)的度 ?葉子或終端節(jié)點(diǎn) ?非終端節(jié)點(diǎn)或分支節(jié)點(diǎn) ?內(nèi)部節(jié)點(diǎn) ?樹(shù)的度 ?孩子 ?雙親 ?兄弟 ?祖先 ?子孫 ?節(jié)點(diǎn)的層次 ?樹(shù)的深度或高度 ?有序樹(shù) ?無(wú)序樹(shù) ?森林 樹(shù)的 ADT ADT Tree { 數(shù)據(jù)對(duì)象為 D: D是具有相同特性的數(shù)據(jù)元素的集合 數(shù)據(jù)間的關(guān)系 R: (1) 若 D為空集 ,則稱(chēng)為空樹(shù) 。這樣的節(jié)點(diǎn)序列稱(chēng)為從 根到節(jié)點(diǎn) e的一條路徑 。 除了 首元 （ 唯一存在 ，在樹(shù)形結(jié)構(gòu)中稱(chēng)為 “根” 節(jié)點(diǎn)）沒(méi)有前驅(qū)元素以外，樹(shù)中其他所有元素（ 節(jié)點(diǎn) ）都有且只有一個(gè)直接前驅(qū)元素（ 父 節(jié)點(diǎn)）；直接后繼元素則沒(méi)有限制：沒(méi)有直接后繼元素的節(jié)點(diǎn)（ 葉 節(jié)點(diǎn)）可以有多個(gè)；存在直接后繼元素的節(jié)點(diǎn)，其直接后繼元素的個(gè)數(shù)也可以有多個(gè)。 樹(shù)的定義與表示 ? 樹(shù)的定義 ： 樹(shù)的 邏輯結(jié)構(gòu) 可以這樣描述： 樹(shù)是包含 N(N0)個(gè)節(jié)點(diǎn)的 有窮集合 D，且在 D上定義了一個(gè) 關(guān)系 R，關(guān)系 R滿(mǎn)足以下條件： (1) 有且僅有一個(gè) 節(jié)點(diǎn) e0?D， 它對(duì)于關(guān)系R來(lái)說(shuō) 沒(méi)有前驅(qū) ， 節(jié)點(diǎn) e0稱(chēng)作樹(shù)的 根 。 樹(shù)的遞歸定義： 樹(shù)是由一個(gè)或多個(gè)節(jié)點(diǎn)組成的有限集 T，它滿(mǎn)足下面兩個(gè)條件： (1)有一個(gè)特定的節(jié)點(diǎn)稱(chēng)之為 根 。 (2) 若 D為非空集且僅含有一個(gè)數(shù)據(jù)元素 ,則 R為空集 ,樹(shù)只包含一個(gè)根節(jié)點(diǎn) 。 幾種基本操作 : treeCreate(amp。tree,elem) treeDelete(amp。 同時(shí) ， 集合 T具有下列的性質(zhì)： (1) 如果 T是空集 ， 則稱(chēng) T是空的二叉樹(shù) 。 ?性質(zhì) (3)：對(duì)任何一棵二叉樹(shù) T，如果其葉節(jié)點(diǎn)數(shù)為 n0，度為 2的節(jié)點(diǎn)數(shù)為 n2，則n0=n2+1。 完全二叉樹(shù)： （ 1）葉子節(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1