特性：

什么是樹：

樹(Tree)是(n>=0)個節點的有限集合T，它滿足兩個條件：

(1) 有且僅有一個特定的稱為根（Root）的節點。

(2) 其余的節點可以分為m（m≥0）個互不相交的有限集合T1、T2、……、Tm，其中每一個集合又是一棵樹，并稱為其根的子樹（Subtree）。

樹的特性：

層次關系，一對多，每個節點最多有一個前驅，但是可以有多個后繼(根節點無前驅，葉節點無后繼)。

關于樹的節點：和鏈表類似，樹存儲結構中也將存儲的各個元素稱為 "結點"。

關于樹的一些術語：

(1) 度數：一個節點的子樹的個數 （一個節點有幾個孩子為該節點度數）

(2) 樹度數：樹中節點的最大度數

(3) 葉節點或終端節點: 度數為零的節點

(4) 分支節點：度數不為零的節點 （A B C D E H）

(5) 內部節點：除根節點以外的分支節點 （去掉根和葉子）

(6) 節點層次: 根節點的層次為1，根節點子樹的根為第2層，以此類推

(7) 樹的深度或高度: 樹中所有節點層次的最大值

二叉樹：

最多只有倆孩子的樹，并且分為左孩子和右孩子。

什么是二叉樹：

二叉樹（Binary Tree）是n（n≥0）個節點的有限集合，它或者是空集（n＝0）， 或者是由一個根節點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。

二叉樹與普通有序樹不同，二叉樹嚴格區分左孩子和右孩子，即使只有一個子節點也要區分左右。

二叉樹的性質（**）

(1) 二叉樹第k（k>=1）層上的節點最多為2的k-1次冪 // 2^(k-1)

(2) 深度為k（k>=1）的二叉樹最多有2的k次冪-1個節點。//滿二叉樹的時候

做多的節點數 2^k-1

(3) 在任意一棵二叉樹中，樹葉的數目比度數為2的節點的數目多一。

設度數為0的節點數為n0，度數為1的節點數為n1以及度數為2的節點數為n2，則：

總節點數為各類節點之和:n=n0+n1+n2

總節點數為所有子節點數加一：n=n0*0+n1*1+n2*2+1

下面式子減上面式子得：0=-n0+n2+1==>n0 = n2 + 1

滿二叉樹和完全二叉樹

滿二叉樹: 深度為k（k>=1）時節點數為2^k - 1(2的k次冪-1)

完全二叉樹: 只有最下面兩層有度數小于2的節點，且最下面一層的葉節點集中在最左邊的若干位置上。(先掛樹的左邊向右, 從上向下掛)

二叉樹的存儲結構：

二叉樹的順序結構：

順序存儲結構 ：完全二叉樹節點的編號方法是從上到下，從左到右，根節點為1號節點。設完全二叉樹的節點數為n，某節點編號為i：

● 當i>1（不是根節點）時，有父節點，其父節點編號為i/2;

● 當2*i<=n時，有左孩子，其編號為2*i ,否則沒有左孩子，本身是葉節點;

● 當2*i+1<=n時，有右孩子，其編號為2*i+1 ,否則沒有右孩子；

有n個節點的完全二叉樹可以用有n+1 個元素的數組進行順序存儲，節點號和數組下標一一對應，下標為零的元素不用。

利用以上特性，可以從下標獲得節點的邏輯關系。不完全二叉樹通過添加虛節點構成完全二叉樹，然后用數組存儲，

二叉樹的遍歷（*）

前序： 根 ----> 左 -----> 右

中序: 左 ----> 根 -----> 右

后序: 左 ----> 右 -----> 根

例如：

前序:A B C D E F G H K

中序：B D C A E H G K F

后序：D C B H K G F E A

練習：

已知遍歷結果如下，試畫出對應的二叉樹。

前序: A B C E H F I J D G K

中序：A H E C I F J B D K G

提示：用前序確定根節點，然后用中序找到根節點然后再找左右子。

練習：

(2) 深度為8的二叉樹，其最多有( 255) 個節點，第8層最多有(128 )個節點

(3) 數據結構中，沿著某條路線，一次對樹中每個節點做一次且僅做一次訪問，對二叉樹的節點從1開始進行連續編號，要求每個節點的編號大于其左、右孩子的編號，同一節點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用(C )次序的遍歷實現編號(網易)

A 先序 B 中序 C 后序 D 從根開始層次遍歷

(4)一顆二叉樹的 前序： A B D E C F, 中序：B D A E F C 問樹的深度是 ( B) (網易)

A 3 B 4 C 5 D 6

二叉樹的鏈式存儲

用鏈表實現，基于完全二叉樹規律來構建樹，按照完全二叉樹的編號方法，從上到下，從左到右。一共n個節點。

第i個節點：

左子節點編號：2*i（2*i<=n）

右子節點編號：2*i+1(2*i+1<=n)

可以根據左右節點編號來判斷是否對二叉樹構建完成

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{int data;            //數據域存數據struct node *lchild; //左子struct node *rchild; //右子
} node_t, *node_p;//創建二叉樹,用遞歸函數創建
node_p CreateBitree(int n, int i) //i 根節點的編號，n：節點數
{//創建根節點node_p r = (node_p)malloc(sizeof(node_t));if (NULL == r){perror("r malloc err");return NULL;}//初始化根節點r->data = i;if (2 * i <= n)r->lchild = CreateBitree(n, 2 * i);elser->lchild = NULL;if (2 * i + 1 <= n)r->rchild = CreateBitree(n, 2 * i + 1);elser->rchild = NULL;return r;
}//前序
void PreOrder(node_p r)
{if (NULL == r)return;             //直接結束函數無返回值printf("%d ", r->data); //根if (r->lchild != NULL)PreOrder(r->lchild); //左if (r->rchild != NULL)PreOrder(r->rchild); //右
}//中序
void InOrder(node_p r)
{if (NULL == r)return; //直接結束函數無返回值if (r->lchild != NULL)InOrder(r->lchild); //左printf("%d ", r->data); //根if (r->rchild != NULL)InOrder(r->rchild); //右
}//后序
void PostOrder(node_p r)
{if (NULL == r)return; //直接結束函數無返回值if (r->lchild != NULL)PostOrder(r->lchild); //左if (r->rchild != NULL)PostOrder(r->rchild); //右printf("%d ", r->data); //根
}int main(int argc, char const *argv[])
{node_p root = CreateBitree(5, 1);PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");return 0;
}

層次遍歷

層次遍歷（隊列思想）一定要懂

補充知識點（哈夫曼樹）

哈夫曼樹

哈夫曼樹又稱為最優樹.

給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

概念：

1、路徑和路徑長度

在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。

2、結點的權及帶權路徑長度

若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。

3、樹的帶權路徑長度

樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。（

Weighted Path Length of Tree）

WPL=2*2+5*2+7*1=21

赫夫曼樹的構造

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

例如：對 2，3，4，8 這四個數進行構造：

第一步：

第二步：

第三步：