樹的基本概念：
- 樹的定義：樹是一種非線性結構
-
樹的基本術語：
結點：結點不僅包含資料元素，而且包含指向子樹的分支。
結點的度：結點擁有的子樹個數或者分支的個數。
樹的度：樹中各結點度的最大值。
葉子結點：又叫做終端結點，指度為0的結點。
非終端結點：又叫做分支結點，指度不為0的結點。
孩子：結點的子樹的根。
-
樹的存儲結構：
順序結構：雙親存儲結構——用一維數組就可以實作。
鍊式存儲結構：
孩子存儲
孩子兄弟存儲結構：
- 二叉樹
二叉樹基本性質與二叉樹的周遊
1、 每個結點最多隻有兩棵子樹，即二叉樹中結點的度隻能為0.1.2；
2、 子樹有左右順序之分，不能颠倒。
-
二叉樹的形态：
1、 空二叉樹
2、 隻有根節點
3、 隻有左子樹
4、 隻有右子樹
5、 左右子樹都有。
二叉樹基本性質與二叉樹的周遊 - 特殊的二叉樹：
滿二叉樹：在一棵二叉樹中，如果所有的分支結點都有左右孩子的結點，并且葉子結點都集中在二叉樹的最下一層，則這樣的二叉樹稱為滿二叉樹。
完全二叉樹：如果對一棵深度為k、有n個結點的二叉樹進行編号後，各結點的編号與深度為k的滿二叉樹中的相同位置上的結點的編号均相同，那麼這棵二叉樹就是一棵完全二叉樹。
-
二叉樹的性質：
1、非空二叉樹上葉子結點數等于雙分支結點數加1.（由于二叉樹除了根結點之外，每個結點都有唯一的一個分支指向它，是以二叉樹中有總分支樹=總結點數-1）
拓展：在一棵度為m的樹中，度為1的結點數為n1,度為2的結點數為n2,…，度為m的結點數位nm,則葉子結點數n0=1+n2+2*n3+…+（m-1）*nm,
推導過程：
總結點數=n0+n1+n2+n3+…+nm;
總分支數=1n1+2n2+3n3+…+mnm;(度為m的結點引出m條分支)
總分支數=總結點數-1；
-
例：在一棵度數為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點的個數是(B)
A、41
B、82
C、113
D、122
解析：
直接引用上述葉結點的公式n0=1+n2+2n3+(4-1)n4=1+1+210+320=82
不僅僅适用于二叉樹。
-
例：在一棵三叉樹中，度為3的結點數位2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點（葉子）數為（C）
A、4
B、5
C、6
D、7
2、二叉樹的第i層上最多有2^(i-1)(i≥1)個結點。
3、深度為k的二叉樹最多有2^k-1
個節點.(滿二叉樹中前k層的結點個數為2^k-1。
4、若i為某個結點a的編号，則：
如果i≠1，則a的雙親結點的編号為
如果2 i≤n，則a的左孩子的編号為2i；如果2i>n,則a無左孩子。
如果2i+1 i≤n，則a的右孩子編号為2i+1；如果2i+1>n，則a無右孩子。
例：如圖，n=5，結點B編号為2，22=4<5,則編号為4的結點D為結點B的左孩子；22+1=5,則編号為5的結點E。
5、給定n個結點，能構成h(n)種不同的二叉樹，h(n)=C(n,2*n)/(n+1) .
6、具有n個結點的完全二叉樹的高度(或深度)為[logn]+1。
- 二叉樹的存儲結構
鍊式存儲：
結構類型定義：
typedef struct BTNode
{
char data;//這裡預設結點data域為char型
struct BTNode *lchild;//左指針域
struct BTNode *rchild;//右指針域
} BTNode;
-二叉樹的周遊（周遊就是全部走遍）。
先序周遊：
周遊過程：根->左->右
根：A
左：有BDE三個結點
{BDE:
根：B
左：D
右：E
}
右：有CF兩個結點
{CF：
根：C
左：空
右：F
}
故先序周遊：ABDECF
設二叉樹中元素數目為n，先序周遊算法的空間複雜性均為O (n)，時間複雜性為(n)。
中序周遊（LDR）
周遊過程：左->根->右
左：BDE
{
左：D
根：B
右：E
}
根：A
右：CF
{
左：F
根：C
右：空
}
中序周遊：DBEAFC
設二叉樹中元素數目為n，中序周遊算法的空間複雜性均為O (n)，時間複雜性為(n)。
後序周遊：
周遊過程：左->右->根
左：BDE
{
左：D
右：E
根：B
}
右：CF
{
左：F
右：空
根：C
}
根：A
後序周遊：DEBFCA
例：表達式(a-(b+c))*(d/e)存儲在圖所示的一棵以二叉連結清單為存儲結構的二叉樹中(二叉樹結點的data域為字元型)，編寫程式求出改表達式的值。
分析：
可以把二叉樹分為三個部分，左子樹(a-(b+c))為表達式A,右子樹(d/e)為B，先求左子樹的值，再求右子樹的值，最後兩式結果相乘就是整個表達式的數值。
可以用後序周遊來完成：
int comp(BTNode *P)
{
int A,B;
if (P!=NULL)
{
if (P->lchild!=NULL&&P->rchild!=NULL)
{
A=comp(P->lchild);
B=comp(P->rchild);
return op(A,B,P->data);
}
else
return P->data-'0';
}
else return 0;
}
說明：函數int op(int A，int B,char C)傳回的是以C為運算符，以A,B為操作數的算式的數值，例如C為“+“，則傳回為A+B的值。
例題：一棵二叉樹的先序周遊序列為A,B,C,D,E,F,中序周遊序列為C,B,A,E,D,F,則後序周遊為（A）
A、C,B,E,F,D,A
B、F,E,D,C,B,A
C、C,B,E,D,F,A
D、不确定
解析：先序：根左右，根A；中序：左根右，左{CB}右{EDF} 後序：左右根，左{CB}，右{EFD}，根A
-
線索二叉樹：二叉樹被線索化後近似于一個線性結構，分支結構的周遊操作就轉化為了近似于線性結構的周遊操作，通過線索的輔助使得尋找目前結點前驅或者後繼的平均效率大大提高。
指向前驅或後繼的指針稱為線索。
1、 中序線索二叉樹
ltag、rtag為辨別域。 二叉樹基本性質與二叉樹的周遊
如果Itag=0,則表示lchild為指針，指向結點的左孩子；
如果Itag=1，則表示lchild為線索，指向結點的直接前驅。
如果rtag=0，則表示rchild為指針，指向結點的右孩子；
如果rtag=1，則表示rchild為線索，指向結點的直接後繼
線索二叉樹的結點定義：
typedef struct TBTNode{
char data;
int ltag,rtag;
struct TBTNode *lchild;
struct TBTNode *rchild;
}TBTNode;
中序線索化的規則：
左線索指針指向目前結點在中序周遊序列中的前驅結點，右線索指針指向後繼結點。是以我們需要一個指針p指向目前正在通路的結點，pre指向p的前驅結點，p的左線索指針如果存在的話直接指向pre（也就是前驅結點），pre的右線索如果存在則指向p（也就是直接後繼）。
優勢
(1)利用線索二叉樹進行中序周遊時，不必采用堆棧處理，速度較一般二叉樹的周遊速度快，且節約存儲空間。
(2)任意一個結點都能直接找到它的前驅和後繼結點。
不足
(1)結點的插入和删除麻煩，且速度也較慢。
(2)線索子樹不能共用。