登入
首頁 所有文章 資料結構 樹-二元搜尋樹之介紹與範例
長也   2018-03-08 20:06:51(1年前)    1205點閱   2喜歡  0收藏
樹-二元搜尋樹之介紹與範例  

二元搜尋樹的特性

1.左子樹的資料(鍵值)均小於樹根的資料

2.右子樹的資料(鍵值)均大於樹根的資料

3.左子樹與右子樹也是二元搜尋樹

二元搜尋樹的加入與搜尋

只要依照左子樹小於樹根,右子樹大於樹根的規則尋找合適的插入點即可

例如我們將87加入,將會加在65的右邊。

    public void insert(){ //插入節點
        
        Node ptr=new Node();
        System.out.println("Input DATA:");
        ptr.data=input.nextInt();
        if(search(ptr.data)!=null){
            System.out.println("該筆資料已經存在");
        }
        else{
            
            ptr.rlink=ptr.llink=null;
            if (root==null){ //判斷樹根
                root=ptr;
                System.out.println("Node Insert!!!(ROOT)");
            }
            else{
                
                Node current = new Node(); //用於尋找適合插入的節點
                current=root;
                Node prev = new Node();
                while (current!=null){
                    
                    prev=current;
                    if(current.data>ptr.data) //如果樹根大於節點,向左
                        current=current.llink;
                    else
                        current=current.rlink;
                    
                }
                if(prev.data>ptr.data) //如果樹根大於節點,插入左方
                    prev.llink=ptr;
                else
                    prev.rlink=ptr;
                System.out.println("Node Insert!!!");
            }
        
        }
                
    
    }

若要搜尋二元搜尋樹,原理與加入差不多。值得一提的是,越高平衡度的二元樹,可以獲得比較好的搜尋效率,相反的,若極度不平衡的二元樹(如左右斜樹),幾乎相當於循序搜尋,相當沒有效率。

    public Node search(int s){
        
        Node current=root;
        while (current!=null){
            
            if(current.data==s)
                break;
            else{
                if(current.data>s)
                  current=current.llink;
                else if(current.data<s)
                 current=current.rlink;
            }
            
        }
        return current;
    }

二元搜尋樹的刪除

刪除時,若不是刪除樹葉節點,為避免鏈結斷掉使二元樹變成樹林,所以需要尋找替代的節點。我們以刪除50舉例兩種方法:

1.尋找右子樹最小的節點:將以65替代50

 

2.尋找左子樹最大的節點:將以45取代

上面兩種方式,只需要採用一個。當找不到右子樹的替代,再找左子樹的替代節點即可。

    public Node re_l(Node node){ //傳入要刪除的節點的左端節點
        
        Node current = node;
        while (current!=null && current.rlink!=null){
           
            current=current.rlink; //由於左端要找最大,最大的一定向右找

        }
        return current;
    }
    
    public Node re_r(Node node){
        
        Node current=node;
        while (current!=null && current.llink!=null){
            
            current=current.llink;
        
        }
        return current;
    }

當找到替代節點後,需尋找替代節點的父節點,與搜尋的原理差不多。比較大小之後,再檢查llink或rlink是否等於替代節點即可。

    public Node parent(Node node){
        
        Node parent=root;
        while(parent!=null){
            
            if(node.data>parent.data){
                if(parent.rlink==node)
                    return parent;
                else
                    parent=parent.rlink;
            }
            else if(node.data<parent.data){
                
                if(parent.llink==node)
                    return parent;
                else
                    parent=parent.llink;
                
            }
               
        }
        return null;
    }

當找到替代節點與父節點之後的情形如下 :

之後判斷替代節點是父節點的左子樹還是右子樹,在判斷替代節點是否有右子樹(不可能有左子樹,若尚有左子樹代表並非右子樹的最小節點),若有右子樹,則將父節點的右鏈結(是左是右要看替代節點是父節點的左還右子樹)指向右子樹。

