??? 這次學(xué)習(xí)的重點(diǎn)在于二叉樹的性質(zhì)、鏈?zhǔn)酱鎯Y(jié)構(gòu)（也就是C語言的struct）和赫夫曼編碼，學(xué)習(xí)的教材是清華大學(xué)出版社出版的C語言版數(shù)據(jù)結(jié)構(gòu)。

??? 首先是二叉樹：
??? 二叉樹（Binary Tree）是另一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。?

?? 二叉樹的性質(zhì)：
?? 二叉樹作為一種重要的樹形結(jié)構(gòu)，在實(shí)際生活中的應(yīng)用雖然不大，但它的結(jié)構(gòu)使我們需要重點(diǎn)研究的。下面寫一寫二叉樹的性質(zhì)和一些我的理??? 解。
?? 性質(zhì)1?? 在二叉樹的第i層至多有2^(i-1)個(gè)結(jié)點(diǎn)。這里，我們把根定義為第一層。
????????????? 證明：用歸納法證明。
?? 性質(zhì)2?? 深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)。
????????????? 證明：結(jié)合性質(zhì)1，用等比數(shù)列求和公式。
?? 性質(zhì)3?? 對任何一顆二叉樹T，如果其終端結(jié)點(diǎn)數(shù)位n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1 。
????????????? 證明：設(shè)整個(gè)樹的結(jié)點(diǎn)數(shù)為n，則n=n0+n1+n2 。?? （1）
?????????????????????? 而樹里的每個(gè)結(jié)點(diǎn)（除開根節(jié)點(diǎn)）都是由一條分支引出，則n=n1+2n2+1 。? （2）
?????????????????????? 綜合（1）（2）得出 n0=n2+1 。
?? 性質(zhì)4? 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 └log_aN┘+1 。└ ┘表示取下整數(shù)。

?? 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)
?? typedef struct? BinTree{
????????? int? data;
????????? struct? BinTree *lchild,*rchild;????
?? }BinTree,*BinTree;

?? 赫夫曼編碼
?? 赫夫曼樹，又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。定義有著帶權(quán)路徑長度最小的二叉樹稱作最優(yōu)二叉樹（赫夫曼樹）。
?? 那么，如何構(gòu)造赫夫曼樹呢？現(xiàn)敘述如下：
（1）根據(jù)給定的n個(gè)權(quán)值{w1，w2…wn}構(gòu)造n棵二叉樹的集合F={T1，T2…Tn}，每課二叉樹Ti的根的權(quán)為Wi，左右子樹為空。
（2）將F={T1，T2…Tn}按權(quán)值由小到大穩(wěn)定排序。
（3）由最小的兩個(gè)權(quán)值樹T1，T2組成樹T，根的權(quán)為T1，T2根的權(quán)之和，左右子樹分別為T1、T2 。
（4）在F中刪除T1、T2，同時(shí)將T按序插入F中。
（5）重復(fù)（3）、（4），直到F中只剩一棵樹。

轉(zhuǎn)載于:https://www.cnblogs.com/perhapstang/archive/2009/12/19/1627692.html

總結(jié)

以上是生活随笔為你收集整理的基础算法学习（二）_二叉树及应用赫夫曼编码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。