什么是樹：

樹是n（n>=0）個結點的有限集。n=0時稱為空樹。在任意一棵非空樹中：

• 有且僅有一個特定的稱為根的結點
• 當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1、T2、......、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹
• 樹的度：即選取整個樹中，出現最大分支的數量為整個樹的度
• 結點間的關系：左右分支稱為結點的孩子，而結點稱為左右分支的雙親，左右分支又互稱為兄弟，祖先則是表示從根到該節點所經分支上的所有結點，同一層結點但不同分支稱為堂兄弟。

樹的表示：

雙親表示法：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?data? | ? parent

其中parent列用雙親的編號表示

孩子表示法：? ? ? ? ? ? ? ? ? ? ? ? ? ?data | child1 | child2 | child3 | ..... | childn

下圖是鏈表表示方法：

孩子雙親表示法：以上圖為基礎加上一列表示雙親編號

孩子兄弟表示法：? ? ? ? ? ? ? ? ? ? ? ? ? ?data?| firstchild | rightsilb

二叉樹：

二叉樹是n（n>=0）個結點的有限集合（最多有兩個結點），該集合或者為空集（稱為空二叉樹）。或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

特殊二叉樹：

斜樹：呈現出來是一條直線的樹

滿二叉樹：

完全二叉樹： 葉子從左向右排序的形態

用數組表示：

• 推論：對于位置為K的結點 左子結點=2*k+1，右子結點=2*（k+1）
• 推論：最后一個非葉結點的位置為（N/2）-1，N為數組長度

二叉樹表示：

data | leftchild?| rightchild