一 樹(shù)、二叉樹(shù)和二叉查找樹(shù)
1。樹(shù)的概念：
遞歸定義：
1） 一個(gè)空結(jié)構(gòu)是一個(gè)空樹(shù)
2）如果t1,...,tk是分離的樹(shù)，那么以t1,...,tk的根為子節(jié)點(diǎn)的根結(jié)構(gòu)也是樹(shù)
3）只有按照1，2規(guī)則產(chǎn)生的結(jié)構(gòu)才是樹(shù)
樹(shù)的概念更多用于分層結(jié)構(gòu)，比如數(shù)據(jù)庫(kù)管理系統(tǒng)的分層模型。
2。二叉樹(shù)（binary tree）：所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)（可以為空），并且每個(gè)子節(jié)點(diǎn)都指明為左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)
1）完全二叉數(shù)，滿足第i層，有2的i-1次方個(gè)子節(jié)點(diǎn)此條件的二叉樹(shù)
2）對(duì)于所有非空二叉樹(shù)，如果它的中間子節(jié)點(diǎn)恰好有兩個(gè)非空子女，那么葉的數(shù)目m大于中間節(jié)點(diǎn)的數(shù)目k，并且m=k+1
3。二叉查找樹(shù)（binary search tree)
1）概念：對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)n，其左子節(jié)點(diǎn)中保存的所有數(shù)值都小于n保存的數(shù)值，右子節(jié)點(diǎn)保存的數(shù)值都大于n保存的數(shù)值。
2）二叉查找樹(shù)可以實(shí)現(xiàn)更為優(yōu)越的查找性能，主要實(shí)現(xiàn)方式有數(shù)組和鏈表結(jié)構(gòu)，相比較而言，鏈表實(shí)現(xiàn)更為容易，因?yàn)閿?shù)組實(shí)現(xiàn)刪除和添加功能需要移動(dòng)數(shù)組元素（如填補(bǔ)刪除空位等）
?
二。二叉樹(shù)的實(shí)現(xiàn)
首先設(shè)計(jì)一個(gè)節(jié)點(diǎn)（設(shè)計(jì)一個(gè)整型的二叉樹(shù)，通用型通理）：
此類簡(jiǎn)單明了，一個(gè)信息值，兩個(gè)引用（左右子樹(shù)）。
public
?
class
?IntBSTNode?
{
?
protected
?
int
?key;
?
protected
?IntBSTNode?left,?right;
?
public
?IntBSTNode()?
{
??left?
=
?right?
=
?
null
;
?}
?
public
?IntBSTNode(
int
?el)?
{
??
this
(el,?
null
,?
null
);
?}
?
public
?IntBSTNode(
int
?el,?IntBSTNode?left,?IntBSTNode?right)?
{
??key?
=
?el;
??left?
=
?left;
??right?
=
?right;
?}
}
由此類而實(shí)現(xiàn)一個(gè)完整二叉搜索樹(shù)：
public
?
class
?IntBST?
{
?
protected
?IntBSTNode?root;
?
protected
?
void
?visit(IntBSTNode?p)?
{
??System.out.print(p.key?
+
?
"
?
"
);
?}
?
public
?IntBST()?
{
??root?
=
?
null
;
?}
第一步，實(shí)現(xiàn)二叉樹(shù)的搜索，查找過(guò)程簡(jiǎn)單明了，對(duì)每一個(gè)節(jié)點(diǎn)將要查找的鍵與當(dāng)前節(jié)點(diǎn)的數(shù)值比較，如果鍵小于該數(shù)，就進(jìn)入節(jié)點(diǎn)的左子樹(shù)繼續(xù)比較，反之進(jìn)入右子樹(shù)繼續(xù)此比較過(guò)程。
?
public
?IntBSTNode?search(
int
?el)?
{
??
return
?search(root,?el);
?}
?
protected
?IntBSTNode?search(IntBSTNode?p,?
int
?el)?
{
??
while
?(p?
!=
?
null
)
???
if
?(el?
==
?p.key)
????
return
?p;
???
else
?
if
?(el?
<
?p.key)
????p?
=
?p.left;
???
else
????p?
=
?p.right;
??
return
?
null
;
?}
此查找過(guò)程最壞情況，樹(shù)成為鏈表O(n)=(n-1)/2，最好情況：O(n)=lg(n+1)-2。經(jīng)過(guò)計(jì)算可知，一般樹(shù)的平均比較次數(shù)更接近于最好情況。
第二步，實(shí)現(xiàn)二叉樹(shù)的遍歷，樹(shù)的遍歷就是訪問(wèn)樹(shù)的所有節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)被訪問(wèn)一次。N個(gè)節(jié)點(diǎn)的樹(shù)有N！種不同的遍歷。我們只考慮兩種情況的遍歷
1）廣度優(yōu)先遍歷，是從最底層（或最高層）開(kāi)始逐層向上（或向下），而在同層自左向右（或者相反）訪問(wèn)每一個(gè)子節(jié)點(diǎn)，因此共有四種情況。考慮自頂向下，自左向右的情況，利用隊(duì)列實(shí)現(xiàn)如下：
?
public
?
void
?breadthFirst()?
{
??IntBSTNode?p?
=
?root;
??Queue?queue?
=
?
new
?Queue();
??
if
?(p?
!=
?
null
)?
{
???queue.enqueue(p);
???
while
?(
!
queue.isEmpty())?
{
????p?
=
?(IntBSTNode)?queue.dequeue();
????visit(p);
????
if
?(p.left?
!=
?
null
)
?????queue.enqueue(p.left);
????
if
?(p.right?
!=
?
null
)
?????queue.enqueue(p.right);
???}
??}
?}
?
2） 深度優(yōu)先遍歷，此種遍歷關(guān)心3個(gè)任務(wù)：
V——訪問(wèn)一個(gè)節(jié)點(diǎn)
L——遍歷左子樹(shù)
R——遍歷右子樹(shù)
因此有3！=6種此類遍歷，我們關(guān)心其中3種：
VLR——先序遍歷樹(shù)
LVR——中序遍歷樹(shù)
LRV——后序遍歷樹(shù)
如果用遞歸來(lái)實(shí)現(xiàn)這3種遍歷非常容易理解，如下：
public
?
void
?preorder()?
{
??preorder(root);
?}
//
先序
protected
?
void
?preorder(IntBSTNode?p)?
{
??
if
?(p?
!=
?
null
)?
{
???visit(p);
???preorder(p.left);
???preorder(p.right);
??}
?}
?
public
?
void
?inorder()?
{
??inorder(root);
?}
//
中序
protected
?
void
?inorder(IntBSTNode?p)?
{
??
if
?(p?
!=
?
null
)?
{
???inorder(p.left);
???visit(p);
???inorder(p.right);
??}
?}
?
public
?
void
?postorder()?
{
??postorder(root);
?}
//
后序
protected
?
void
?postorder(IntBSTNode?p)?
{
??
if
?(p?
!=
?
null
)?
{
???postorder(p.left);
???postorder(p.right);
???visit(p);
??}
?}
同樣，我們知道，遞歸調(diào)用總可以被迭代方式取代，只不過(guò)不是這么容易理解了，在此不再列出。
第三步。插入操作，此算法很簡(jiǎn)單，不詳細(xì)講解，簡(jiǎn)單來(lái)講就是找到合適的位置連接即可
public?void?insert(int?el)?{
????????IntBSTNode?p?=?root,?prev?=?null;
????????while?(p?!=?null)?{?//?find?a?place?for?inserting?new?node;
????????????prev?=?p;
????????????if?(p.key?<?el)
????????????????p?=?p.right;
????????????else
????????????????p?=?p.left;
????????}
????????if?(root?==?null)?//?tree?is?empty;
????????????root?=?new?IntBSTNode(el);
????????else?if?(prev.key?<?el)
????????????prev.right?=?new?IntBSTNode(el);
????????else
????????????prev.left?=?new?IntBSTNode(el);
????}
???
第四步。節(jié)點(diǎn)的刪除。
1）歸并刪除法，當(dāng)被刪除節(jié)點(diǎn)沒(méi)有或者只有一個(gè)子樹(shù)的時(shí)候很簡(jiǎn)單，當(dāng)有兩個(gè)子樹(shù)存在的時(shí)候，情況稍微復(fù)雜。歸并刪除法就是將節(jié)點(diǎn)的兩棵子樹(shù)合并成一棵樹(shù)，然后連接到節(jié)點(diǎn)的父節(jié)點(diǎn)上。歸并子樹(shù)的原則，尋找左子樹(shù)中key最大的節(jié)點(diǎn)，并將其作為右子樹(shù)的父節(jié)點(diǎn)。相反，也可以尋找右子樹(shù)的key最小的節(jié)點(diǎn)，作為左子樹(shù)的父節(jié)點(diǎn)。我們以第一種情況為例：
public?void?deleteByMerging(int?el)?{
????????IntBSTNode?tmp,?node,?p?=?root,?prev?=?null;
????????while?(p?!=?null?&&?p.key?!=?el)?{?//?find?the?node?p
????????????prev?=?p;?//?with?element?el;
????????????if?(p.key?<?el)
????????????????p?=?p.right;
????????????else
????????????????p?=?p.left;
????????}
????????node?=?p;
????????if?(p?!=?null?&&?p.key?==?el)?{
????????????if?(node.right?==?null)?//?node?has?no?right?child:?its?left
????????????????node?=?node.left;?//?child?(if?any)?is?attached?to?its?parent;
????????????else?if?(node.left?==?null)?//?node?has?no?left?child:?its?right
????????????????node?=?node.right;?//?child?is?attached?to?its?parent;
????????????else?{?//?be?ready?for?merging?subtrees;
????????????????tmp?=?node.left;?//?1.?move?left
????????????????while?(tmp.right?!=?null)
????????????????????//?2.?and?then?right?as?far?as
????????????????????tmp?=?tmp.right;?//?possible;
????????????????tmp.right?=?//?3.?establish?the?link?between?the
????????????????node.right;?//?the?rightmost?node?of?the?left
????????????????//?subtree?and?the?right?subtree;
????????????????node?=?node.left;?//?4.
????????????}
????????????if?(p?==?root)
????????????????root?=?node;
????????????else?if?(prev.left?==?p)
????????????????prev.left?=?node;
????????????else
????????????????prev.right?=?node;
????????}?else?if?(root?!=?null)
????????????System.out.println("key?"?+?el?+?"?is?not?in?the?tree");
????????else
????????????System.out.println("the?tree?is?empty");
????}
2）復(fù)制刪除法：歸并刪除法帶來(lái)的問(wèn)題是可能改變樹(shù)的高度。另一種刪除法也就是復(fù)制刪除法，將待刪除節(jié)點(diǎn)的key用它的前驅(qū)節(jié)點(diǎn)的key來(lái)代替，某一節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是該節(jié)點(diǎn)左子樹(shù)中key最大的節(jié)點(diǎn)。如下實(shí)現(xiàn)：
???
?public?void?deleteByCopying(int?el)?{
????????IntBSTNode?node,?p?=?root,?prev?=?null;
????????while?(p?!=?null?&&?p.key?!=?el)?{?//?find?the?node?p
????????????prev?=?p;?//?with?element?el;
????????????if?(p.key?<?el)
????????????????p?=?p.right;
????????????else
????????????????p?=?p.left;
????????}
????????node?=?p;
????????if?(p?!=?null?&&?p.key?==?el)?{
????????????if?(node.right?==?null)?//?node?has?no?right?child;
????????????????node?=?node.left;
????????????else?if?(node.left?==?null)?//?no?left?child?for?node;
????????????????node?=?node.right;
????????????else?{
????????????????IntBSTNode?tmp?=?node.left;?//?node?has?both?children;
????????????????IntBSTNode?previous?=?node;?//?1.
????????????????while?(tmp.right?!=?null)?{?//?2.?find?the?rightmost
????????????????????previous?=?tmp;?//?position?in?the
????????????????????tmp?=?tmp.right;?//?left?subtree?of?node;
????????????????}
????????????????node.key?=?tmp.key;?//?3.?overwrite?the?reference
????????????????if?(previous?==?node)?//?of?the?key?being?deleted;
????????????????????previous.left?=?tmp.left;?//?4.
????????????????else
????????????????????previous.right?=?tmp.left;?//?5.
????????????}
????????????if?(p?==?root)
????????????????root?=?node;
????????????else?if?(prev.left?==?p)
????????????????prev.left?=?node;
????????????else
????????????????prev.right?=?node;
????????}?else?if?(root?!=?null)
????????????System.out.println("key?"?+?el?+?"?is?not?in?the?tree");
????????else
????????????System.out.println("the?tree?is?empty");
????}
4。樹(shù)的平衡：如果樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差或者是0或者為1，那么這樣的二叉樹(shù)就是高度平衡的。如何平衡一棵樹(shù)？
1）簡(jiǎn)單算法：將樹(shù)中的所有數(shù)據(jù)中序遍歷，放進(jìn)一個(gè)數(shù)組，此數(shù)組已經(jīng)排序，然后折半插入
?public?void?balance(int?data[],?int?first,?int?last)?{
????????if?(first?<=?last)?{
????????????int?middle?=?(first?+?last)?/?2;
????????????System.out.print(data[middle]?+?"?");
????????????insert(data[middle]);
????????????balance(data,?first,?middle?-?1);
????????????balance(data,?middle?+?1,?last);
????????}
????}
???
2）DSW算法：
基本原理是通過(guò)樹(shù)的右旋轉(zhuǎn)得到樹(shù)的主干，然后再進(jìn)行左旋轉(zhuǎn)得到平衡樹(shù)