當然,若替代節點沒有右子樹,則將父節點指向null即可。

    public void del(){
        
        Node del_node=new Node();
        System.out.println("Input DEL DATA:");
        del_node.data=input.nextInt();
        if(search(del_node.data)==null)
            System.out.println("Data Not Find!");
        else{
            del_node=search(del_node.data);
            if(del_node.rlink==null && del_node.llink==null){ //若刪除為樹葉,直接刪掉
                if(del_node==root)  //若刪除的不是樹根,必須先移除父節點的鍊節
                    root=null;
                
                else{
                    
                    Node parent=parent(del_node);
                    if(del_node.data>parent.data) //若要刪除的節點為父的右子樹
                        parent.rlink=null;
                    else if(del_node.data<parent.data)
                        parent.llink=null;
                
                }
                del_node=null;
            
            }
            else{ //如果不是,要找左或右的替代節點
                Node re_node;
                if(re_r(del_node.rlink)!=null)
                  re_node=re_r(del_node.rlink);
                else
                  re_node=re_l(del_node.llink);
                //System.out.printf("RENODE:%d\n",re_node.data);
                Node parent=parent(re_node); //尋找替代節點的父節點
                //System.out.printf("parent:%d\n",parent.data);
                //判斷替代節點為父節點的左子還右子樹
                if(re_node.data>parent.data){ //替代節點為右子
                    //替代節點不是有右子樹就是有左子樹,否則為樹葉節點,不會同時有左或右子樹,如果有代表不符合替代節點的規則
                    if(re_node.llink!=null)//右子為空
                        parent.rlink=re_node.llink;
                    else if(re_node.rlink!=null)//左子為空
                        parent.rlink=re_node.rlink;
                    else    //樹葉
                        parent.rlink=null;
                    
                }
                else{   //替代節點為左
                    if(re_node.llink!=null)//右子為空
                        parent.llink=re_node.llink;
                    else if(re_node.rlink!=null)//左子為空
                        parent.llink=re_node.rlink;
                    else    //樹葉
                        parent.llink=null;
                }
                //System.out.printf("%d %d \n",del_node.data,re_node.data);
               del_node.data=re_node.data; 
            }
                
            
        }
        
    }

這裡實作的部分,最後del_node.data=re_node.data這行,替代的只是資料內容,並不是傳指標。

走訪

這裡實作採用中序走訪,而前、中、後序的走訪基本上都利用遞迴(堆疊)實作。

    public void inordor(Node node){
        
        if(node!=null){
            inordor(node.llink);//走訪左
            System.out.printf("%d ",node.data);//訪樹根
            inordor(node.rlink);//走訪右
        }
    }

完整程式碼

import java.util.Scanner;

class Node{
    
    int data;
    Node llink;
    Node rlink;

}

public class BinarySearchTree {
    
    Node root,ptr;
    Scanner input = new Scanner(System.in);

    public BinarySearchTree() {
        
        root=null;
        
    }
    
    
    public void insert(){ //插入節點
        
        Node ptr=new Node();
        System.out.println("Input DATA:");
        ptr.data=input.nextInt();
        if(search(ptr.data)!=null){
            System.out.println("該筆資料已經存在");
        }
        else{
            
            ptr.rlink=ptr.llink=null;
            if (root==null){ //判斷樹根
                root=ptr;
                System.out.println("Node Insert!!!(ROOT)");
            }
            else{
                
                Node current = new Node(); //用於尋找適合插入的節點
                current=root;
                Node prev = new Node();
                while (current!=null){
                    
                    prev=current;
                    if(current.data>ptr.data) //如果樹根大於節點,向左
                        current=current.llink;
                    else
                        current=current.rlink;
                    
                }
                if(prev.data>ptr.data) //如果樹根大於節點,插入左方
                    prev.llink=ptr;
                else
                    prev.rlink=ptr;
                System.out.println("Node Insert!!!");
            }
        
        }
                
    
    }
    
    public void del(){
        
        Node del_node=new Node();
        System.out.println("Input DEL DATA:");
        del_node.data=input.nextInt();
        if(search(del_node.data)==null)
            System.out.println("Data Not Find!");
        else{
            del_node=search(del_node.data);
            if(del_node.rlink==null && del_node.llink==null){ //若刪除為樹葉,直接刪掉
                if(del_node==root)  //若刪除的不是樹根,必須先移除父節點的鍊節
                    root=null;
                
                else{
                    
                    Node parent=parent(del_node);
                    if(del_node.data>parent.data) //若要刪除的節點為父的右子樹
                        parent.rlink=null;
                    else if(del_node.data<parent.data)
                        parent.llink=null;
                
                }
                del_node=null;
            
            }
            else{ //如果不是,要找左或右的替代節點
                Node re_node;
                if(re_r(del_node.rlink)!=null)
                  re_node=re_r(del_node.rlink);
                else
                  re_node=re_l(del_node.llink);
                //System.out.printf("RENODE:%d\n",re_node.data);
                Node parent=parent(re_node); //尋找替代節點的父節點
                //System.out.printf("parent:%d\n",parent.data);
                //判斷替代節點為父節點的左子還右子樹
                if(re_node.data>parent.data){ //替代節點為右子
                    //替代節點不是有右子樹就是有左子樹,否則為樹葉節點,不會同時有左或右子樹,如果有代表不符合替代節點的規則
                    if(re_node.llink!=null)//右子為空
                        parent.rlink=re_node.llink;
                    else if(re_node.rlink!=null)//左子為空
                        parent.rlink=re_node.rlink;
                    else    //樹葉
                        parent.rlink=null;
                    
                }
                else{   //替代節點為左
                    if(re_node.llink!=null)//右子為空
                        parent.llink=re_node.llink;
                    else if(re_node.rlink!=null)//左子為空
                        parent.llink=re_node.rlink;
                    else    //樹葉
                        parent.llink=null;
                }
                //System.out.printf("%d %d \n",del_node.data,re_node.data);
               del_node.data=re_node.data; 
            }
                
            
        }
        
    }
    
