樹是n（n>=0）個結點的有限集。n=0時稱為空樹。在任意一棵非空樹中：1.有且僅有一個特定的稱為根的結點2.當n>1時其餘結點可分為m（m>0）個互不相交的有限集T1,T2。。。。。Tn 其中每一個集合本身又是一棵樹，并且稱為根的子樹。
結點擁有的子樹數稱為結點的度，度為0的結點稱為葉結點或終端結點;度不為0的結點稱為非終端結點或分支結點。除根結點之外，分支結點也稱為内部結點，樹的度是樹内各結點的度的最大值。
------A------
| |
--------B -----C-----
| | |
--------D------- E F
| | | |
G H I J
A為根節點 BCDE為内部結點 GHIJF為葉結點或終端結點
B結點度為1 C度為2 D結點度為3 J結點度為0
ABCDE 為分支結點或非終端結點
B是D的雙親 B是A的孩子 B和C互為兄弟
結點的層次從根開始 第一層 第二層 第三層 第四層
最大層次稱為樹的深度或高度 目前為4
雙親在同一層的結點互為堂兄弟 例如I J
如果将樹中結點的各子樹看成從左到右是有次序的，不能互換的，則稱該樹是有序樹，否則是無序樹。
森林是m（m>=0） 棵互不相交的樹的集合，對樹中每個結點而言，其子樹的集合即為森林。 例如 B結點及以下 和C及以下結點 那麼B C 即森林
樹的抽象資料類型
ADT 樹（tree）
Data
樹是由一個根節點和若幹棵子樹構成。樹中結點具有相同資料類型及層次關系
Operation
InitTree（*T）：構造空樹T
DestroyTree（*T）：銷毀樹T
CreateTree(*T，definition)：按definition中給出樹的定義來構造樹
ClearTree（*T）：若樹T存在，則将樹T清為空樹。
TreeEmpty（T）：若T樹為空樹，傳回true，否則傳回false
TreeDepth(T)：傳回T的深度
Root(T)：傳回T的根結點
Value（T，cur_e）：cur_e是樹T中的一個結點，傳回此結點的值
Assign（T，cur_e，value）：給樹T的結點cur_e指派為value
Parent(T，cur_e)：若cur_e是樹T的非根結點，則傳回它的雙親，否則傳回空。
LeftChild（T，cur_e）：若cur_e是樹T的非葉結點，則傳回它的最左孩子，否則傳回空。
RightSibling(T，cur_e)：若cur_e有右兄弟，則傳回它的右兄弟，否則傳回空
InsertChild(*T,*p，i，c)：其中p指向樹T的某個結點，i為所指結點p的度加上1，非空樹c與T不相交，操作結果為插入c為樹T中p指結點的第i棵子樹
DeleteChild（*T，*p，i）：其中p指向樹T的某個結點，i為所指結點p的度，操作結果為删除T中p所指結點的第i棵子樹
endADT
樹的存儲結構
1.雙親表示法
在每個結點中，附設一個訓示器訓示其雙親結點到連結清單中的位置
data parent
其中data是資料域，存儲節點的資料資訊，而parent是指針域，存儲節點的雙親在數組中的下标
樹的雙親表示法結點結構定義。
#define MAX_TREE_SIZE 100
typedef int TElemType; 樹結點的資料類型，目前暫定為整型
typedef struct PTNode 結點結構
｛
TElemType data; 結點資料
int parent; 雙親位置
｝PTNode;
typedef struct 樹結構
PTNode nodes[MAX_TREE_SIZE]; 結點數組
int r,n; 根的位置和結點數
｝PTree;
由于根結點是沒有雙親的，是以我們約定根結點的位置域設定是-1.
下标 data parent
0 A -1
1 B 0
2 C 0
3 D 1
4 E 2
可以根據parent指針很容易找到雙親結點，是以O(1)，如果是找結點的孩子，那就要周遊整個結構。
我們關注結點的雙親，結點孩子，結點兄弟。可以擴充雙親域，長子域，右兄弟域。
存儲結構的設計是一個非常領過的過程，一個存儲結構設計的是否合理，取決于基于該存儲結構的運算是否适合，是否友善，時間複雜度好不好等。
2.孩子表示法
每個結點有多個指針域，其中每個指針指向一棵子樹的根結點，我們把這種方法叫做多重連結清單表示法。
方案一
指針域的個數就等于樹的度，複習一下，樹的度是樹各結點度的最大值。
data child1 child2 child3 child4 child5 。。。
data是資料域，child到childn 是指針域指向該結點的孩子結點。
因為各個結點的度不一樣 是以導緻有些結點度少的空了很多指針域
方案二
每個結點指針域的個數等于該結點的度，我們專門取一個位置來存儲結點指針域的個數。
data degree child1 child2 child3 。。。。。childn
data為資料域 degree為度域 也就是存儲該結點的孩子結點的個數 child1到childd為指針域，指向各個結點孩子的結點。
這種方法克服了浪費空間的缺點，對空間使用率提高了。
以上都是有些不足
孩子表示法：把每個結點的孩子結點排列起來，以單連結清單作存儲結構，則n個結點有n個孩子連結清單，如果是葉子結點則此單連結清單為空，然後n個頭指針又組成一個線性表，采用順序存儲結構，存放進一個一維數組中。
下标 data firstchild child next
0 A 1 2
1 B 3
2 C 4 5
3 D 6 7 8
4 E 9
5 F
6 G
7 H
8 I
9 J
為此，設計兩種結點結構，一個是孩子連結清單的孩子結點。
child next
其中child是資料域，用來存儲某個結點在表頭數組中的下标，next是指針域，用
來存儲指向某結點的下一個孩子結點的指針。
另一個是表頭數組的表頭結點
data firstchild
其中data是資料域，存儲某結點的資料資訊，firstchild是頭指針域，存儲該結點的孩子連結清單的頭指針。
樹的孩子表示法結構定義
#define MAX_TREE_SIZE 100
typedef struct CTNode 孩子結點
{
int child;
struct CTNode*next;
}*ChildPtr;
typedef struct 表頭結構
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct 樹結構
CTBox nodes[MAX_TREE_SIZE]; 結點數組
int r,n; 根的位置和結點數
}CTree;
把雙親表示法和孩子表示法結合 雙親孩子表示法，即在上面多一個parent一列
下标 data parent firstchild
孩子兄弟表示法
任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。是以，我們設定兩個指針，分别指向該結點的第一個孩子和此結點的右兄弟。
data firstchild rightsib
data是資料域，firstchild為指針域，存儲該結點的第一個孩子結點的存儲位址，rightsib是指針域，存儲該結點的右兄弟結點的存儲位址
樹的孩子兄弟表示法結構定義
typedef struct CSNode
struct CSNode * firstchild，*rightsib;
｝CSNode，*CSTree;
二叉樹的定義
二叉樹是n（n>=0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的，分别稱為根結點的左子樹和右子樹的二叉樹組成。
二叉樹的特點：
1.每個結點最多有兩棵子樹，是以二叉樹中不存在度大于2的結點，注意不是隻有兩棵子樹，而是最多有。沒有子樹或者有一棵子樹都是可以的
2.左子樹和右子樹是有順序的，次序不能任意颠倒。就像人是雙手，雙腳，但顯然左手，左腳和右手，右腳是不一樣的，右手戴左手套，右腳穿左鞋會極其别扭
3.即使樹中某結點隻有一棵子樹，也要區分它是左子樹還是右子樹。
二叉樹具有五種基本形态
1.空二叉樹
2.隻有一個根結點
3.根結點隻有左子樹
4.根結點隻有右子樹
5.根結點既有左子樹又有右子樹
如果有3個結點樹隻有2種情況
而如果是二叉樹 則有5種情況
特殊二叉樹：
1.斜樹
所有的結點都隻有左子樹的二叉樹叫左子樹，所有結點都是隻有右子樹的二叉樹叫做右斜樹。這兩種統稱為斜樹。
2.滿二叉樹
在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層，這樣的二叉樹稱為滿二叉樹
單是每個結點都存在左右子樹，不能算是滿二叉樹，還必須要所有的葉子都在同一層，這就做到了整棵樹的平衡。是以滿二叉樹的特點有：
1.葉子隻能出現在最下一層。出現在其他層就不能達成平衡
2.非葉子結點的度一定是2.否則就是缺胳膊少腿了
3.在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。
3.完全二叉樹
對一棵具有n個結點的二叉樹按層序編号，如果編号為i（1<=i<=n）的結點與同樣深度的滿二叉樹編号為i的結點在二叉樹中位置完全相同，則這課二叉樹稱為完全二叉樹
完全二叉樹的特點：
1.葉子結點隻能出現在最下兩層
2.最下層的葉子一定集中在左部連續位置
3.倒數二層，若有葉子結點，一定都在右部連續位置
4.如果結點度為1，則該結點隻有左孩子，即不存在隻有右子樹的情況。
5.同樣結點數的二叉樹，完全二叉樹的深度最小。
編号連續 逐層排号 如果斷了 就不是完全二叉樹
二叉樹的性質
性質1：在二叉樹的第i層上至多有2^i-1個結點（i>=1）。
性質2：深度為k的二叉樹至多有（2^k）-1個結點（k>=1）
性質3：對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2.則n0=n2+1 n0是度為2的結點數 n2是度為0的結點數
性質4：具有n個結點的完全二叉樹的深度為 以2為底n的對數+1
性質5：如果對一棵有n個結點的完全二叉樹的結點按照層序編号（從第一層到第深度 那層 每層從左到右），對任一結點i（1<=i<=n）
1。如果i=1，則結點i是二叉樹的根，無雙親;如果i>1，則其雙親是結點i/2
2.如果2i>n，則結點i無左孩子（結點i為葉子結點）;否則其左孩子是結點2i
3.如果2i+1>n，則結點i無右孩子;否則其右孩子是結點2i+1
二叉樹順序存儲結構
順序存儲一般隻用于完全二叉樹
二叉樹連結清單
二叉樹每個結點最多有2個孩子，是以為它設計一個資料域和兩個指針域。這樣的連結清單叫做二叉連結清單
lchild data rchild
data是資料域，lchild和rchild都是指針域，分别存放指向左孩子和右孩子的指針
二叉樹的二叉連結清單結點結構定義
typedef struct BiTNode 結點結構
TElemType data; 結點資料
struct BiTNode*lchild，*rchild; 左右孩子指針
｝BiTNode，*BiTree;
還可以增加一個指向其雙親的指針域，那樣就稱之為三叉連結清單。
周遊二叉樹
二叉樹周遊：是指從根結點出發，按照某種次序依次通路二叉樹中的所有結點，使得每個結點被通路一次且僅被通路一次。
二叉樹周遊方法
1.前序周遊
規則是若二叉樹為空，則空操作傳回，否則先通路根結點，然後在前序周遊左節點，再前序周遊右結點。
-------A--------
| |
B C-------
| | |
--------D E F
| | |
G H I
ABDGHCEIF
2.中序周遊
規則是若樹為空，則空操作傳回，否則從根結點開始（注意并不是先通路根結點），中序周遊根結點的左子樹，然後是通路根結點，最後中序周遊右子樹。
GDHBAEICF
3.後序周遊
規則是若樹為空，則空操作傳回，否則從左到右先葉子後結點的方式周遊通路左右子樹，最後通路根結點。
GHDBIEFCA
4.層序周遊
規則是若樹為空，則空操作傳回，否則從樹的第一層，也就是根結點開始通路，從上而下逐層周遊，在同一層中，按從左到右的順序對結點逐個通路。
ABCDEFGHI
前序周遊算法
void PreOrderTraverse（BiTree T）
if（T==NULL）
return;
printf（"%c"，T->data）; 顯示結點資料，可以更改為其他對結點操作
PreOrderTraverse（T->lchild）; 再先序周遊左子樹
PreOrderTraverse（T->rchild）; 最後先序周遊右子樹
｝
中序周遊算法
void InOrderTraverse（BiTree T）
InOrderTraverse（T->lchild）;中序周遊左子樹
print（"%c"，T->data）; 顯示結點資料，可以更改為其他對結點操作
InOrderTraverse(T->rchild); 最後中序周遊右子樹
後序周遊算法
void PostOrderTraverse（BiTree T）
PostOrderTraverse（T->lchild）;先後序周遊左子樹
PostOrderTraverse（T->rchild）;在後序周遊右子樹
Printf（"%c"，T->data）;顯示結點資料，可以更改為其他對結點操作
前序ABCDEF 中序 CBAEDF 後？CBEFDA
中序ABCDEFG 後序BDCAFGE 前？EACBDGF
二叉樹的建立
為了每個結點确認是否有左右孩子，我們對它進行擴充，也就是将二叉樹中每個結點的空指針引出一個虛結點，其值為一特定值，比如#，我們稱這種處理後的二叉樹為原二叉樹的擴充二叉樹。擴充二叉樹就可以做到一個周遊序列确定一棵二叉樹了。
例如 --------A-------
B C
--------- ---------
# D # #
--------
# #
前序周遊AB#D##C##
按前序輸入二叉樹中結點的值（一個字元）
#表示空樹，構造二叉連結清單表示二叉樹T
void CreateBiTree（BiTree *T）
TElemType ch;
scanf（"%c"，&ch）;
if（ch=='#'）
*T=NULL;
else
*T=（BiTree）malloc（sizeof（BiTNode））;
if（！*T）
exit（OVERFLOW）;
(*T)->data=ch; 生成根結點
CreateBiTree（&（*T）->lchild）; 構造左子樹
CreateBiTree（&（*T）->rchild）; 構造右子樹
線索二叉樹
我們把指向前驅和後繼的指針稱為線索，加上線索的二叉連結清單稱為線索連結清單，相應的二叉樹就稱為線索二叉樹
我們對二叉樹以某種次序周遊使其變為線索二叉樹的過程稱做是線索化
為每個結點增設标志域ltag和rtag，存放0或1布爾型變量。
lchild ltag data rtag rchild
ltag為0時指向該結點的左孩子，為1時指向該結點的前驅
rtag為0時指向該結點的右孩子，為1時指向該結點的後繼
線索二叉樹結構實作
typedef enum｛Link，Thread｝PointterTag; Link==0表示指向左右孩子指針 Thread==1表示指向前驅或後繼的線索
typedef struct BiThrNode 二叉線索存儲結點結構
TElemType data; 結點資料
struct BiThrNode *lchild，*rchild; 左右孩子指針
PointerTag LTag;
PointerTag RTag; 左右标志
｝BiThrNode，*BiThrTree;
線索化的實質就是将二叉連結清單中的空指針改為指向前驅或後繼的線索。由于前驅和後繼的資訊隻有在周遊該二叉樹時才能得到，是以線索化的過程就是周遊的過程中修改空指針的過程。
中序周遊線索化的遞歸函數：
BiThrTree pre;全局變量，始終指向剛剛通路過的結點
void InThreading（BiThrTree p）
if（p）
InThreading（p->lchild）;遞歸左子樹線索化
if（！p->lchild） 沒有左孩子
p->LTag=Thread; 前驅線索
p->lchild=pre; 左孩子指針指向前驅
if（！pre->rchild） 前驅沒有右孩子
pre->RTag=Thread; 後繼線索
pre->rchild=p; 前驅右孩子指針指向後繼（目前結點p）
pre=p; 保持pre指向p的前驅
InThreading（p->rchild）;遞歸右子樹索引
有了線索二叉樹後，我們對它進行周遊時發現，其實就等于是操作一個雙向連結清單結構。
和雙向連結清單結構一樣，在二叉樹線索連結清單上添加一個頭結點。并令其lchild域的指針指向二叉樹的根結點，其rchild域的指針指向中序周遊時通路的最後一個結點。反之，令二叉樹的中序序列中的第一個結點中，lchild域指針和最後一個結點的rchild域指針均指向頭結點，這樣定義的好處就是我們既可以從第一個結點起順後繼進行周遊，也可以從最後一個結點起順前驅進行周遊。
T指向頭結點，頭結點左鍊lchild指向根結點，頭結點右鍵rchild指向中序周遊的
最後一個結點，中序周遊二叉線索連結清單表示的二叉樹T
Status InOrderTraverse_Thr（BiThrTree T）
BiThrTree p;
p=T->lchild;
while（p!=T）
while（p->LTag==Link）
p=p->lchild;
printf（"%c"，p->data）;
while（p->RTag==Thread && p->rchild!=T）
p=p->rchild;
return OK;
如果所用的二叉樹需要經常周遊或查找結點時需要某種周遊序列中的前驅和後繼，那麼采用線索二叉連結清單的存儲結構就是非常不錯的選擇。
樹，森林與二叉樹的轉換
樹轉換為二叉樹步驟:
1.加線。 在所有兄弟結點之間加一條線
2.去線。 對樹中每個結點，隻保留它與第一個孩子結點的連線，删除它與其他孩子結點之間的連線。
3.層次調整。 以樹的根結點為軸心，講整棵樹順時針旋轉一定的角度，使之結構層次分明。注意第一個孩子是二叉樹結點的左孩子，兄弟轉換過來的孩子是結點的右孩子。
森林轉換成二叉樹
1.把每個樹轉換成二叉樹
2.第一棵二叉樹不動，從第二棵二叉樹開始，依次把後一顆二叉樹的根結點作為前一棵二叉樹的根結點的右孩子，用線連接配接起來。當所有的二叉樹連接配接起來後就得到了由森林轉換來的二叉樹。
二叉樹轉換為樹
1.加線。若某結點的左孩子結點存在，則将這個左孩子的右孩子結點，右孩子的右孩子結點，右孩子的右孩子的右孩子的結點，，右孩子結點都作為此結點的孩子。将該結點與這右孩子結點用線連接配接起來。
2.去線。 删除原二叉樹中所有結點與其右孩子結點的連線
3.層次調整。 使之結構層次分明
二叉樹轉換為森林
判斷一顆二叉樹能夠轉換成一棵樹還是森林，标準很簡單，那就是隻要看這棵二叉樹的根結點有沒有右孩子，有就是森林，沒有就是一棵樹。那麼如果是轉換成森林:
1.從根節點開始，若右孩子存在，則把與右孩子結點的連線删除，在檢視分離後的二叉樹，若右孩子存在，則連線删除。。。。直到所有右孩子連線都删除為止，得到分離的二叉樹。
2.再将每棵分離後的二叉樹轉換為樹
樹與森林的周遊
樹的周遊分為兩種方式:
1.一種是先根周遊樹，即先通路樹的根節點，然後依次先根周遊根的每棵子樹。
2，另一種是後根周遊，即先依次後根周遊每棵子樹，然後再通路根結點。
森林的周遊分為兩種方式:
1.前序周遊:先通路森林中第一棵樹的根結點，然後再依次先根周遊根的每棵子樹，在依次用同樣方式周遊除去第一棵樹的剩餘樹構成的森林。
2.後序周遊:是先通路森林中第一棵樹，後根周遊的方式周遊每棵子樹，然後再通路根結點，再依次同樣方式周遊除去第一棵樹的剩餘樹構成的森林。
當以二叉連結清單作樹的存儲結構時，樹的先根周遊和後根周遊完全可以借用二叉樹的前序周遊和中序周遊的算法實作。
霍夫曼樹定義與原理
我們先把二叉樹簡化成葉子結點帶權的二叉樹。
從樹中一個結點到另一個結點之間的分支構成兩個結點之間的路徑，路徑上的分支數目稱做路徑長度。
樹的路徑長度就是從樹根到每一結點的路徑長度之和。
結點的帶權的路徑長度為從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和。
本文轉自潘闊 51CTO部落格，原文連結：http://blog.51cto.com/pankuo/1631337，如需轉載請自行聯系原作者
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)