722
數據結構之二叉樹
一 樹、二叉樹和二叉查找樹
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); } }
文章轉自莊周夢蝶 ，原文發布時間5.17
2）DSW算法：
基本原理是通過樹的右旋轉得到樹的主幹，然後再進行左旋轉得到平衡樹
最後更新：2017-05-17 11:35:36