熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

09年自考《數據結構》各章要點二[3]

2013-11-15 15:01:35  來源: 數據結構 

  樹的前序遍歷與相對應的二叉樹的前序遍歷一致;樹的後序遍歷與相對應的二叉樹的中序遍歷一致

  樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和樹的帶權路徑長度最小的二叉樹就稱為最優二叉樹(即哈夫曼樹)

  在葉子的權值相同的二叉樹中完全二叉樹的路徑長度最短

  哈夫曼樹有n個葉結點共有n個結點沒有度為的結點這類樹又稱為嚴格二叉樹

  變長編碼技術可以使頻度高的字符編碼短而頻度低的字符編碼長但是變長編碼可能使解碼產生二義性這三個碼無法在解碼時確定是哪一個所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴這種碼稱為前綴碼(其實是非前綴碼)

  哈夫曼樹的應用最廣泛地是在編碼技術上它能夠容易地求出給定字符集及其概率分布的最優前綴碼哈夫曼編碼的構造很容易只要畫好了哈夫曼樹按分支情況在左路徑上寫代碼右路徑上寫代碼然後從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優前綴碼

  第七章 圖

  圖的邏輯結構特征就是其結點(頂點)的前趨和後繼的個數都是沒有限制的即任意兩個結點之間之間都可能相關

  圖GraphG=(VE)V是頂點的有窮非空集合E是頂點偶對的有窮集

  有向圖Digraph每條邊有方向

  無向圖Undigraph每條邊沒有方向

  有向完全圖具有n*(n)條邊的有向圖

  無向完全圖具有n*(n)/條邊的無向圖

  有根圖有一個頂點有路徑到達其它頂點的有向圖

  簡單路徑是經過頂點不同的路徑

  簡單回路是開始和終端重合的簡單路徑

  網絡是帶權的圖

[]  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22736.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.