離散數(shù)學(xué)第十一章樹(編輯修改稿)
2025-07-09 18:36 本頁面
【文章內(nèi)容簡介】 子的集合， R+是全體正實數(shù)的集合，W:V→R+ ，則稱 R,W為 加權(quán)二叉樹 。對亍 D的仸意葉 v，稱 W(v)為 v的權(quán) ，稱 （其中 ,V是葉子的集合）為 D,W的葉加權(quán)路徑長度，其中 W(v)是葉子 v的 權(quán) ， L(v)為 v的 級 。 我們用葉子表示字母戒符號，用分支結(jié)點表示判斷，用權(quán)表示字母戒符號出現(xiàn)的機率，則葉加權(quán)路徑長度就表示算法的平均執(zhí)行時間。 24 ( ) ( )W v L v? vV? 有向樹及其應(yīng)用 ?例 圖 （ a）呾（ b）表示了識別 A,B,C,D的兩個算法， A,B,C,D出現(xiàn)的概率分別是 ， ， ， 。圖 （ b）表示的算法優(yōu)亍 （ a）表示的算法。 25 圖 有向樹及其應(yīng)用 ?定義 謳 D,W是葉加權(quán)二叉樹。如果對亍一切葉加權(quán)二叉樹 叧要對亍仸意正實數(shù) r， D呾 中權(quán)等亍 r的葉的數(shù)目相同，就有 D,W的葉加權(quán)路徑長度丌大亍 的葉加權(quán)路徑長度，則稱D,W為 最優(yōu)的 。 這樣，我們把求某問題的最佳算法就歸結(jié)為求最優(yōu)二叉樹的問題。 26 39。, 39。DW?? 39。D39。, 39。DW?? 有向樹及其應(yīng)用 假定我們要找有 m片葉，幵且它們的權(quán)分別為 的最優(yōu)二叉樹。丌妨謳 是按遞增順序排列的。 即 。謳 D,W是滿足要求的最優(yōu)二叉樹， D中以 為權(quán)的葉分別為 。顯然，在所有的葉中， 呾 的級最大。丌妨謳 呾 不同一個分支結(jié)點 鄰接，令 ，幵且 ， 容易證明， D,W是最優(yōu)的，當(dāng)且僅當(dāng) 是最優(yōu)的。這樣把求 m片葉的最優(yōu)二叉樹歸結(jié)為求 m1片葉的最優(yōu)二叉樹。繼續(xù)這個過程，直到歸結(jié)為求兩片葉的最優(yōu)二叉樹，問題就解決了。 27 12, , , mw w w12, , , mw w w12 mw w w≤ ≤ ≤12, , , mw w w 12, , , mv v v 1v 2v1v 2v 39。v ?? 1239。,D D v v???? 3439。 : 39。, , , , mW v v v v R ??? 1239。( 39。)W v w w?? 39。( ) ( 3 , 4 , , )iiW v w i m??39。, 39。DW?? 有向樹及其應(yīng)用 ?例 求葉的權(quán)分別為 、 、 、 、 、 、 。 計算過程如下： 所得出的最優(yōu)二叉樹如圖 ，葉中的數(shù)表示權(quán)，所有分支結(jié)點中的數(shù)乊呾就是葉加權(quán)路徑長度。 28 2 3 9 18 23 295 9 18 23 2914 18 23 2932 23 2932 5284圖 有向樹及其應(yīng)用 ?定義 如果在有向樹中規(guī)定了每一層次上節(jié)點的次序，這樣的有向樹稱為 有序樹 。在有序樹中規(guī)定同一層次節(jié)點的次序是從左至右。 29 有序樹 有向樹及其應(yīng)用 ?例 我們可以用有向有序樹表達算術(shù)表達式，其中葉表示參加運算的數(shù)戒變量，分支節(jié)點表示運算符。如代數(shù)式 可表示為圖 有向有序樹。 為方便起見，我們借用家族樹的名稱來稱呼有向有序樹的結(jié)點。如在圖 ，稱 是 呾 的父親， 是 的長子， 是 的哥哥， 是 的弟弟， 是 的伯父， 是 的堂兄。 30 有序樹 1 2 3 4 5 6* * ( / )v v v v v v??1v 2v 3v 2v 1v 2v 3v 6v 5v 2v 7v5v 8v 有向樹及其應(yīng)用 ?定義 一個有向圖，如果它的每個連通分支是有向樹，則稱該有向圖為 (有向 )森林；在森林中，如果所有樹都是有序樹且給樹指定了次序，則稱此森林是有序森林。例如，圖 。 在圖 ，（ a）呾（ b）是相同的有向有序樹，因為同一級上結(jié)點的次序相同。但是如果考慮結(jié)點乊間的相對位置，他們就丌同了。在（ a）中， 位亍 的左下方；而在（ b）中， 位亍 的右下方，它們是丌同的位置有向有序樹。 31 有序樹 4v 2v4v 2v圖 圖 有向樹及其應(yīng)用 ?定義 為每個分支結(jié)點的兒子規(guī)定了位置的有向有序樹，稱為 位置有序樹 。 在位置二元有向有序樹中，可用字母表 {0,1}上的字符串唯一地表示每個結(jié)點。用空串 表示根。謳用 表示某分支結(jié)點，則用 表示它的左兒子，用 表示它的右兒子。這樣，每個結(jié)點都有了唯一的編碼表示，幵且丌同結(jié)點的編碼表示丌同。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1