二叉搜索樹的Java實現

為了更加深入了解二叉搜索樹，本人用Java寫了個二叉搜索樹，有興趣的同學可以一起探討探討。

　　首先，二叉搜索樹是啥？它有什麼用呢？

　　二叉搜索樹， 也稱二叉排序樹，它的每個節點的數據結構為1個父節點指針，1個左孩子指針，1個有孩子指針，還有就是自己的數據部分了，因為只有左右兩孩子，所以才叫二叉樹，在此基礎上，該二叉樹還滿足另外一個條件：每個結點的左孩子都不大於該結點&&每個結點的右孩子都大於該結點。這樣，我們隊這棵樹進行中序遍歷，就能把key從小到大排序了……

　　那麼問題來了，我都有線性表有鏈表了，我還要它干啥？兩個字！效率！

　　相比線性表，你要搜索一個key，就要執行一次線性時間，算法復雜度為O(n)；而用二叉搜索樹，算法效率是O(lgn)！這是很誘人的數字。下面我用Java實現以下二叉搜索樹，你自然就明白為什麼算法復雜度是O(lgn)了。

　　其次，寫一個數據結構，自然而然也要實現對這個數據結構的增、刪、查、改了。

　　下面是我的思路：

 

1. 創建樹：我是通過一個一個結點的插入來建立一棵二叉搜索樹。
2. 搜索結點：從根節點開始，進行key的比較，小了就往左走，大了就往右走，最後到了葉子結點都還沒有的話，那麼該樹就不存在要搜索的結點了。
3. 修改結點：修改其實就是查詢，在查詢之後把結點的數據部分給改了而已，這裡我就不重復去實現了。
4. 刪除結點：這個應該就是最難的了，所以我有必要詳細講，先上圖（不好意思，懶得用軟件畫圖了，將就將就下哈）：

當我們要刪除一個結點時，分如下幾種情況：

• 此結點是葉子結點，這個最簡單啦，直接把結點給釋放掉就行了。（如圖刪除9）
• 此結點只有左孩子，這個也簡單啦，直接把左子樹替換過來就行了。（如圖刪除3）
• 此結點只有右孩子，同上。（如圖刪除8）
• 此結點有左右孩子，當出現這種情況時（如圖刪除7），我們就要找出該結點的後繼結點（因為右子樹肯定存在，所以找肯定在右子樹中），然後把這個後繼結點替換到要刪除的結點中，然後繼續執行對這個後繼結點的刪除操作（遞歸刪除操作就行了）。

  　　發現沒？現在我的解題思路是自頂向下去分析……自頂向下，逐級求精是一個很偉大的思想！   　　現在問題來了！後繼結點怎麼求？我們來分析一下，當求一個結點的後繼結點時，分為以下兩種情況：

• 當該結點有右孩子時，後繼結點就在右子樹中，就是該右子樹的最小結點
• 當該結點沒有右孩子時，那後繼結點就滿足這個條件：該後繼結點是該結點的祖先&&該結點位於該結點的左子樹中（如圖中的9的後繼結點是12）

　　哎呀呀！問題又來了！最小結點咋辦！很簡單！ 　　當求一棵樹的最小結點時，那麼就要從這顆樹的根節點開始，一直往左子樹走，就能找到它的最小結點了！ 　　好了，現在問題逐步解決了！刪除結點的功能也就完成了！ 　　最後，沒代碼說個錘子，咱上代碼！   首先，寫個測試類：

 public class Test {
    public static void main(String[] args) {
        int[] datas={12,4,5,7,4,8,3,2,6,9};
        BinTree tree=new BinTree(datas);
        tree.preOrderTraverse();//先序遍歷
        tree.midOrderTraverse();//中序遍歷
        tree.postOrderTraverse();//後序遍歷
        tree.insert(15);    //插入結點
        tree.search(7);        //查詢結點
        tree.search(100);    //查詢一個不存在的結點
        tree.getMax();        //獲取最大值
        tree.getMin();        //獲取最小值
        tree.getPre(7);        //前驅結點
        tree.getPre(2);        //最前的前驅結點
        tree.getPost(7);    //後繼結點
        tree.getPost(15);    //最後的後繼結點
        tree.delete(5);        //刪除結點
        tree.delete(0);        //刪除一個不存在的結點
    }
}

然後，二叉搜索樹：

