[理學]數(shù)據(jù)結(jié)構(gòu)7樹形結(jié)構(gòu)(編輯修改稿)
2024-11-12 21:14 本頁面
【文章內(nèi)容簡介】 點 。 11??mmh11??mmh證明： 由樹的性質(zhì) 2可知 ， 第 i 層上最多結(jié)點數(shù)為 mi1(i=1,2,… ,h)， 顯然當高度為 h 的 m 次樹 (即度為 m的樹 )上每一層都達到最多結(jié)點數(shù)時 ， 整個 m 次樹具有最多結(jié)點數(shù) ， 因此有： 整個樹的最多結(jié)點數(shù) = 每一層最多結(jié)點數(shù)之和 = m0 + m1 + m2 + … + mh1 = ?當一棵 m次樹上的結(jié)點數(shù)達到： (mh1)/(m1)則稱該樹為滿 m次數(shù) 。 例如高度為 3的滿 2次樹 (每個結(jié)點的度最大為 2)， 總結(jié)點數(shù) = (231)/(21)=7 1 2 3 4 5 6 7 性質(zhì) 4： 具有 n 個結(jié)點的 m 次樹的最小高度為 ?logm(n(m1)+1)?。 證明：略 例 ： 若一棵三次樹中度為 3 的結(jié)點個數(shù)為 2， 度為 2 的結(jié)點個數(shù)為 1， 度為1的結(jié)點個數(shù)為 2， 則該三次樹中總的結(jié)點個數(shù)和度為 0的結(jié)點個數(shù)分別是多少 ？ 解：設(shè)該三次樹中總的結(jié)點個數(shù)： n 度為 0的結(jié)點個數(shù)： n0 度為 1的結(jié)點個數(shù)： n1 度為 2的結(jié)點個數(shù)： n2 度為 3的結(jié)點個數(shù)： n3 由已知條件得到： n1=2， n2=1， n3=2 由樹的性質(zhì) 1可知： (樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加 1) n = 0 n0 + 1 n1 + 2 n2 + 3 n3 + 1 = 11 又因為： n = n0 + n1 + n2 + n3 即： n0 = n n1 n2 n3 = 11212 = 6 所以該三次樹中總的結(jié)點個數(shù)和度為 0的結(jié)點個數(shù)分別是 11和 6。 樹的基本運算 由于樹是非線性結(jié)構(gòu) ， 結(jié)點之間的關(guān)系較線性結(jié)構(gòu)復雜得多 ， 所以樹的運算較以前討論過的各種線性數(shù)據(jù)結(jié)構(gòu)的運算要復雜許多 。 樹的運算主要分為三大類： (1) 第一類 ， 尋找滿足某種特定關(guān)系的結(jié)點 ， 如尋找當前結(jié)點的雙親結(jié)點等； (2) 第二類 ， 插入或刪除某個結(jié)點 ， 如在樹的當前結(jié)點上插入一個新結(jié)點或刪除當前結(jié)點的第 i個 孩子結(jié)點等； (3) 第三類 ， 遍歷樹中每個結(jié)點 (重點內(nèi)容 )。 樹的遍歷運算是指按某種方式訪問樹中的每一個結(jié)點 ， 且每一個結(jié)點只被訪問一次 。 樹的遍歷運算的算法主要有先根遍歷和后根遍歷兩種 。 注意 ， 下面的先根遍歷和后根遍歷算法都是遞歸的 。 1. 先根遍歷 先根遍歷過程為： (1) 訪問根結(jié)點； (2) 按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹。 例 ：求該樹的先序遍歷次序 。 (1) 訪問根結(jié)點； (2) 按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹。 R A B C D E F G H K R ?按照從左到右的次序先根遍歷子樹 A、 B、 C ?遍歷每個子樹時又要按照原則 (1)和 (2)進行 即遍歷 B之前應完成 A的遍歷 。 A D E B C F G H K 2. 后根遍歷 后根遍歷過程為： (1) 按照從左到右的次序后根遍歷根結(jié)點的每一棵子樹； (2) 訪問根結(jié)點 。 ?遇到 R時不訪問 ， 要待到其所有子樹全部訪問完畢 (左至右 )， 即準備訪問 A； ?處理 A時遵守同樣的規(guī)則 。 D E A B G H K F C R A B C D E F G H I J K L M 練習：寫出下面這棵樹的先根和后根遍歷次序 。 ?先根遍歷： A,B,E,K,L,F,C,G,D,H,M,I,J ?后根遍歷： K,L,E,F,B,G,C,M,H,I,J,D,A 樹的存儲結(jié)構(gòu) 樹的存儲既要求保存結(jié)點的數(shù)據(jù)元素本身 ， 又要存儲結(jié)點之間的邏輯關(guān)系 。 1. 二維數(shù)組表示法 (Array Representation,補充 ) 數(shù)組中的行數(shù)目用樹中結(jié)點數(shù)的數(shù)目表示 ， 列數(shù)用樹的度 +1表示 。 例 ： A B C D E F G H I J K L M A:{B,C,D} B:{E,F} C:{G} D:{H,I,J} E:{K,L} H:{M} 該樹有 13個結(jié)點即數(shù)組有 13行 ， 樹的度為 3所以數(shù)組要有 4列 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 A B C D E F G H I J K L M 1 2 3 (子樹根的地址 ) 4 5 6 7 8 9 10 11 12 特點：查找任一結(jié)點的孩子結(jié)點非常方便 ， 查找父結(jié)點麻煩 解決方法：增加一列存儲父結(jié)點的地址 5 1 0 0 0 1 1 2 3 3 3 4 4 7 2. 雙親存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu) ， 用一組連續(xù)空間存儲樹的所有結(jié)點 ， 同時在每個結(jié)點中附設(shè)一個偽指針 (下標 )指示其雙親結(jié)點的位置 。 R A B C D E F
教學課件相關(guān)推薦
鄂ICP備17016276號-1