小編給大家分享一下編程開發(fā)中二叉樹和霍夫曼樹的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供舞陽網(wǎng)站建設(shè)、舞陽做網(wǎng)站、舞陽網(wǎng)站設(shè)計、舞陽網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、舞陽企業(yè)網(wǎng)站模板建站服務(wù)，十余年舞陽做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

一、二叉樹的深層性質(zhì)

性質(zhì)1
在二叉樹的第 i層最多有 2^(i-1)個結(jié)點 。 (i≥1)
第一層最多有 2-1=1個結(jié)點
第二層最多有 2^(2-1)=2個結(jié)點
第三層最多有 2^(3-1)=4個結(jié)點
性質(zhì)2
深度為 k 的二叉樹最多有 2^k -1個結(jié)點 。 (k  ≥ 0)
如果有一層 ，最多有  1=2- 1=1 個結(jié)點
如果有兩層 ，最多有  1+2=2^2- 1=3 個結(jié)點
如果有三層 ，最多有  1+2+4=2^3 -1=7個結(jié)點
性質(zhì)3
對任何一棵二叉樹 ， 如果其葉結(jié)點有 n0個 ， 度為2的非葉結(jié)點有n2個， 有 則有
n0＝n2＋1
性質(zhì)4
具有n個結(jié)點的完全二叉樹的高度為[log2 n]+ 1  。 （[X]表示不大于  X  的最大整數(shù))
性質(zhì)5
一棵有 n個結(jié)點的二叉樹 （ 高度為[log2 n]+ 1）， 按層次對結(jié)點進行編號（ 從上到下 ， 從左到右 ），對任意結(jié)點 i 有 ：
如果  i = 1 ， 則結(jié)點 i 是二叉樹的根
如果  i > 1 ， 則其雙親結(jié)點為 [ i/2]
如果  2i <= n ，則結(jié)點  i 的左孩子為  2i
如果  2i > n  ， 則結(jié)點 i 無左孩子
如果  2i+1 <= n  ，則結(jié)點  i  為 的右孩子為  2i+1
如果  2i+1 > n , 則結(jié)點 i無右孩子

二、創(chuàng)建二叉樹的方法

指路法定位結(jié)點

指路法通過根結(jié)點與目標(biāo)結(jié)點的相對位置進行定位
指路法可以避開二叉樹遞歸的性質(zhì)“線性”定位

二叉樹存儲結(jié)構(gòu)

用結(jié)構(gòu)體來定義二叉樹中的指針域
二叉樹的頭結(jié)點也可以用結(jié)構(gòu)體實現(xiàn)

 //結(jié)點指針域定義
typedef struct _tag_BTreeNode BTreeNode;
struct _tag_BTreeNode
{
    BTreeNode* left;
    BTreeNode* right;   
};                             

//頭結(jié)點定義
typedef struct _tag_BTree TBTree;
struct  _tag_BTree
{
    int count;
    BTreeNode* root;
};

定位：利用二進制中的0和1分別表示left和right，位運算是實現(xiàn)指路法的基礎(chǔ)

三、遍歷二叉樹

單鏈表的遍歷是指從第一個結(jié)點開始（下標(biāo)為0的結(jié)點），按照某種次序依次訪問每一個結(jié)點。
二叉樹的遍歷是指從根結(jié)點開始，按照某種次序依次訪問二叉樹中的所有結(jié)點。
前序遍歷

中序遍歷

后序遍歷

層次遍歷

四、線索化二叉樹

線索化二叉樹指的是將二叉樹中的結(jié)點進行邏輯意義上的“重排列”，使其可以線性的方式訪問每一個結(jié)點
二叉樹線索化之后每個結(jié)點都有一個線性下標(biāo)，通過這個下標(biāo)可以快速訪問結(jié)點，而不需要遍歷二叉樹
線索化方法1
 利用結(jié)點中的空指針域，使其指向后繼結(jié)點

算法思想：

線索化方法2
 利用線性表保存二叉樹的遍歷順序

算法思想：

利用結(jié)點空指針線索化的方法會破壞樹的結(jié)構(gòu)，線索化二叉樹之后不能夠再恢復(fù)
這兩個問題可以在樹結(jié)點中加入一個線索化指針而得以解決
 然而線索化指針的加入又會浪費內(nèi)存空間，不夠靈活
 鏈表線索化方法不會破化樹的結(jié)構(gòu)，不需要時線索化時銷毀鏈表即可
鏈表線索化方法可以很容易的以任何一種遍歷順序?qū)Χ鏄溥M行線索化

五、霍夫曼樹

以上是“編程開發(fā)中二叉樹和霍夫曼樹的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！