public class BinTree {
    Node root=null;
    private class Node{
        Node parent=null;
        Node leftChild=null;
        Node rightChild=null;
        int key;
        public Node(int data) {
            this.key=data;
        }
    }
    public BinTree(int[] datas) {
        buildTree(datas);
    }
    private void buildTree(int[] datas) {
        for (int i = 0; i < datas.length; i++) {
            Node node=new Node(datas[i]);
            insertNode(node);
        }
    }
    private void insertNode(Node node) {    //插入結點
        Node next=this.root;   
        Node cur=null;    //用來保存當前結點
        while(next!=null){    //當到達葉子結點時，確認位置！
            cur=next;
            if(node.key>=cur.key){
                next=next.rightChild;
            }else{
                next=next.leftChild;
            }
        }
        node.parent=cur;    //插入該結點！
        if(cur==null){
            this.root=node;  //該樹為空樹，所以這個是根節點
        }else if(node.key>=cur.key){
            cur.rightChild=node;
        }else{
            cur.leftChild=node;
        }
    }
    /*
    * 插入一個數
    */
    public void insert(int data){   
        Node node=new Node(data);
        System.out.println("插入結點："+data);
        insertNode(node);
        this.midOrderTraverse();
    }
   
    /*
    * 先序遍歷
    */
    public void preOrderTraverse(){   
        System.out.println("先序遍歷：");
        preOrderTraverse(root);
        System.out.println();
    }
    private void preOrderTraverse(Node node){    //先序遍歷
        if(node!=null){
            System.out.print("-"+node.key+"-");
            preOrderTraverse(node.leftChild);
            preOrderTraverse(node.rightChild);
        }
    }
    /*
    * 中序遍歷
    */
    public void midOrderTraverse(){   
        System.out.println("中序遍歷：");
        midOrderTraverse(root);
        System.out.println();
    }
    private void midOrderTraverse(Node node){    //中序遍歷
        if(node!=null){
            midOrderTraverse(node.leftChild);
            System.out.print("-"+node.key+"-");
            midOrderTraverse(node.rightChild);
        }
       
    }
   
    /*
    * 後序遍歷
    */
    public void postOrderTraverse(){
        System.out.println("後序遍歷：");
        postOrderTraverse(root);
        System.out.println();
    }
    private void postOrderTraverse(Node node){    //後序遍歷
        if(node!=null){
            System.out.print("-"+node.key+"-");
            postOrderTraverse(node.leftChild);
            postOrderTraverse(node.rightChild);
        }
    }
   
    /*
    * 搜索結點
    */
    public void search(int data){   
        System.out.println("您要查找的是："+data);
        Node node;
        if((node=searchNode(new Node(data)))==null){
            System.out.println("樹中沒有該結點！");
        }else{
            System.out.println("查找"+node.key+"成功！");
        }
    }
   
    private Node searchNode(Node node){    //private供內部調用，��索結點
        if(node==null){
            System.out.println("輸入為空，查找失敗！");
        }else{
            if(root==null){
                System.out.println("該樹為空樹！");
            }else{                        //開始查找
                boolean isFound=false;   
                Node x=root;
                Node y=null;
                while(!isFound&&x!=null){    //當查到或者到了葉子節點還沒查到時，終結！
                    y=x;
                    if(node.key==x.key){   
                        isFound=true;
                    }else{                    //通過比較大小往下面查找
                        if(node.key>x.key){   
                            x=x.rightChild;
                        }else{
                            x=x.leftChild;
                        }
                    }
                }
                if(isFound){    //沒找到的話，在最後返回null
                    return y;
                }
            }
        }
        return null;
    }
   
    /*
    * 獲取最大值
    */
    public void  getMax(){   
        Node node;
        if((node=getMaxNode(root))==null){
            System.out.println("該樹為空！");
        }else{
            System.out.println("最大的結點是："+node.key);
        }
       
    }
   
    private Node getMaxNode(Node node){    //獲取最大值
        if(node!=null){
            Node x=node;
            Node y=null;
            while(x!=null){    //一直往右遍歷直到底就是最大值了！
                y=x;
                x=x.rightChild;
            }
            return y;
        }
        return null;
    }
   
    /*
    * 獲取最小值
    */
    public void getMin(){   
        Node node;
        if((node=getMinNode(root))==null){
            System.out.println("該樹為空！");
        }else{
            System.out.println("最小的結點是："+node.key);
        }
    }
    private Node getMinNode(Node node){    //獲取最小值
        if(node!=null){
            Node x=node;
            Node y=null;
            while(x!=null){    //一直往左遍歷直到底就是最小值了！
                y=x;
                x=x.leftChild;
            }
            return y;
        }
        return null;
    }
   
