樹，這是一棵樹，這是一種非線性結(jié)構(gòu)。在前面我們所學(xué)習(xí)的都是線性結(jié)構(gòu)，而他們的特點是表中的元素相互之間都是線性關(guān)系，邏輯較為清晰，容易進行查找、插入和刪除操作，這種數(shù)據(jù)結(jié)構(gòu)描述的是一種元素只唯一前驅(qū)元素和唯一后繼元素的模型。
而樹這種非線性結(jié)構(gòu)是相對于線性結(jié)構(gòu)而言的，相比起線性結(jié)構(gòu)中元素之間一對一的關(guān)系，樹型結(jié)構(gòu)中元素之間是一對多的關(guān)系。樹是一種十分重要的非線性結(jié)構(gòu)。
樹的基本概念
樹的定義
樹是n（n>=0）個元素的的有限集合，既然被叫做樹，那么自然有根有葉子。在任何一顆非空樹中：
- 有且僅有一個節(jié)點被稱為根節(jié)點，而且我們一般把根節(jié)點提到整棵數(shù)的最上面
- 當(dāng)n>1時，除根以外的其余節(jié)點可一被分為m（m>0）個互不相交的有限集合T1，……,Tn,其中每一個集合本身又是一顆樹，并且稱為根的子樹
這真的是個很繞的東西，不過由此可以看出，樹的定義是具有遞歸性的，即樹中有樹，當(dāng)一顆樹只有一個節(jié)點時，該節(jié)點被稱為根節(jié)點。當(dāng)有多個節(jié)點時，除了根節(jié)點外，它還有多棵子樹，每棵子樹都互不相交。
樹的相關(guān)術(shù)語
一般而言，就像圖片描述的，圖中的圓圈代表節(jié)點，線代表邊，圈內(nèi)的東東就是這個節(jié)點的信息。
- 節(jié)點：樹中的數(shù)據(jù)元素稱為節(jié)點，每個節(jié)點都保存了該節(jié)點的信息，即數(shù)據(jù)元素和數(shù)據(jù)項與數(shù)據(jù)元素之間的關(guān)系
- 節(jié)點的度：節(jié)點擁有子樹的個數(shù)
- 樹的度：樹中各節(jié)點的度的最大值
- 葉子節(jié)點： 樹中度為0的節(jié)點，也叫做終端節(jié)點
- 分支節(jié)點： 樹中度不為0的節(jié)點，稱為分支節(jié)點或非終端節(jié)點
- 兒子：節(jié)點子樹的根，兒子節(jié)點簡稱為子節(jié)點
- 父親：有兒子的就是父親，父親節(jié)點簡稱為父節(jié)點
- 兄弟：有同一父親的節(jié)點被稱為兄弟節(jié)點
- 堂兄弟：位于同一層，但是沒有同一父親的子節(jié)點稱為堂兄弟
- 樹的深度：樹中節(jié)點節(jié)點的最大層數(shù)，圖中的樹深度為3
- 節(jié)點的層次：從根節(jié)點開始，根為第一層，根的孩子為第二層，以此類推，如果某節(jié)點在第k層，那么其子樹的根就在k+1層。
- 根：唯一一個沒有前驅(qū)的節(jié)點（無父節(jié)點），此節(jié)點為根節(jié)點
- 森林： 指m棵互不相交的樹的集合，一棵樹的子樹就構(gòu)成一個森林
- 有序樹： 如果樹中節(jié)點的各棵子樹規(guī)定從左至右是有序的（不能互換），則稱為有序樹，否則稱為無序樹。二叉樹就是一種有序樹。
- 無序樹：不是有序樹就是無序樹了（= =||），就是節(jié)點的各個子樹可以互換位置
二叉樹
樹型結(jié)構(gòu)中有一種特殊的樹叫做二叉樹，二叉樹的結(jié)構(gòu)也比較簡單，規(guī)律性較強，并且可以證明，即使一般的樹也能轉(zhuǎn)化成二叉樹。而且許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往就是二叉樹的形式。
二叉樹的定義
二叉樹是個有限元素的集合，該集合為空或者由一個根和兩個互不相交的左子樹和右子樹組成。在二叉樹中，一個元素也稱為一個節(jié)點。
二叉樹的基本特征：
- 每個節(jié)點最多只有兩棵子樹，即不存在度大于2的節(jié)點
- 左子樹和右子樹次序不能顛倒，即二叉樹是有序樹，而且哪怕只有
一顆子樹，也要區(qū)分是左子樹還是右子樹。
二叉樹有五中基本形態(tài)：
- 空集
- 根有兩顆子樹
- 根只有一顆子樹（左子樹或右子樹）
- 根沒有子樹
在二叉樹中有兩種特殊的二叉樹：滿二叉樹和完全二叉樹
滿二叉樹
在一棵樹中所有的分支節(jié)點都存在左子樹和右子樹，并且所有的葉子節(jié)點都在同一層上，這樣的二叉樹稱為滿二叉樹。
完全二叉樹
一棵深度為k且具有n個節(jié)點的二叉樹，對樹中節(jié)點按從上至下，從左至右的順序進行編號，當(dāng)且僅當(dāng)節(jié)點都與深度為k的滿二叉樹中編號從1至n的節(jié)點一一對應(yīng)
時，才稱這棵二叉樹為完全二叉樹。顯然滿二叉樹也是完全二叉樹的一種。
完全二叉樹的特點：
- 葉子節(jié)點只可能在層次最大的兩層上出現(xiàn)
-
對任一節(jié)點，其右分支下的兒子的最大層次為h，則其左分支下的兒子最大層次為
h或h+1
完全二叉樹
