1、樹的定義

樹是n(n>=0)個節點的有限集合。當n=0時稱為空樹，當n>0 為非空樹，任何非空樹中，有且僅有一個根節點；其余節點可分為m(m>=0)個互不相交的有限集合T1、T2 等，其中每一個集合都可以稱為一棵樹，稱為根節點的子樹。

2、樹的基本概念?

? ? ? ??雙親孩子、兄弟：節點的字數的根稱為該節點的孩子，該節點稱為其子節點的雙親。具有相同雙親的節點互為兄弟節點。如圖：A是根節點，B、C、D互為兄弟；B是E、F的父節點（雙親）；E、F 互為兄弟節點。

節點的度：一個節點下的子節點個數稱為節點的度。比如 A的度為3，D的度為1。

葉子節點：是指度為0的節點，也被稱為終端節點。比如 C、E、F、G都是葉子節點。

內部節點：度不為零的節點稱為分支節點或非終端節點。去掉根節點，分支節點稱為內部節點。比如：B、D。

節點的層次：根節點A屬于第一層，依次類推。B屬于第二層，E屬于第三層。

樹的高度：一棵樹的最大層次數稱為樹的高度或者樹的深度。

有序（無序）樹：樹中的節點的各個子樹看成是從左到右有次序的，即不能交換，則稱為有序樹，否則為無序樹。

森林：m(m>=0)棵互補相交的樹的集合。

3、二叉樹

3.1 二叉樹定義

二叉樹是n(n>=0)個節點的有限集合，它或者是空樹（n=0），或者是由一個根節點及兩棵不相交的、分別稱為左子樹、右子樹的二叉樹所組成。

3.2 二叉樹和普通樹的區別

二叉樹中節點區分左子樹、右子樹，即便只有一個子樹的情況下也有標明是左子樹還是右子樹，普通樹則不區分；二叉樹中節點最大度為2，普通樹則沒有限制節點的度數。

3.3 二叉樹的性質

1、二叉樹第i層上最多有 ?2^(i-1)個節點

2、深度為k的二叉樹最多有(2^k)-1個節點

3、對任何一棵二叉樹，若其終端節點數為n,度為2的節點數為n2，則n=n2+1

4、具有n個節點的完全二叉樹的深度為(log2^n)+1

3.4 二叉樹分類

1、滿二叉樹：深度為k的二叉樹有2^(k-1)個節點,是滿二叉樹

2、完全二叉樹:高度為k的二叉樹，除了第k層都是滿的，稱為完全二叉樹。滿二叉樹也是完全二叉樹。具有n個節點的完全二叉樹高度為 (log2^n) +1

3、非完全二叉樹：不滿足完全二叉樹的稱為非完全二叉樹。

3.5叉樹的存儲結構

1、二叉樹的順序存儲結構

用一組地址連續的存儲單元存儲二叉樹的節點，必須把節點排成一個適當的線性序列，并且節點在這個序列中的相互位置可以反映出節點之間的邏輯關系

順序存儲適合對完全二叉樹的存儲方式，既簡單又節省空間。對于一般二叉樹而言，因為在順序存儲結構中，以節點在存儲單元中的位置來表示節點之間的關系，所以存儲方式也必須按照完全二叉樹的方式存儲，這樣會造成空間上的浪費。最壞的情況，一個深度為h且只有h個節點的二叉樹（也是單枝樹）需要(2^h) -1 存儲單元.

2、二叉樹的鏈式存儲結構

由于二叉樹中節點包含數據、左子樹根、右子樹根、雙親信息，因此可以用三叉鏈表或二叉鏈表來 存儲二叉樹，鏈表的頭指針指向二叉樹的根節點。

3.6 ?二叉樹的遍歷

遍歷是按某種策略訪問樹中的每個節點，僅訪問一次。對于含有n個節點的二叉樹遍歷算法的時間復雜度都是O(n).

3.7 ?哈夫曼樹（最優二叉樹）

節點的路徑：從樹的一個節點到另一個節點之前的通路。

該通路的分支數據稱為路徑長度。

節點的帶權路徑：節點到樹根之間的路徑長度*該節點的權重值。

樹的帶權路徑長度為樹種所有葉子節點的帶權路徑長度之和。數值最小的就是哈夫曼樹。

IT技術分享社區

個人博客網站：https://programmerblog.xyz

文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識

?