    /*
    * 獲取前驅結點
    */
    public void getPre(int data){   
        Node node=null;
        System.out.println(data+"的前驅結點：");
        if((node=getPreNode(searchNode(new Node(data))))==null){
            System.out.println("該結點不存在或無前驅結點！");
        }else{
            System.out.println(data+"的前驅結點為："+node.key);
        }
    }
   
    private Node getPreNode(Node node){    //獲取前驅結點
        if(node==null){
            return null;
        }
        if(node.leftChild!=null){    //當有左孩子時，前驅結點就是左子樹的最大值
            return getMaxNode(node.leftChild);
        }else{//當不存在左孩子時，前驅結點就是——它的祖先，而且，它在這個祖先的右子樹中。這句話自己畫圖就能理解了
            Node x=node;
            Node y=node.parent;
            while(y!=null&&x==y.leftChild){
                x=y;
                y=y.parent;
            }
            return y;
        }
    }
   
    /*
    * 獲取後繼結點
    */
    public void getPost(int data){   
        Node node=null;
        System.out.println(data+"的後繼結點：");
        if((node=getPostNode(searchNode(new Node(data))))==null){
            System.out.println("該結點不存在或無後繼結點！");
        }else{
            System.out.println(data+"的後繼結點為："+node.key);
        }
    }
   
    private Node getPostNode(Node node){    //獲取後繼結點
        if(node==null){
            return null;
        }
        if(node.rightChild!=null){    //當有右孩子時，前驅結點就是右子樹的最小值
            return getMinNode(node.rightChild);
        }else{//當不存在右孩子時，後繼結點就是——它的祖先，而且，它在這個祖先的左子樹中。這句話自己畫圖就能理解了
            Node x=node;
            Node y=node.parent;
            while(y!=null&&x==y.rightChild){
                x=y;
                y=y.parent;
            }
            return y;
        }
    }
   
   
    /*
    * 刪除結點
    */
    public void delete(int data){   
        Node node;
        if((node=searchNode(new Node(data)))==null){//注意！這裡不能new結點！你必須從樹中找該結點！new就是初始化了
            System.out.println("二叉樹中不存在此結點！");
            return;
        }
        deleteNode(node);
        System.out.println("刪除結點"+data+"後：");
        this.midOrderTraverse();
    }
   
   
    private void deleteNode(Node node){
        if(node==null){
            System.out.println("刪除結點不能為空！");
            return;
        }
        replacedNode(node);
    }
   
    private void replacedNode(Node node) {    //替換結點
        if(node.leftChild!=null
                &&node.rightChild!=null){    //當有左右孩子時，用後繼結點替換
            replacedNodeOfPost(node);
        }
        else
        {
            if(node.leftChild!=null){    //當只有左孩子時，直接用左子樹替換
                node=node.leftChild;
            }else if(node.rightChild!=null){    //只有右孩子時，直接有子樹替換
                node=node.rightChild;
            }else{            //當沒有左右孩子時，就直接釋放了這個結點
                freeNode(node);
            }
        }
    }
   
   
    private void freeNode(Node node) {    //釋放該結點，斷掉其與父結點的鏈接
        if(node==node.parent.leftChild){
            node.parent.leftChild=null;
        }else{
            node.parent.rightChild=null;
        }
    }
   
    private void replacedNodeOfPost(Node node) {   
        Node y=this.getPostNode(node);    //找後繼結點
        node.key=y.key;
        replacedNode(y);    //替換了key之後，再一次遞歸把現在這個結點給替換了！
    }
   
}

最後是測試結果：

------------------分割線-------------------------

先序遍歷：
-12--4--3--2--5--4--7--6--8--9-
中序遍歷：
-2--3--4--4--5--6--7--8--9--12-
後序遍歷：
-12--4--3--2--5--4--7--6--8--9-
插入結點：15
中序遍歷：
-2--3--4--4--5--6--7--8--9--12--15-
您要查找的是：7
查找7成功！
您要查找的是：100
樹中沒有該結點！
最大的結點是：15
最小的結點是：2
7的前驅結點：
7的前驅結點為：6
2的前驅結點：
該結點不存在或無前驅結點！
7的後繼結點：
7的後繼結點為：8
15的後繼結點：
該結點不存在或無後繼結點！
刪除結點5後：
中序遍歷：
-2--3--4--4--6--7--8--9--12--15-
二叉樹中不存在此結點！

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm