java 二叉樹實(shí)現(xiàn)

　　樹的概述

　　樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，樹與前面介紹的線性表，棧，隊(duì)列等線性結(jié)構(gòu)不同，樹是一種非線性結(jié)構(gòu)

　　1.樹的定義和基本術(shù)語

　　計(jì)算機(jī)世界里的樹，是從自然界中實(shí)際的樹抽象而來的，它指的是N個(gè)有父子關(guān)系的節(jié)點(diǎn)的有限集合。對(duì)于這個(gè)有限的節(jié)點(diǎn)集合而言，它滿足如下條件：

　　當(dāng)N=0時(shí)，改節(jié)點(diǎn)集合為空，這課樹也被稱為空樹

　　在任意的非空樹中，有且僅有一個(gè)根（root）節(jié)點(diǎn)

　　當(dāng)N》1時(shí)，除根節(jié)點(diǎn)以外的其余節(jié)點(diǎn)可分為M個(gè)互為相交的有限集合T1，T2，…，Tm，其中的每個(gè)集合本身又是一棵樹，并稱其為根的子樹（subtree）。

　　從上面定義可以發(fā)現(xiàn)樹的遞歸特性：一棵樹由根和若干棵子樹組成，而每棵子樹又由若干棵更小的子樹組成。

　　樹中任一節(jié)點(diǎn)可以有0或多個(gè)子節(jié)點(diǎn)，但只能有一個(gè)父節(jié)點(diǎn)。根節(jié)點(diǎn)是一個(gè)特例，根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)。樹中每個(gè)節(jié)點(diǎn)既可以是其上一級(jí)節(jié)點(diǎn)的子節(jié)點(diǎn)，也可以是下一級(jí)節(jié)點(diǎn)的父節(jié)點(diǎn)，因此同一個(gè)節(jié)點(diǎn)既可以是父節(jié)點(diǎn)，也可以是子節(jié)點(diǎn)（類似于一個(gè)人—————他既是他兒子的父親，又是他父親的兒子）。

　　很顯然，父子關(guān)系是一種非線性關(guān)系，所以樹結(jié)構(gòu)是非線性結(jié)構(gòu)。

　　如果按節(jié)點(diǎn)是否包含子節(jié)點(diǎn)來分，節(jié)點(diǎn)可以分成以下兩種：

　　普通節(jié)點(diǎn)：包含子節(jié)點(diǎn)的節(jié)點(diǎn)

　　葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，因此葉子節(jié)點(diǎn)不可作為父節(jié)點(diǎn)

　　如果按節(jié)點(diǎn)是否具有唯一的父節(jié)點(diǎn)來分，節(jié)點(diǎn)有可分為如下兩種：

　　根節(jié)點(diǎn)：沒有父節(jié)點(diǎn)的節(jié)點(diǎn)，根節(jié)點(diǎn)不可作為子節(jié)點(diǎn)

　　普通節(jié)點(diǎn)：具有唯一父節(jié)點(diǎn)的節(jié)點(diǎn)

　　一棵樹只能有一個(gè)根節(jié)點(diǎn)，如果一棵樹有了多個(gè)根節(jié)點(diǎn)，那么它已經(jīng)不再是一棵樹了，而是多棵樹的集合，有時(shí)也被稱為森林。示意圖如下：

　　tree.PNG

　　tree.PNG

　　與樹有關(guān)的術(shù)語有如下一些：

　　節(jié)點(diǎn)：樹的最基本組成單元，通常包括一個(gè)數(shù)據(jù)元素及若干指針用于指向其他節(jié)點(diǎn)。

　　節(jié)點(diǎn)的度：節(jié)點(diǎn)擁有的子樹的個(gè)數(shù)被稱為節(jié)點(diǎn)的度（degree）

　　樹的度：樹中所有節(jié)點(diǎn)的度的最大值就是該樹的度

　　葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)被稱為葉子節(jié)點(diǎn)或終端節(jié)點(diǎn)

　　分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)被稱為分支節(jié)點(diǎn)或非終端節(jié)點(diǎn)

