樹是n(n>=0)個結(jié)點的有限集瘦锹，n=0時稱為空樹，在任意一顆非空樹中：
- 有且只有一個特定的稱為根(Root)的結(jié)點
- 當n > 1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2...Tm沼本，其中每一個集合本身又是一棵樹噩峦，并且稱為根的子樹(SubTree)
- 結(jié)點擁有的子樹稱為結(jié)點的度(Degree)，度為0的結(jié)點稱為葉結(jié)點(Leaf)或終端結(jié)點抽兆，度不為0的結(jié)點稱為分支結(jié)點或非終端結(jié)點，除根節(jié)點之外族淮，分支結(jié)點也稱為內(nèi)部結(jié)點辫红，樹的度是樹內(nèi)各結(jié)點的度的最大值
- 結(jié)點的子樹的根稱為該結(jié)點的孩子(Child)，該結(jié)點稱為孩子的雙親(Parent)祝辣，同一個雙親的孩子之間互稱兄弟(Sibling)贴妻，結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫
- 結(jié)點的層次：根為第一層蝙斜，根的孩子為第二層名惩，雙親在同一層的結(jié)點互為堂兄弟，樹中結(jié)點的最大層次稱為樹的深度(Depth)或高度
- 如果將樹中結(jié)點的各子樹看成從左至右是有順序的孕荠，不能互換的 娩鹉，則該樹稱為有序樹，否則稱為無序樹
- 森林是m(m>=0)棵互不相交的樹的集合
樹的存儲結(jié)構(gòu)
簡單的順序存儲結(jié)構(gòu)是不能滿足樹的實現(xiàn)要求的稚伍，但結(jié)合鏈式存儲結(jié)構(gòu)可以滿足
雙親表示法
除了根結(jié)點弯予，每個結(jié)點一定且僅有一個雙親
- 雙親表示法結(jié)點定義：在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在數(shù)組中的位置，即一個數(shù)據(jù)域个曙、一個指針域(存放雙親下標)
- 可以靈活擴展此結(jié)構(gòu)锈嫩，把指針域擴展為長子域、右兄弟域等
- 一個存儲結(jié)構(gòu)設(shè)計的是否合理垦搬，取決于基于該存儲結(jié)構(gòu)的運算是否合適呼寸、方便、時間復(fù)雜度好壞等
孩子表示法
每個結(jié)點有多個指針域猴贰，其中每個指針指向一棵子樹的根結(jié)點对雪，這稱為多重鏈表表示法，有兩種方案：
- 指針域的個數(shù)就等于樹的度糟趾；對于樹中各結(jié)點的度相差很大時會浪費空間
- 是專門取一個位置(度域)來存儲結(jié)點指針域的個數(shù)慌植；各結(jié)點的鏈表結(jié)構(gòu)不同，損耗運算時間
結(jié)合該兩種方案做到既可以減少空指針的浪費又能使結(jié)點結(jié)構(gòu)相同义郑，即孩子表示法蝶柿，具體為：
- 把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表做存儲結(jié)構(gòu)非驮，則n個結(jié)點有n個孩子鏈表交汤，葉子節(jié)點為空表
- n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進一個一維數(shù)組中
如此一來芙扎，要查找某個結(jié)點的某個孩子或兄弟星岗，只需要查找這個結(jié)點的孩子單鏈表即可
如果還想知道某個結(jié)點的雙親是誰，可以結(jié)合雙親表示法戒洼，形成雙親孩子表示法
孩子兄弟表示法
- 任何一棵樹俏橘，它的結(jié)點的第一個孩子如果存在，就是唯一的圈浇，它的右兄弟如果存在也是唯一的寥掐。因此設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟
- 孩子兄弟表示法結(jié)構(gòu)定義：數(shù)據(jù)域磷蜀、兩個指針域(指向該結(jié)點的第一個孩子結(jié)點召耘、指向右兄弟結(jié)點)
二叉樹
由n個結(jié)點組成的有限集合，該集合或為空集(空二叉樹)褐隆，或由一個根結(jié)點和兩棵互不相交污它、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成
特點：
- 每個結(jié)點最多有兩棵子樹(0~2棵)
- 左子樹和右子樹的次序不能變
- 只有一棵子樹時也要區(qū)分左右子樹
二叉樹的五種基本形態(tài)：空二叉樹、只有根結(jié)點庶弃、只有左子樹衫贬、只有右子樹、有左右子樹
特殊二叉樹：
- 斜樹：每一層都只有一個結(jié)點虫埂，結(jié)點的個數(shù)與二叉樹的深度相同祥山；分左斜樹和右斜樹
- 滿二叉樹：所有葉子都在最底層；分支結(jié)點的度一定是2掉伏；與同深度的二叉樹比缝呕，滿二叉樹的結(jié)點和葉子數(shù)最多
- 完全二叉樹：按層序編號，如果編號沒出現(xiàn)空檔(存在的結(jié)點位置和同條件的滿二叉樹的位置相同)則是斧散；葉結(jié)點只能在最后兩層供常，與同深度的二叉樹比，完全二叉樹的深度最小
二叉樹的性質(zhì)
- 性質(zhì)1：在二叉樹的第i層上至多有2^(i-1)個結(jié)點(i>=1)
- 性質(zhì)2：深度為k的二叉樹至多有(2^k)-1個結(jié)點 (k>=1)
- 性質(zhì)3：葉結(jié)點數(shù)=度為2的結(jié)點數(shù)+1(通過推導(dǎo)總結(jié)點數(shù)和分支線總數(shù)得出)
- 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為[log2n]+1(性質(zhì)2的倒推)
- 性質(zhì)5：對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層編號鸡捐，對任一結(jié)點i有：
- 若i=1栈暇，則i是根結(jié)點，無雙親箍镜；若i>1源祈，則雙親是結(jié)點i/2
- 若2i>n，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)色迂；否則其左孩子是結(jié)點2i
- 若2i+1>n香缺，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1
二叉樹的存儲結(jié)構(gòu)
順序存儲結(jié)構(gòu)：用一維數(shù)組存儲二叉樹中結(jié)點歇僧，對一般的二叉樹不能反應(yīng)邏輯關(guān)系图张；一般用于完全二叉樹
二叉鏈表：由結(jié)點數(shù)據(jù)(數(shù)據(jù)域)、左右孩子指針(兩個指針域)定義的鏈表；若再加一個指向雙親的指針域就稱為三叉鏈表
遍歷二叉樹
指從根結(jié)點出發(fā)祸轮，按照某種次序依次訪問二叉樹中所有結(jié)點兽埃，使得每個結(jié)點被訪問一次且僅被訪問一次
前序遍歷算法：
先前序遍歷左子樹，再前序遍歷右子樹
/* 用C實現(xiàn)二叉樹的前序遍歷遞歸算法*/
void PreOrder(BiTree T)
{
if (T == NULL)
return;
printf("%c", T->data); /*對結(jié)點的操作*/
PreOrder(T->lchild)
PreOrder(T->rchild)
}
中序遍歷算法：
先中序遍歷根結(jié)點的左子樹适袜，然后訪問根結(jié)點柄错，最后中序遍歷右子樹
與前序遍歷相比相當于把調(diào)用左孩子的遞歸函數(shù)提前了
遍歷到左孩子為NULL的結(jié)點時才返回對結(jié)點操作，然后再對該結(jié)點的右子樹做同樣遍歷
/* 用C實現(xiàn)二叉樹的中遍歷遞歸算法*/
void InOrder(BiTree T)
{
if (T == NULL)
return;
InOrder(T->lchild) /*提前*/
printf("%c", T->data); /*對結(jié)點的操作*/
InOrder(T->rchild)
}
后序遍歷算法：
從左到右的順序先遍歷葉子再遍歷結(jié)點的方式遍歷訪問左右子樹
/* 用C實現(xiàn)二叉樹的后遍歷遞歸算法*/
void PostOrder(BiTree T)
{
if (T == NULL)
return;
PostOrder(T->lchild) /*先左*/
PostOrder(T->rchild) /*再右*/
printf("%c", T->data); /*對結(jié)點的操作*/
}
