1. 樹
1. 樹的定義
樹（Tree）：是n（n>=0）個節(jié)點的有限集，它或為空樹（n=0）狸驳；或為非空樹预明，對于非空樹T： a.有且僅有一個稱之為根的節(jié)點； b.除根節(jié)點以外的其余節(jié)點可分為m個互不相干的有限集T1,T2,…..Ti,Tm,其中每一個集合本身又是一顆樹耙箍，并稱之為根的子樹（SubTree）撰糠。
樹的結(jié)構(gòu)是遞歸的定義，樹的定義中又有樹的定義辩昆，這是樹的固有特性阅酪；
2. 基礎(chǔ)術(shù)語
- 結(jié)點：樹中的一個獨立單元。
- 結(jié)點的度：結(jié)點擁有的子樹數(shù)稱為結(jié)點的度。
- 樹的度：樹內(nèi)各結(jié)點度的最大值术辐。
- 葉子：度為0的結(jié)點稱為葉子或終端結(jié)點砚尽。
- 非終端結(jié)點：度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。除根結(jié)點之外辉词，非終端結(jié)點也稱為內(nèi)部結(jié)點必孤。
- 雙親和孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)地瑞躺，該結(jié)點稱為孩子的雙親敷搪。
- 兄弟：同一個雙親的孩子之間互稱兄弟。
- 祖先：從根結(jié)點到該結(jié)點所經(jīng)分支上的所有結(jié)點隘蝎。
- 子孫：以某結(jié)點為根的子樹種的任一結(jié)點都稱為該結(jié)點的子孫购啄。
- 層次：結(jié)點的層次從根開始定義起，根為第一層嘱么，根的孩子為第二層狮含。樹中任意結(jié)點的層次等于其雙親結(jié)點層次加1。
- 堂兄弟：其雙親在同一層的結(jié)點互為堂兄弟曼振。
- 樹的深度：樹中結(jié)點的最大層次稱為樹的深度或高度.
- 有序樹和無序樹：如果將樹中結(jié)點的各個子樹看成從左至右是有次序的（即不能護換）几迄，則稱該樹為有序樹，否則為無序樹冰评，在有序樹中最左邊的子樹的根稱為第一個孩子映胁，右邊的稱為最后一個孩子.
- 森林：是m顆互不相干的樹的集合。對樹中的每個結(jié)點而言甲雅，其子樹的集合為森林解孙。
就邏輯結(jié)構(gòu)而言：任何一顆樹都是一個二元組（Tree=（root,F））,其中root為根幾點，F(xiàn)為m顆樹的森林抛人。
RF = {<root,ri>|i=1,2,3,4,.....m,m>0}
該定義有助于得到深林和樹與二叉樹之間轉(zhuǎn)換的遞歸定義弛姜。
2. 二叉樹
二叉樹是一種特殊的樹結(jié)構(gòu)，其存儲和處理比一般的樹要簡單妖枚，且一般的樹可以通過轉(zhuǎn)換得到與之對應(yīng)的二叉樹廷臼，這樣就可以采用二叉樹的存儲結(jié)構(gòu)和相關(guān)算法來解決樹的相關(guān)問題。
1. 二叉樹的定義（Binary tree）:
二叉樹是n個結(jié)點所構(gòu)成的集合绝页，它或為空樹荠商，或為非空樹，對于非空樹T：
1.有且僅有一個稱之為根的結(jié)點：
2.除根結(jié)點以外的其余結(jié)點分為兩個互不相交的子集T1和T2续誉，分別稱為T的左子樹和右子樹莱没，且都是二叉樹。
2. 二叉樹與樹的區(qū)別:
1.二叉樹每個結(jié)點至多有兩顆子樹（即二叉樹中不存在度大于2的結(jié)點）酷鸦；
2.二叉樹的子樹有左右之分饰躲，切次序不能任意顛倒朴译。
3. 二叉樹的性質(zhì)**
1.在二叉樹的第i層上最多有2i-1個結(jié)點。
2.深度為k的二叉樹至多有2k-1個結(jié)點属铁。
3.對任何一顆二叉樹T，如果其終端結(jié)點數(shù)為n0
,度為2的結(jié)點數(shù)為n2則n0=n2+1躬翁；
4. 特殊二叉樹
滿二叉樹：深度為k且含有2k-1個結(jié)點的二叉樹焦蘑；
完全二叉樹：深度為k且有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)i每一個結(jié)點都與深度為k的滿二叉樹中編號從1-n的結(jié)點一一對應(yīng)時盒发，稱為完全二叉樹例嘱。
完全二叉樹特點：
1.葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；
2.對任一結(jié)點宁舰，若其右分支下的子孫的最大層次為l拼卵，其左分支下的子孫的最大層次必為l或l+1。
性質(zhì)：
1.具有n個結(jié)點的完全二叉樹的深度為[log2n]+1蛮艰。
2.如果對一顆有n個結(jié)點的完全二叉樹的結(jié)點按層序編號腋腮，則對任一結(jié)點i有：
a.如果i=1，則結(jié)點i是二叉樹的根壤蚜，無雙親即寡；
b.如果i>1,則其雙親PARENT（i）是結(jié)點i/2；
c.如果2i>n,則結(jié)點i無左孩子袜刷，否則其左孩子LCHILD(i)是結(jié)點2i聪富；
d.如果2i+1>n,則結(jié)點i無右孩子，否則其右孩子RCHILD(i)是結(jié)點2i+1著蟹；
5. 二叉樹的存儲結(jié)構(gòu)
可采用：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)兩種墩蔓；
順序存儲結(jié)構(gòu):一般適用于完全二叉樹（因為使用順序存儲會浪費空間），所以二叉樹通常還是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)萧豆。 引出另一種鏈?zhǔn)酱鎯?線索鏈表奸披。
遍歷二叉樹
1.遍歷二叉樹（traversing binary tree）：指按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次炕横，而且僅被訪問一次源内。
先序遍歷：
1.訪問根結(jié)點；
2.先序遍歷左子樹份殿；
3.先序遍歷右子樹膜钓。
中序遍歷：
1.中序遍歷左子樹；
2.訪問根結(jié)點卿嘲；
3.中序遍歷右子樹颂斜。
后序遍歷：
1.后序遍歷左子樹；
2.后序遍歷右子樹拾枣；
3.訪問根結(jié)點沃疮。
線索二叉樹
有時間再寫
