樹基本的含義
樹（tree）是包含n（n>0）個結點的有窮集，其中：
（1）每個元素稱為結點（node）砾医；
（2）有一個特定的結點被稱為根結點或樹根（root）锨匆。
（3）除根結點之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的集合T1新思，T2，……Tm-1猪叙，其中每一個集合Ti（1<=i<=m）本身也是一棵樹娇斩，被稱作原樹的子樹（subtree）。
樹也可以這樣定義：樹是由根結點和若干顆子樹構成的穴翩。樹是由一個集合以及在該集合上定義的一種關系構成的犬第。集合中的元素稱為樹的結點，所定義的關系稱為父子關系芒帕。父子關系在樹的結點之間建立了一個層次結構歉嗓。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點背蟆，或稱為樹根鉴分。
我們可以形式地給出樹的遞歸定義如下:
單個結點是一棵樹哮幢，樹根就是該結點本身。
設T1,T2,..,Tk是樹志珍，它們的根結點分別為n1,n2,..,nk橙垢。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹伦糯，結點n就是新樹的根柜某。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點敛纲。我們還稱T1,T2,..,Tk為結點n的子樹喂击。
空集合也是樹，稱為空樹淤翔〔训龋空樹中沒有結點。
二叉樹
在計算機科學中办铡，二叉樹是每個節(jié)點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）琳要。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆寡具。
二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分稚补，次序不能顛倒童叠。二叉樹的第i層至多有2{i-1}個結點；深度為k的二叉樹至多有2k-1個結點课幕；對任何一棵二叉樹T厦坛，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2乍惊，則n0=n2+1杜秸。
一棵深度為k，且有2^k-1個節(jié)點稱之為滿二叉樹润绎；深度為k撬碟，有n個節(jié)點的二叉樹，當且僅當其每一個節(jié)點都與深度為k的滿二叉樹中莉撇，序號為1至n的節(jié)點對應時呢蛤，稱之為完全二叉樹。
二叉樹的性質
性質1：二叉樹第i層上的結點數(shù)目最多為 2i-1 (i≥1)棍郎。
性質2：深度為k的二叉樹至多有2k-1個結點(k≥1)其障。
性質3：包含n個結點的二叉樹的高度至少為log2 (n+1)。
性質4：在任意一棵二叉樹中涂佃，若終端結點的個數(shù)為n0励翼，度為2的結點數(shù)為n2蜈敢，則n0=n2+1。
二叉樹的存儲
順序存儲
與線性表的順序存儲類似抚笔，二叉樹的順序存儲結構一般也由一個一維數(shù)組來呈現(xiàn)扶认。