　　子節(jié)點(diǎn)，父節(jié)點(diǎn)，兄弟節(jié)點(diǎn)：節(jié)點(diǎn)的子樹的根被稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)，而該節(jié)點(diǎn)稱為子節(jié)點(diǎn)的父節(jié)點(diǎn)（parent）。具有相同父節(jié)點(diǎn)的子節(jié)點(diǎn)之間互稱為兄弟節(jié)點(diǎn)。

　　節(jié)點(diǎn)的層次（level）：節(jié)點(diǎn)的層次從根開始算起，根的層次值為1，其余節(jié)點(diǎn)的層次值為父節(jié)點(diǎn)層次值加l。

　　樹的深度（depth）：樹中節(jié)點(diǎn)的最大層次值稱為樹的深度或高度。

　　有序樹與無序樹：如果將樹中節(jié)點(diǎn)的各棵子樹看成從左到右是有序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。

　　祖先節(jié)點(diǎn)（ancestor）：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)

　　后代節(jié)點(diǎn)（descendant）：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的后代節(jié)點(diǎn)。

　　森林（forest）：森林是；兩顆或兩顆以上互不相交的樹的集合，刪去一棵樹的根，就得到一個(gè)森林。

　　樹的基本操作

　　如果需要實(shí)現(xiàn)一棵樹，程序不僅要以合適的方式保存該樹的所有節(jié)點(diǎn)，還要記錄節(jié)點(diǎn)與節(jié)點(diǎn)之間的父子關(guān)系。接下來，還應(yīng)該為樹實(shí)現(xiàn)如下基本操作。

　　初始化：通常是一個(gè)構(gòu)造器，用于創(chuàng)建一棵空樹，或者以指定節(jié)點(diǎn)為根來創(chuàng)建樹。

　　為指定節(jié)點(diǎn)添加子節(jié)點(diǎn)

　　判斷樹是否為空

　　返回根節(jié)點(diǎn)

　　返回指定節(jié)點(diǎn)（非根節(jié)點(diǎn)）的父節(jié)點(diǎn)

　　返回指定節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）的所有子節(jié)點(diǎn)

　　返回指定節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）的第i個(gè)子節(jié)點(diǎn)

　　返回該樹的深度

　　返回指定節(jié)點(diǎn)的位置

　　為了實(shí)現(xiàn)樹這種數(shù)據(jù)結(jié)構(gòu)，程序必須能記錄節(jié)點(diǎn)與節(jié)點(diǎn)之間的父子關(guān)系，為此有一下兩種選擇：

　　父節(jié)點(diǎn)表示法：每個(gè)子節(jié)點(diǎn)都記錄它的父節(jié)點(diǎn)。

　　子節(jié)點(diǎn)鏈表示法：每個(gè)非葉子節(jié)點(diǎn)通過一個(gè)鏈表來記錄它所有的子節(jié)點(diǎn)。

　　父節(jié)點(diǎn)表示法

　　通過前面的介紹可以發(fā)現(xiàn)，樹中除根節(jié)點(diǎn)之外的每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)。為了記錄樹中節(jié)點(diǎn)與節(jié)點(diǎn)之間的父子關(guān)系，可以為每個(gè)節(jié)點(diǎn)增加一個(gè)parent域，用以記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)。用如下圖和如下表來表示

　　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

　　… … …

　　由此可見，只要用一個(gè)節(jié)點(diǎn)數(shù)組來保存樹里的每個(gè)節(jié)點(diǎn)，并讓每個(gè)節(jié)點(diǎn)記錄其父節(jié)點(diǎn)在數(shù)組中的索引即可。

　　子節(jié)點(diǎn)鏈表表示法

　　父節(jié)點(diǎn)表示法的思想是讓每個(gè)節(jié)點(diǎn)“記住”它的父節(jié)點(diǎn)的索引，父節(jié)點(diǎn)表示法是從子節(jié)點(diǎn)著手的;反過來，還有另外一種方式：讓父節(jié)點(diǎn)“記住”它的所有子節(jié)點(diǎn)口在這種方式下，由于每個(gè)父節(jié)點(diǎn)需要記住多個(gè)子節(jié)點(diǎn)，因此必須采用“子節(jié)點(diǎn)鏈”表示法。示意圖如下：

