樹的定義
樹是一種遞歸數(shù)據(jù)結(jié)構(gòu)，它有n個節(jié)點的有限集合T恕曲，在一棵樹中有且僅有一個稱為根的節(jié)點谴轮，其余節(jié)點可分為m個互不相交的集合T1,T2,···,Tm,其中醇滥，每一個集合本身又是一棵樹挂洛，并稱為根的子樹礼预。
度：樹中每個節(jié)點具有的子樹數(shù)或者后繼節(jié)點數(shù)稱為該節(jié)點的度。一棵樹中各節(jié)點度數(shù)的最大值稱為這個樹的度
深度：樹是層次結(jié)構(gòu)抹锄，一顆樹中最大層數(shù)稱為此樹的深度或高度。
森林：n個樹的集合稱為森林荠藤。
樹狀結(jié)構(gòu)的邏輯特征：樹中任一節(jié)點都可以有0個或多個直接后繼節(jié)點伙单，但至多只能有一個直接前驅(qū)節(jié)點。樹中只有開始節(jié)點無前趨哈肖，是開始節(jié)點吻育。葉節(jié)點無后繼，則是終端節(jié)點淤井。
二叉樹
二叉樹是有限元素的集合布疼，該集合或者為空，或者由一個稱為根元素及兩個不相交的被稱為左子樹和右子樹的二叉樹組成币狠，當集合為空時游两，稱該二叉樹為空二叉樹。
所有分支節(jié)點都有左子樹和右子樹漩绵，并且所有葉子節(jié)點都在同一層上贱案，這樣一顆二叉樹稱為滿二叉樹。
葉子節(jié)點只出現(xiàn)在最下層和次下層止吐，且最下層的葉子節(jié)點集中在樹的左部的二叉樹稱為完全二叉樹宝踪。
二叉樹是有序的侨糟，左右子樹顛倒，就成為另一顆不同的二叉樹瘩燥，即使只有一顆子樹秕重，也要區(qū)分他是左子樹還是右子樹。
樹和二叉樹的區(qū)別
沒有空樹有空二叉樹厉膀。
樹子樹直接沒序琼开，二叉樹子樹之間有序囱桨。
二叉樹最多只能有兩個子樹。
二叉樹有以下幾個性質(zhì)：TODO(上標和下標)
二叉樹性質(zhì)
- 在二叉樹的第ｉ（ｉ>=１）層最多有２＾(ｉ - １)個結(jié)點。
- 深度為k(k>=0)的二叉樹最少有k個結(jié)點泵喘，最多有２＾ｋ－１個結(jié)點。
- 對于任一棵非空二叉樹拄丰，若其葉結(jié)點數(shù)為n0蝇棉，度為2的非葉結(jié)點數(shù)為n2，則ｎ0 = ｎ2 ＋１澜倦。
- 具有n個結(jié)點的完全二叉樹的深度為int_UP（log(2聚蝶，ｎ+1)）。
- 如果將一棵有n個結(jié)點的完全二叉樹自頂向下藻治，同一層自左向右連續(xù)給結(jié)點編號１碘勉，２，３桩卵，．．．．．．验靡，ｎ，然后按此結(jié)點編號將樹中各結(jié)點順序的存放于一個一維數(shù)組雏节，并簡稱編號為i的結(jié)點為結(jié)點i（ ｉ>=１ && ｉ<=ｎ）,則有以下關系：
（1）若 ｉ= 1胜嗓，則結(jié)點i為根，無父結(jié)點钩乍；若 ｉ> 1辞州，則結(jié)點 i 的父結(jié)點為結(jié)點int_DOWN（ｉ / ２）;
（2）若 ２＊ｉ <= ｎ，則結(jié)點 ｉ 的左子女為結(jié)點 ２＊ｉ寥粹；
（3）若２＊ｉ＜＝ｎ变过，則結(jié)點ｉ的右子女為結(jié)點２＊ｉ＋１；
（4）若結(jié)點編號ｉ為奇數(shù)涝涤，且ｉＣ恼＝１，它處于右兄弟位置阔拳，則它的左兄弟為結(jié)點ｉ－１哈雏；
（5）若結(jié)點編號ｉ為偶數(shù)，且ｉ！＝ｎ裳瘪，它處于左兄弟位置土浸，則它的右兄弟為結(jié)點ｉ＋１；
（6）結(jié)點ｉ所在的層次為 int_DOWN（log（2彭羹，ｉ））＋１黄伊。
二叉樹的存儲結(jié)構(gòu)
滿二叉樹和完全二叉樹可采取順序存儲，非完全二叉樹派殷，采用鏈式存儲更好还最。
