莊周夢蝶

一 樹、二叉樹和二叉查找樹

1。樹的概念：

遞歸定義：

1） 一個空結構是一個空樹

2）如果t1,...,tk是分離的樹，那么以t1,...,tk的根為子節點的根結構也是樹

3）只有按照1，2規則產生的結構才是樹

樹的概念更多用于分層結構，比如數據庫管理系統的分層模型。

2。二叉樹（binary tree）：所有節點都有兩個子節點（可以為空），并且每個子節點都指明為左子節點還是右子節點

1）完全二叉數，滿足第i層，有2的i-1次方個子節點此條件的二叉樹

2）對于所有非空二叉樹，如果它的中間子節點恰好有兩個非空子女，那么葉的數目m大于中間節點的數目k，并且m=k+1

3。二叉查找樹（binary search tree)

1）概念：對于樹中的每個節點n，其左子節點中保存的所有數值都小于n保存的數值，右子節點保存的數值都大于n保存的數值。

2）二叉查找樹可以實現更為優越的查找性能，主要實現方式有數組和鏈表結構，相比較而言，鏈表實現更為容易，因為數組實現刪除和添加功能需要移動數組元素（如填補刪除空位等）

?

二。二叉樹的實現

首先設計一個節點（設計一個整型的二叉樹，通用型通理）：

此類簡單明了，一個信息值，兩個引用（左右子樹）。

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;
?}
}

由此類而實現一個完整二叉搜索樹：

public ? class ?IntBST? {
? protected ?IntBSTNode?root;

? protected ? void ?visit(IntBSTNode?p)? {
??System.out.print(p.key? + ? " ? " );
?}

? public ?IntBST()? {
??root? = ? null ;
?}

第一步，實現二叉樹的搜索，查找過程簡單明了，對每一個節點將要查找的鍵與當前節點的數值比較，如果鍵小于該數，就進入節點的左子樹繼續比較，反之進入右子樹繼續此比較過程。

?

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 ;
?}

此查找過程最壞情況，樹成為鏈表O(n)=(n-1)/2，最好情況：O(n)=lg(n+1)-2。經過計算可知，一般樹的平均比較次數更接近于最好情況。

第二步，實現二叉樹的遍歷，樹的遍歷就是訪問樹的所有節點，且每個節點被訪問一次。N個節點的樹有N！種不同的遍歷。我們只考慮兩種情況的遍歷

1）廣度優先遍歷，是從最底層（或最高層）開始逐層向上（或向下），而在同層自左向右（或者相反）訪問每一個子節點，因此共有四種情況。考慮自頂向下，自左向右的情況，利用隊列實現如下：

?

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） 深度優先遍歷，此種遍歷關心3個任務：

V——訪問一個節點

L——遍歷左子樹

R——遍歷右子樹

因此有3！=6種此類遍歷，我們關心其中3種：

VLR——先序遍歷樹

LVR——中序遍歷樹

LRV——后序遍歷樹

如果用遞歸來實現這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);
??}
?}

同樣，我們知道，遞歸調用總可以被迭代方式取代，只不過不是這么容易理解了，在此不再列出。

第三步。插入操作，此算法很簡單，不詳細講解，簡單來講就是找到合適的位置連接即可

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);
????}

???
第四步。節點的刪除。
1）歸并刪除法，當被刪除節點沒有或者只有一個子樹的時候很簡單，當有兩個子樹存在的時候，情況稍微復雜。歸并刪除法就是將節點的兩棵子樹合并成一棵樹，然后連接到節點的父節點上。歸并子樹的原則，尋找左子樹中key最大的節點，并將其作為右子樹的父節點。相反，也可以尋找右子樹的key最小的節點，作為左子樹的父節點。我們以第一種情況為例：

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）復制刪除法：歸并刪除法帶來的問題是可能改變樹的高度。另一種刪除法也就是復制刪除法，將待刪除節點的key用它的前驅節點的key來代替，某一節點的前驅節點就是該節點左子樹中key最大的節點。如下實現：
???

?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。樹的平衡：如果樹中任何節點的兩個子樹的高度差或者是0或者為1，那么這樣的二叉樹就是高度平衡的。如何平衡一棵樹？
1）簡單算法：將樹中的所有數據中序遍歷，放進一個數組，此數組已經排序，然后折半插入

?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算法：
基本原理是通過樹的右旋轉得到樹的主干，然后再進行左旋轉得到平衡樹