java 二叉樹實現
樹的概述
樹是一種非常常用的數據結構，樹與前面介紹的線性表，棧，隊列等線性結構不同，樹是一種非線性結構
1.樹的定義和基本術語
計算機世界里的樹，是從自然界中實際的樹抽象而來的，它指的是N個有父子關系的節點的有限集合。對于這個有限的節點集合而言，它滿足如下條件：
當N=0時，改節點集合為空，這課樹也被稱為空樹
在任意的非空樹中，有且僅有一個根（root）節點
當N》1時，除根節點以外的其余節點可分為M個互為相交的有限集合T1，T2，…，Tm，其中的每個集合本身又是一棵樹，并稱其為根的子樹（subtree）。
從上面定義可以發現樹的遞歸特性：一棵樹由根和若干棵子樹組成，而每棵子樹又由若干棵更小的子樹組成。
樹中任一節點可以有0或多個子節點，但只能有一個父節點。根節點是一個特例，根節點沒有父節點，葉子節點沒有子節點。樹中每個節點既可以是其上一級節點的子節點，也可以是下一級節點的父節點，因此同一個節點既可以是父節點，也可以是子節點（類似于一個人—————他既是他兒子的父親，又是他父親的兒子）。
很顯然，父子關系是一種非線性關系，所以樹結構是非線性結構。
如果按節點是否包含子節點來分，節點可以分成以下兩種：
普通節點：包含子節點的節點
葉子節點：沒有子節點的節點，因此葉子節點不可作為父節點
如果按節點是否具有唯一的父節點來分，節點有可分為如下兩種：
根節點：沒有父節點的節點，根節點不可作為子節點
普通節點：具有唯一父節點的節點
一棵樹只能有一個根節點，如果一棵樹有了多個根節點，那么它已經不再是一棵樹了，而是多棵樹的集合，有時也被稱為森林。示意圖如下：
tree.PNG
tree.PNG
與樹有關的術語有如下一些：
節點：樹的最基本組成單元，通常包括一個數據元素及若干指針用于指向其他節點。
節點的度：節點擁有的子樹的個數被稱為節點的度（degree）
樹的度：樹中所有節點的度的最大值就是該樹的度
葉子節點：度為0的節點被稱為葉子節點或終端節點
分支節點：度不為0的節點被稱為分支節點或非終端節點
子節點，父節點，兄弟節點：節點的子樹的根被稱為該節點的子節點，而該節點稱為子節點的父節點（parent）。具有相同父節點的子節點之間互稱為兄弟節點。
節點的層次（level）：節點的層次從根開始算起，根的層次值為1，其余節點的層次值為父節點層次值加l。
樹的深度（depth）：樹中節點的最大層次值稱為樹的深度或高度。
有序樹與無序樹：如果將樹中節點的各棵子樹看成從左到右是有序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。
祖先節點（ancestor）：從根到該節點所經分支上的所有節點
后代節點（descendant）：以某節點為根的子樹中任一節點都稱為該節點的后代節點。
森林（forest）：森林是；兩顆或兩顆以上互不相交的樹的集合，刪去一棵樹的根，就得到一個森林。
樹的基本操作
如果需要實現一棵樹，程序不僅要以合適的方式保存該樹的所有節點，還要記錄節點與節點之間的父子關系。接下來，還應該為樹實現如下基本操作。
初始化：通常是一個構造器，用于創建一棵空樹，或者以指定節點為根來創建樹。
為指定節點添加子節點
判斷樹是否為空
返回根節點
返回指定節點（非根節點）的父節點
返回指定節點（非葉子節點）的所有子節點
返回指定節點（非葉子節點）的第i個子節點
返回該樹的深度
返回指定節點的位置
為了實現樹這種數據結構，程序必須能記錄節點與節點之間的父子關系，為此有一下兩種選擇：
父節點表示法：每個子節點都記錄它的父節點。
子節點鏈表示法：每個非葉子節點通過一個鏈表來記錄它所有的子節點。
父節點表示法
通過前面的介紹可以發現，樹中除根節點之外的每個節點都有一個父節點。為了記錄樹中節點與節點之間的父子關系，可以為每個節點增加一個parent域，用以記錄該節點的父節點。用如下圖和如下表來表示
tree_show.PNG
tree_show.PNG
數組索引 data parent
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 3
6 G 3
7 H 4
8 I 4
9 J 4
10 K 6
… … …
由此可見，只要用一個節點數組來保存樹里的每個節點，并讓每個節點記錄其父節點在數組中的索引即可。
子節點鏈表表示法
父節點表示法的思想是讓每個節點“記住”它的父節點的索引，父節點表示法是從子節點著手的;反過來，還有另外一種方式：讓父節點“記住”它的所有子節點口在這種方式下，由于每個父節點需要記住多個子節點，因此必須采用“子節點鏈”表示法。示意圖如下：
tree_linked.PNG
tree_linked.PNG
二叉樹
二叉樹的定義和基本概念
二叉樹指的是每個節點最多只能有兩個子樹的有序樹。通常左邊的子樹被稱作“左子樹”（left subtree），右邊的子樹被稱為“右子樹”（right subtree）。由此可見，二叉樹依然是樹，它是一種特殊的樹。
二叉樹的每個節點最多只有來兩顆樹（不存在度大于2的節點），二叉樹的子樹有左，右之分，次序不能顛倒。
樹和二叉樹的兩個重要區別如下：
樹中節點的最大度數沒有限制，而二叉樹節點的最大度數為2，也就是說，二叉樹是節點的最大度數為2的樹。
無序樹的節點無左右之分，而二叉樹的節點有左，右之分，也就是說，二叉樹是有序樹。
一棵深度為k的二叉樹，如果它包含了
2^k-1
個節點，就把這棵二叉樹稱為滿二叉樹。滿二叉樹的特點是。每一層上的節點數都是最大節點數，即各層節點數分別為1，2，4，8， 16，…，滿二叉樹下圖所示：
two_tree.PNG
two_tree.PNG
一顆有n個節點的二叉樹，按滿二叉樹的編號方式對它進行編號，若樹中所有節點和滿二叉樹1~n編號完全一致，則稱該樹為完全二叉樹。也就是說，如果一顆二叉樹除最后一層外，其余層的所有節點都是滿的，并且最后一層或者是滿的，或者僅在右邊缺少若干連續的節點，則此二叉樹就是完全二叉樹。
綜上所述，二叉樹大致有如下幾個性質：
二叉樹第i層上的節點數據至多為2的i-1次方
深度為k的二叉樹至多有2的k次方-1個節點。滿二叉樹的每層節點的數量依次為1， 2， 4，8，…，因此深度為k的滿二叉樹包含的節點數為公比為2的等比數列的前k項總和，
即2的k次方一1。
在任何一棵二叉樹中，如果其葉子節點的數量為n0，度為2的子節點數量為n2，則
n0=n2 + 1。這是因為：如果為任意葉子節點增加一個子節點，則原有葉子節點變成非葉子節點，新增節點變成葉子節點，上述等式不變;如果為任意葉子節點增加兩個子節點，則原有葉子節點變成度為2的非葉子lto點，新增的兩個節點變成葉子節點，上述等式依然不變。
具有n個節點的完全二叉樹的深度為log2（n+1）
對于一顆具有n個節點的完全二叉樹的節點按層自左向右編號，則對任一編號為i（n》=i》=1）的節點有下列性質。
當i==1時，節點i是二叉樹的根；若i》1，則節點的父節點是i/2
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%