　　tree_linked.PNG

　　tree_linked.PNG

　　二叉樹

　　二叉樹的定義和基本概念

　　二叉樹指的是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子樹的有序樹。通常左邊的子樹被稱作“左子樹”（left subtree），右邊的子樹被稱為“右子樹”（right subtree）。由此可見，二叉樹依然是樹，它是一種特殊的樹。

　　二叉樹的每個(gè)節(jié)點(diǎn)最多只有來兩顆樹（不存在度大于2的節(jié)點(diǎn)），二叉樹的子樹有左，右之分，次序不能顛倒。

　　樹和二叉樹的兩個(gè)重要區(qū)別如下：

　　樹中節(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹節(jié)點(diǎn)的最大度數(shù)為2，也就是說，二叉樹是節(jié)點(diǎn)的最大度數(shù)為2的樹。

　　無序樹的節(jié)點(diǎn)無左右之分，而二叉樹的節(jié)點(diǎn)有左，右之分，也就是說，二叉樹是有序樹。

　　一棵深度為k的二叉樹，如果它包含了

　　2^k-1

　　個(gè)節(jié)點(diǎn)，就把這棵二叉樹稱為滿二叉樹。滿二叉樹的特點(diǎn)是。每一層上的節(jié)點(diǎn)數(shù)都是最大節(jié)點(diǎn)數(shù)，即各層節(jié)點(diǎn)數(shù)分別為1，2，4，8， 16，…，滿二叉樹下圖所示：

　　two_tree.PNG

　　two_tree.PNG

　　一顆有n個(gè)節(jié)點(diǎn)的二叉樹，按滿二叉樹的編號(hào)方式對(duì)它進(jìn)行編號(hào)，若樹中所有節(jié)點(diǎn)和滿二叉樹1~n編號(hào)完全一致，則稱該樹為完全二叉樹。也就是說，如果一顆二叉樹除最后一層外，其余層的所有節(jié)點(diǎn)都是滿的，并且最后一層或者是滿的，或者僅在右邊缺少若干連續(xù)的節(jié)點(diǎn)，則此二叉樹就是完全二叉樹。

　　綜上所述，二叉樹大致有如下幾個(gè)性質(zhì)：

　　二叉樹第i層上的節(jié)點(diǎn)數(shù)據(jù)至多為2的i-1次方

　　深度為k的二叉樹至多有2的k次方-1個(gè)節(jié)點(diǎn)。滿二叉樹的每層節(jié)點(diǎn)的數(shù)量依次為1， 2， 4，8，…，因此深度為k的滿二叉樹包含的節(jié)點(diǎn)數(shù)為公比為2的等比數(shù)列的前k項(xiàng)總和，

　　即2的k次方一1。

　　在任何一棵二叉樹中，如果其葉子節(jié)點(diǎn)的數(shù)量為n0，度為2的子節(jié)點(diǎn)數(shù)量為n2，則

　　n0=n2 + 1。這是因?yàn)椋喝绻麨槿我馊~子節(jié)點(diǎn)增加一個(gè)子節(jié)點(diǎn)，則原有葉子節(jié)點(diǎn)變成非葉子節(jié)點(diǎn)，新增節(jié)點(diǎn)變成葉子節(jié)點(diǎn)，上述等式不變;如果為任意葉子節(jié)點(diǎn)增加兩個(gè)子節(jié)點(diǎn)，則原有葉子節(jié)點(diǎn)變成度為2的非葉子lto點(diǎn)，新增的兩個(gè)節(jié)點(diǎn)變成葉子節(jié)點(diǎn)，上述等式依然不變。

　　具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log2（n+1）

　　對(duì)于一顆具有n個(gè)節(jié)點(diǎn)的完全二叉樹的節(jié)點(diǎn)按層自左向右編號(hào)，則對(duì)任一編號(hào)為i（n》=i》=1）的節(jié)點(diǎn)有下列性質(zhì)。

　　當(dāng)i==1時(shí)，節(jié)點(diǎn)i是二叉樹的根；若i》1，則節(jié)點(diǎn)的父節(jié)點(diǎn)是i/2