以此文記錄學習 數(shù)據(jù)結構-樹 的相關知識狸窘，以備后續(xù)回顧復習欺殿。
一、樹
定義：
樹（Tree）是n（n>=0)個結點的有限集立美。n=0時稱為空樹。在任意一顆非空樹中：
1). 有且僅有一個特定的稱為根（Root）的結點方灾；
2). 當n>1時建蹄，其余結點可分為m(m>0)個互不相交的有限集T1、T2裕偿、......洞慎、Tn，其中每一個集合本身又是一棵樹嘿棘，并且稱為根的子樹劲腿。
相關概念：
- 結點的度：一個結點含有的子樹的個數(shù)稱為該結點的度；
- 樹的度：一棵樹中鸟妙，最大結點的度稱為樹的度焦人；
- 樹的層次：樹中根結點為第1層，根結點的孩子結點是第二層重父，以此類推花椭；
- 樹的深度/高度：樹中結點的最大層次稱為樹的深度或高度；
- 葉節(jié)點或終端結點：度為0的結點稱為葉結點房午；
- 雙親結點或父結點： 若一個結點含有子節(jié)點矿辽，則這個結點稱為其子結點的父結點；
- 孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點郭厌；
- 兄弟結點：具有相同父結點的結點互稱為兄弟結點袋倔；
- 堂兄弟結點：雙親在同一層的結點互稱為堂兄弟；
- 結點的祖先：從根結點到該結點多經過分支上的所有結點沪曙；
- 子孫：以某結點為根的子樹任一結點都稱為該結點的子孫奕污；
- 森林：由m根互不相交的樹的集合稱為森林；
表示方法：
- 雙親表示法：
在每個結點中液走，附設一個指示器指示其雙親結點到鏈表中的位置碳默。
結點結構為：data | parent
其中data是數(shù)據(jù)域贾陷，存儲結點的數(shù)據(jù)信息。而parent是指針域嘱根，存儲該結點的雙親在數(shù)組中的下標髓废。
由于根結點是沒有雙親的，所以約定根結點的位置域設置為-1. - 孩子表示法：
把每個結點的孩子結點排列起來该抒，以單鏈表作存儲結構慌洪，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空凑保，然后n個頭指針又組成一個線性表冈爹，采用順序存儲結構，存放進一個一維數(shù)組中欧引。
為此频伤，設計兩種結點結構：
一個是孩子鏈表的孩子結點， child | next
其中child是數(shù)據(jù)域芝此，用來存儲某個結點在表頭數(shù)組中的下標憋肖。next是指針域，用來存儲指向某結點的下一個孩子結點的指針婚苹。
另一個是表頭數(shù)組的表頭結點岸更， data | firstchild
其中data是數(shù)據(jù)域，存儲某結點的數(shù)據(jù)信息膊升。firstchild是頭指針域怎炊，存儲該結點的孩子鏈表的頭指針。 - 孩子兄弟表示法：
任意一棵樹用僧，它的結點的第一個孩子如果存在就是唯一的结胀，它的右兄弟如果存在也是唯一的赞咙。因此责循，我們設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟攀操。
結點結構如表所示：
data | firstchild | rightsib
其中data是數(shù)據(jù)域院仿，first child為指針域，存儲該結點的第一個孩子結點的存儲地址速和，rightsib是指針域歹垫，存儲該結點的右兄弟結點的存儲地址。
二颠放、二叉樹
定義：
二叉樹是n(n>=0)個結點的有限集合排惨，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的碰凶、分別稱為根結點的左子樹和右子樹組成暮芭。
特點：
- 每個結點最多有兩顆子樹鹿驼，所以二叉樹中不存在度大于2的結點。
- 左子樹和右子樹是有順序的辕宏，次序不能任意顛倒畜晰。
- 即使樹中某結點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹瑞筐。
五種基本形態(tài)：
1.空二叉樹凄鼻。
2.只有一個根結點。
3.根結點只有左子樹聚假。
4.根結點只有右子樹块蚌。
5.根結點既有左子樹又有右子樹。
二叉樹的性質
性質1：在二叉樹的第i層上至多有2∧(i-1)個結點（i>=1)膘格。
性質2：深度為k的二叉樹至多有(2∧k) -1個結點（k>=1)匈子。
性質3：對任何一棵二叉樹T，如果其終端結點數(shù)為n0闯袒，度為2的結點數(shù)為n2虎敦，則n0=n2+1。
性質4：具有n個結點的完全二叉樹的深度為[log2n]+1 ([x]表示不大于x的最大整數(shù)政敢。
性質5：如果對一棵有n個結點的完全二叉樹（其深度為[log2n]+1) 的結點按層序編號（從第1層到[log2n]+1層其徙，每層從左到右），對任一節(jié)點i(1≦i≦n)有：
- 如果i=1,則結點i是二叉樹的根喷户，無雙親唾那；如果i>1, 則其雙親是結點[i/2]。
- 如果2i>n, 則結點i無左孩子（結點i為葉子結點）褪尝；否則其左孩子是結點2i闹获。
- 如果2i+1>n, 則結點i無右孩子；否則其右孩子是結點2i+1河哑。
二叉樹的存儲結構
二叉樹的順序存儲結構：
二叉樹的順序存儲結構就是用一維數(shù)組存儲二叉樹中的結點避诽，并且結點的存儲位置，也就是數(shù)組的下標要能體現(xiàn)結點之間的邏輯關系璃谨。
順序存儲結構一般只用于完全二叉樹沙庐。二叉鏈表（鏈式存儲結構）
二叉樹每個結點最多有兩個孩子，所以為它設計一個數(shù)據(jù)域和兩個指針域是比較自然的想法佳吞，我們稱這樣的鏈表叫做二叉鏈表拱雏。
二叉樹遍歷方法:
1.前序遍歷：規(guī)則是若二叉樹為空，則空操作返回底扳，否則先訪問根結點铸抑，然后前序遍歷左子樹，再前序遍歷右子樹衷模。
2.中序遍歷：規(guī)則是若樹為空鹊汛，則空操作返回菇爪，否則從根結點開始（注意并不是先訪問根結點），中序遍歷根結點的左子樹柒昏，然后是訪問根結點凳宙，最后中序遍歷右子樹。
3.后序遍歷：規(guī)則是若樹為空职祷，則空操作返回氏涩，否則從左到右先葉子后結點的方式遍歷訪問左右子樹，最后是訪問根結點有梆。
4.層序遍歷：規(guī)則是若樹為空是尖，則空操作返回，否則從樹的第一層泥耀，也就是根結點開始訪問饺汹，從上而下逐層遍歷，在同一層中痰催，按從左到右的順序對結點逐個訪問兜辞。
*前序遍歷算法：
//二叉樹的前序遍歷遞歸算法
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c", T->lchild); /*顯示結點數(shù)據(jù)，可以更改為其他對結點操作*/
PreOrderTraverse(T->lchild); /*再先序遍歷左子樹*/
PreOrderTraverse(T->rchild); /*最后先序遍歷右子樹*/
}
``
*中序遍歷算法：
/*二叉樹的中序遍歷遞歸算法*/
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /*中序遍歷左子樹*/
printf("%c", T->data); /*顯示結點數(shù)據(jù)夸溶，可以更改為其他對結點操作*/
InOrderTraverse(T->rchild); /*最后中序遍歷右子樹*/
}
*后序遍歷算法：
/*二叉樹的后序遍歷遞歸算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /*先后序遍歷左子樹*/
PostOrderTraverse(T->rchild); /*再后續(xù)遍歷右子樹*/
printf("%c", T->data); /*顯示結點數(shù)據(jù)逸吵，可以更改為其他對結點操作*/
}
- 已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹缝裁。
已知后序遍歷序列和中序遍歷序列扫皱，可以唯一確定一棵二叉樹。
二叉樹的建立：
建立二叉樹捷绑，也是利用了遞歸的原理韩脑。只不過在原來應該是打印結點的地方，改成了生成結點粹污，給結點賦值的操作而已段多。
對二叉樹進行拓展：將二叉樹中每個結點的空指針引出一個虛節(jié)點，其值唯一特定值厕怜，比如”#“衩匣。
用前序遍歷生成二叉樹：
/*按前序輸入二叉樹中結點的值（一個字符）*/
/** #表示空樹，構造二叉鏈表表示二叉樹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); /*構造右子樹*/
}
}
線索二叉樹
- 對于一個有n個結點的兒茶鏈表，每個結點有指向左右孩子的兩個指針域生百，所以一共是2n個指針域递雀。而n個結點的二叉樹一共有n-1條分支線數(shù)，也就是說蚀浆，其實是存在2n-1(n-1)=n+1個空指針域缀程。
線索二叉樹：指向前驅和后繼的指針稱為線索搜吧，加上線索的二叉鏈表稱為線索鏈表，相應的二叉樹就稱為線索二叉樹杨凑。
線索二叉樹滤奈，等于是把一棵二叉樹轉變成了一個雙向鏈表。
對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱作是線索化撩满。
線索二叉樹結構實現(xiàn)：
/*二叉樹的二叉線索存儲結構定義*/
typedef enum(Link,Thread) PointerTag; /*Link==0表示指向左右孩子指針*/
/*Thread==1表示指向前驅或后繼的線索*/
typedef struct BiThrNode /*二叉樹線索存儲結點結構*/
{
TElemType data; /*結點數(shù)據(jù)*/
struct BiThrNode *lchild, *rchild; /*左右孩子指針*/
PointerTag LTag;
PointerTag RTag; /*左右標志*/
}BiThrNode, *BiThree;
線索化的實質就是將二叉鏈表中的空指針改為指向前驅或后繼的線索蜒程。由于前驅和后繼的信息只有在遍歷該二叉樹時才能得到，所以線索化的過程就是在遍歷的過程中修改空指針的過程伺帘。
線索二叉樹的時間復雜度為O(n).
如果所用的二叉樹需經常遍歷或查找結點時需要某種遍歷序列中的前驅和后繼昭躺，那么采用線索二叉鏈表的存儲結構就是非常不錯的選擇。
特殊二叉樹：
斜樹：所有的結點都只有左子樹的二叉樹叫左斜樹伪嫁。所有結點都是只有右子樹的二叉樹叫右斜樹领炫。這兩者統(tǒng)稱為斜樹。
滿二叉樹：在一棵二叉樹中张咳。如果所有分支結點都存在左子樹和右子樹帝洪，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹脚猾。
滿二叉樹的特點有：
- 葉子只能出現(xiàn)在嘴下一層碟狞。出現(xiàn)在其它層就不可能達成平衡。
- 非葉子結點的度一定是2婚陪。
- 在同樣深度的二叉樹中族沃，滿二叉樹的結點個數(shù)最多，葉子數(shù)最多泌参。
- 完全二叉樹：對一顆具有n個結點的二叉樹按層編號脆淹，如果編號為i(1<=i<=n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹沽一。
完全二叉樹的特點：
- 滿二叉樹一定是一棵完全二叉樹盖溺，但完全二叉樹不一定是滿的。
葉子結點只能出現(xiàn)在最下兩層铣缠。
最下層的葉子一定集中在左部連續(xù)位置烘嘱。
倒數(shù)二層，若有葉子結點蝗蛙，一定都在右部連續(xù)位置蝇庭。
如果結點度為1，則該結點只有左孩子捡硅，即不存在只有右子樹的情況哮内。
同樣結點的二叉樹，完全二叉樹的深度最小壮韭。
判斷某二叉樹是否是完全二叉樹：
給每個結點按照二叉樹的結構逐層順序編號北发，如果編號出現(xiàn)空擋纹因，就說明不是完全二叉樹，否則就是琳拨。
樹瞭恰、森林與二叉樹的轉換
樹轉換為二叉樹
- 加線。在所有兄弟結點之間加一條連線狱庇。
- 去線惊畏。對樹中每個結點，只保留它與第一個孩子結點的連線僵井，刪除它與其他孩子結點之間的連線陕截。
- 層次調整。以樹的根結點為軸心批什，將整棵樹順時針旋轉一定的角度农曲，使之結構層次分明。注意第一個孩子是二叉樹結點的左孩子驻债，兄弟轉換過來的孩子是結點的右孩子乳规。
森林轉換為二叉樹
- 把每個樹轉換為二叉樹。
- 第一棵二叉樹不動合呐，從第二棵二叉樹開始暮的，依次把后一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子，用線連接起來淌实。當所有的二叉樹連接起來后就得到了由森林轉換來的二叉樹冻辩。
二叉樹轉換為樹
- 加線。若某結點的右孩子存在拆祈，則將做左孩子的n各右孩子結點都作為此結點的孩子恨闪。將該結點與這些右孩子結點用線連接起來。
- 去線放坏。刪除原二叉樹中所有結點與其右孩子結點的連線咙咽。
- 層次調整。使之結構層次分明淤年。
- 判斷一棵二叉樹能夠轉換成一棵樹還是森林钧敞，就是只要看這棵二叉樹的根結點有沒有右孩子，有就是森林麸粮，沒有就是一棵樹溉苛。
二叉樹轉換為森林
- 從根結點開始，若右孩子存在豹休，則把與右孩子結點的連線刪除炊昆，在查看分離后的二叉樹，若右孩子存在威根，則連線刪除凤巨，直到所有右孩子連線都刪除為止，得到分離的二叉樹洛搀。
- 再將每棵分離后的二叉樹轉換為樹即可敢茁。
樹與森林的遍歷
樹的遍歷的兩種方式:
- 一種是先根遍歷樹，即先訪問樹的根結點留美，然后依次先根遍歷根的每棵子樹彰檬。
- 另一種是后根遍歷，即先依次后根遍歷每棵子樹谎砾，然后再訪問根結點逢倍。
森林的遍歷也分為兩種方式：
- 前序遍歷：先訪問森林中第一棵樹的根結點，然后再依次縣根遍歷根的每棵子樹景图，再依次用同樣方式遍歷除去第一棵樹的剩余樹構成的森林较雕。
- 后序遍歷：是先訪問森林中第一棵樹，后根遍歷的方式遍歷每棵子樹挚币，然后再訪問根結點亮蒋，再依次同樣方式遍歷除去第一棵樹的剩余樹構成的森林。
- 當以二叉樹做作樹的存儲結構時妆毕，樹的先根遍歷和后根遍歷完全可以借用二叉樹的前序遍歷和中序遍歷的算法來實現(xiàn)慎玖。
以上。