    public Node re_l(Node node){ //傳入要刪除的節點的左端節點
        
        Node current = node;
        while (current!=null && current.llink!=null){
           
            current=current.rlink; //由於左端要找最大,最大的一定向右找

        }
        return current;
    }
    
    public Node re_r(Node node){
        
        Node current=node;
        while (current!=null && current.llink!=null){
            
            current=current.llink;
        
        }
        return current;
    }
    
    public Node parent(Node node){
        
        Node parent=root;
        while(parent!=null){
            
            if(node.data>parent.data){
                if(parent.rlink==node)
                    return parent;
                else
                    parent=parent.rlink;
            }
            else if(node.data<parent.data){
                
                if(parent.llink==node)
                    return parent;
                else
                    parent=parent.llink;
                
            }
               
        }
        return null;
    }
    
    
    public Node search(int s){
        
        Node current=root;
        while (current!=null){
            
            if(current.data==s)
                break;
            else{
                if(current.data>s)
                  current=current.llink;
                else if(current.data<s)
                 current=current.rlink;
            }
            
        }
        return current;
    }
    
    public void inordor(Node node){
        
        if(node!=null){
            inordor(node.llink);//走訪左
            System.out.printf("%d ",node.data);//訪樹根
            inordor(node.rlink);//走訪右
        }
    }
    
    public void show(){
        
        if(root!=null)
            inordor(root);
        else
            System.out.println("TREE IS NULL!");
        
    }
    
    public static void main(String[] args) {
        
        BinarySearchTree obj=new BinarySearchTree();
        Scanner input = new Scanner (System.in);
        System.out.println("1.Insert 2.Del 3.中序走訪");
        while (true){
            
            int doing=input.nextInt();
            switch(doing){
                case 1:
                    obj.insert();
                    break;
                case 2:
                    obj.del();
                    break;
                case 3:
                    obj.show();
                    break;
                
                
            }
            
        }
        
    }
    

延伸二元樹

一N節點的二元樹,必有N+1個空白鏈結,將這些空白鏈結以外部型態表示,則此二元樹稱為延伸二元樹。

外徑長(extrenal path length):所有外部節點到樹根距離的總和

內徑長(internal path length):所有內部結點至樹根的距離總和

若以I表示內徑長,E表示外徑長,N表示二元樹節點總和,則:E=I+2N,且若一二元樹擁有最大E,則也具有最大I。通常傾斜樹擁有最大的I,完整二元樹擁有最小I。

下圖中圓圈表示內部節點,方框表示外部節點

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  8則回覆
  回覆於2018-03-08 21:54:30
回覆  #1

補充E=I+2N的證明

E:外部路徑長 ,I:內部路徑長,n:節點數

E = I+ 2n ,n>=0 證明:

令 n = k ,假設n = k 時 E = I + 2k成立

令 n = k+1 ,長度為 I' 、E'

此時內部路徑長:I' = I  + x(令x為新節點的路徑長)

外部路徑長:E' = E - x + 2(x+1) ( 新增內部節點必定由外部節點變成,而新內部節點又使得增加2個新外部節點 )

E' - I' = E - x + 2(x+1) - I - x

        = E - I + 2

        = 2k + 2

-> E' = I' + 2(k+1) 故根據數學歸納法得證

  回覆於2018-03-08 21:55:20

此為97中央資管資結證明

長也   回覆於2018-03-09 00:56:55

感謝補充,目前我的範例在某些測資下還是有問題,目前發現只要父節點是要被刪除的節點,就會產生問題

長也   回覆於2018-03-09 01:00:19

可能是因為父節點再重新指向替代節點的下一個節點(?)的時候,是由目前的父節點判斷,但是父節點若將被刪除,代表前的判斷可能是錯的,會導致二元搜尋樹壞掉(?

  回覆於2018-03-09 12:49:04
 

我猜是祖節點壞掉吧

祖節點指向父節點,改動父節點指向位址時,祖節點依然指向被刪除的節點,所以出問題

長也   回覆於2018-03-09 17:36:33
 

實際上這次實作的替換,他不是真正的傳指標,只是替換資料的內容與調整鏈結

長也   回覆於2018-03-09 19:41:35
 

我最後只好完成刪除後再判斷還符不符合二元搜尋樹的定義

長也   回覆於2018-03-09 20:48:18
 

上面都搞錯了(炸,只是單純把找左子最大的條件寫錯了,已經更正