北大離散數(shù)學(xué)chap(編輯修改稿)
2025-09-01 04:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的最小生成樹(shù)可能不唯一， G但 G 的不同最小生成樹(shù)權(quán)的值一樣。 第二節(jié) 根樹(shù)及其應(yīng)用 內(nèi)容： 有向樹(shù)，根樹(shù)，最優(yōu)二元樹(shù)。 重點(diǎn)： 有向樹(shù)及根樹(shù)的定義， 家族樹(shù)，有序樹(shù)， 元樹(shù)的概念， r最優(yōu) 2元樹(shù)的概念及哈夫曼 ()H u ffm a n算法。 一、根樹(shù)。 有向樹(shù) ： 一個(gè)有向圖 ，若略去有向邊的 D方向所得的無(wú)向圖為一棵無(wú)向樹(shù)，則稱 D 為 有向樹(shù) 。 根樹(shù) ： 一棵非平凡的有向樹(shù)，如果有一個(gè) 頂點(diǎn)的入度為 0，其余頂點(diǎn)的入度均為 1，則 稱此有向樹(shù)為 根樹(shù) 。 根樹(shù)的頂點(diǎn) 樹(shù)葉 (入度為 1，出度為 0) 分支點(diǎn) 樹(shù)根 (入度為 0) 內(nèi)點(diǎn) (入度為 1， 出度大于 0) 例 例 樹(shù)高。 的層數(shù) v —— 從樹(shù)根到頂點(diǎn) v 的通路 長(zhǎng)度，記 ()lv 。 樹(shù)高 —— 樹(shù)中頂點(diǎn)的最大層數(shù)，記 ()hT 。 如例 1(2)中， 家族樹(shù)。 一棵根樹(shù)可以看成一棵 家族樹(shù) 。 (1) 若頂點(diǎn) 鄰接到頂點(diǎn) ，則稱 為 a b b a 的兒子， 為 a b 的父親， (2) 若 a,bc 同為 的兒子，則稱 ,bc 為 兄弟 ， (3) 若 ad? ，而 可達(dá) a ，則稱 d a 為 d 的 祖先 ， d 為 a 的 后代 。 根子樹(shù)。 樹(shù) 的 根子樹(shù) T —— T 的非樹(shù)根的頂點(diǎn) a 及其 后代導(dǎo)出的子圖。 T8v7v6v5v4v3v2v1v例 3v39。T8v7v6v5v4v二、 元樹(shù)。 r 有序樹(shù) —— 每一層上都規(guī)定次序的根樹(shù)。 元樹(shù) r —— 每個(gè)分支點(diǎn)至多有 個(gè)兒子的根樹(shù)。 rr 元正則樹(shù) —— 每個(gè)分支點(diǎn)恰有 個(gè)兒子的根樹(shù)。 rr 元有序樹(shù) r 元有序正則樹(shù) 二、 元樹(shù)。 rr 元有序完全正則樹(shù) 注意： 2元有序正則樹(shù)是最重要的一種 r 元樹(shù)。 有序樹(shù) —— 每一層上都規(guī)定次序的根樹(shù)。 r 元完全正則樹(shù) 的層數(shù)相同 (等于樹(shù)高 )。 —— 元正則樹(shù)，且所有樹(shù)葉 r例 (1 )22111( 2 )2221112元有序樹(shù) 2元有序正則樹(shù) (3 )2 22111例 2元有序完全正則樹(shù) 最優(yōu) 2元樹(shù)。 (1) 的 權(quán) T最優(yōu) 2元樹(shù) —— 權(quán)最小的 2元樹(shù)。 —— 中每片樹(shù)葉所帶權(quán)與其層高 T乘積的和。 記為 1( ) ( )tiiiW T w L w?? ?例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6 1 2 3,T T T的 2元樹(shù)，求 1()WT， 2()WT 3()WT， 。 654311T解： 1( ) (6 3 ) 3 ( 4 5 1 ) 2 4 7WT ? ? ? ? ? ? ? ?例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6 1 2 3,T T T的 2元樹(shù)，求 1()WT， 2()WT 3()WT， 。 解： 2( ) ( 1 6 ) 4 5 3 4 2 3 1 5 4WT ? ? ? ? ? ? ? ? ? ?2T65431例 下圖中的 都是帶權(quán) 1， 3， 4， 5， 6
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1