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