目錄

1、二叉排序樹的定義

2、二叉排序樹的查找

3、二叉排序樹的插入與刪除

4、二叉排序樹的構造

5、二叉排序樹的刪除

?

定義

二叉排序樹（Binary Sort Tree）又稱為二叉查找樹（Binary Search Tree）、二叉搜索樹。

它是特殊的二叉樹：對于二叉樹，假設x為二叉樹中的任意一個結點，x節(jié)點包含關鍵字key，節(jié)點x的key值記為key[x]。如果y是x的左子樹中的一個結點，則key[y]<=key[x]；如果y是x的右子樹的一個結點，則key[y]>=key[x]。那么，這棵樹就是二叉查找樹。

?

二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小于右分支的值，然后再就行和每個節(jié)點的父節(jié)點比較大小，查找最合適的范圍。這個算法的效率查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。

?

它或者是一顆空樹，或者是具有下列性質的二叉樹：

1. 若任意節(jié)點的左子樹不為空，則左子樹上的所有節(jié)點的值均小于它的根結點的值；
2. 若任意節(jié)點的右子樹不為空，則左子樹上所有節(jié)點的值均小于它的根結點的值；
3. 任意節(jié)點的左、右子樹也分別為二叉查找樹。
4. 沒有鍵值相等的節(jié)點。

二叉查找樹的性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。

構造一顆二叉排序樹的目的，其實并不是為了排序，而是為了提高查找和插入刪除關鍵字的速度。不管怎么說，在一個有序數據集上的查找，速度總是要快于無序的數據集的，而二叉排序樹這樣的非線性結構，也有利于插入和排序的實現。

二叉查找樹的高度決定了二叉查找樹的查找效率。

?

查找

在二叉查找樹中查找x的過程如下：

1. 若二叉樹是空樹，則查找失敗。
2. 若x等于根結點的數據，則查找成功，否則。
3. 若x小于根結點的數據，則遞歸查找其左子樹，否則。
4. 遞歸查找其右子樹。

復雜度分析，它和二分查找一樣，插入和查找的時間復雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡。

根據上述的步驟，寫出其查找操作的代碼：

c語言實現：

?/*二叉樹的查找，非遞歸*/
BiSTNode *BST_Search1(BiSTree t, KeyType kx , BiSTNode **parent)
{  /*在二叉排序樹t上查找關鍵字為kx的元素，若找到，返回所在結點的地址，否則返回空指針，通過形參parent返回待查找結點kx的父結點地址*/
    BiSTNode *p = t, *q = NULL;
    while(p) {  /*從根結點開始查找*/
       if (kx == p->data.key) { /*查找成功*/
            *parent = q;
            return(p);
        }
        q = p;
        if(kx < p->data.key)
            p = p->lchild; /*kx小于p的關鍵字，在左子樹查找*/
        else
            p = p->rchild; /*kx大于p的關鍵字，在右子樹查找*/
    }
    *parent = q;
    return p;   /*查找失敗*/
}

/*二叉樹的查找，遞歸算法*/
BiSTNode *BST_Search2 (BiSTree t, KeyType kx)
{ /*在二叉排序樹t上查找關鍵字為kx的元素，若找到，返回所在結點的地址，否則返回空指針*/
    if (t == NULL || t->data.key == kx)
        return(t);    /*若樹空或根結點等于kx*/
    else if(kx < t ->data.key)
        BST_Search2(t->lchild, kx); 
    else
        BST_Search2(t->rchild, kx); 
}

Java實現：

 public boolean contains(T t)  
   {  
      return contains(t, rootTree);  
         
   }  
 /**從某個結點出開始查找元素*/  
   public boolean contains(T t, BinaryNode<T> node)  
   {  
      if(node==null)  
        return false;//結點為空，查找失敗  
      int result = t.compareTo(node.data);  
       if(result>0)  
          return contains(t,node.right);//遞歸查詢右子樹  
      else if(result<0)  
          return contains(t, node.left);//遞歸查詢左子樹    
      else  
          return true;  
   }  
    /** 
       這里我提供一個對二叉樹最大值 
       最小值的搜索*/  
   
  
 /**找到二叉查找樹中的最小值*/  
   public T findMin()  
   {  
      if(isEmpty())  
      {  
          System.out.println("二叉樹為空");  
          return null;  
      }else  
       return findMin(rootTree).data;  
         
   }  
   /**找到二叉查找樹中的最大值*/  
   public T findMax()  
   {  
       if(isEmpty())  
          {  
              System.out.println("二叉樹為空");  
              return null;  
          }else  
           return findMax(rootTree).data;  
   }  
  
/**查詢出最小元素所在的結點*/  
   public BinaryNode<T> findMin(BinaryNode<T> node)  
   {  
       if(node==null)  
           return null;  
       else if(node.left==null)  
           return node;  
       return findMin(node.left);//遞歸查找  
   }  
   /**查詢出最大元素所在的結點*/  
   public BinaryNode<T> findMax(BinaryNode<T> node)  
   {  
       if(node!=null)  
       {  
           while(node.right!=null)  
               node=node.right;  
       }  
       return node;         
   }

?

插入

插入：從根結點開始逐個與關鍵字進行對比，小了去左邊，大了去右邊，碰到子樹為空的情況就將新的節(jié)點連接。二叉查找樹的插入過程如下：

• 1) 若當前的二叉查找樹為空，則插入的元素為根節(jié)點;
• 2) 若插入的元素值小于根節(jié)點值，則將元素插入到左子樹中;
• 3) 若插入的元素值不小于根節(jié)點值，則將元素插入到右子樹中。

c語言實現：

?

BiSTree BST_InsertNode (BiSTree t, KeyType kx)
{    /*在二叉排序樹上插入關鍵字為kx的結點*/
    BiSTNode *f, *p, *s;
    p = t;
    while(p) { /*尋找插入位置*/
        if (kx == p->data.key)   {
            printf("kx已存在,不需插入");
            return(t);
        } else {
            f = p;                        /*結點f指向結點p的雙親*/
            if(kx < p->data.key)
                p = p->lchild;
            else
                p = p->rchild;
        }
    }
    s = ( BiSTNode *)malloc(sizeof(BiSTNode)); /*申請并填裝結點*/
    s->data.key = kx;   s->lchild = NULL;  s->rchild = NULL;
    if (!t) t = s;                          /*向空樹中插入時*/
    else if(kx < f->data.key)
        f->lchild = s; /*插入結點s為結點f的右孩子*/
    else
        f->rchild = s;                 /*插入結點s為結點f的左孩子*/
    return(t);
}

?

Java實現：

/**插入元素*/  
   public void insert(T t)  
   {  
       rootTree = insert(t, rootTree);  
   }  
/**在某個位置開始判斷插入元素*/  
   public BinaryNode<T> insert(T t,BinaryNode<T> node)  
   {  
       if(node==null)  
       {  
           //新構造一個二叉查找樹  
           return new BinaryNode<T>(t, null, null);  
       }  
       int result = t.compareTo(node.data);  
       if(result<0)  
          node.left= insert(t,node.left);  
       else if(result>0)  
          node.right= insert(t,node.right);  
       else  
           ;//doNothing  
       return node;  
   }

?

?

刪除

如果要刪除的節(jié)點是葉子，直接刪；如果只有左子樹或只有右子樹，則刪除節(jié)點后，將子樹連接到父節(jié)點即可；如果同時有左右子樹，則可以將二叉排序樹進行中序遍歷，取將要被刪除的節(jié)點的前驅或者后繼節(jié)點替代這個被刪除的節(jié)點的位置。

二叉查找樹的刪除，分三種情況進行處理：

• 1) p為葉子節(jié)點，直接刪除該節(jié)點，即修改其父節(jié)點的指針（注意分是根節(jié)點和不是根節(jié)點），如圖a;

?

?

?

?

?

?

?

• p為單支節(jié)點（即只有左子樹或右子樹）。讓p的子樹與p的父親節(jié)點相連，刪除p即可（注意分是根節(jié)點和不是根節(jié)點），如圖b;

• p的左子樹和右子樹均不空。即待刪除的結點同時有左子樹和右子樹。根據二叉樹的特點，可以從其左子樹選擇關鍵字最大的結點或右子樹關鍵字最小的結點放在被刪去結點的位置上。如圖c，刪除5。

?

/**刪除元素*/  
   public void remove(T t)  
   {  
       rootTree = remove(t,rootTree);  
   } /**在某個位置開始判斷刪除某個結點*/  
   public BinaryNode<T> remove(T t,BinaryNode<T> node)  
   {  
       if(node == null)  
           return node;//沒有找到,doNothing  
       int result = t.compareTo(node.data);  
       if(result>0)  
           node.right = remove(t,node.right);  
       else if(result<0)  
           node.left = remove(t,node.left);  
       else if(node.left!=null&&node.right!=null)  
       {  
           node.data = findMin(node.right).data;  
           node.right = remove(node.data,node.right);  
       }  
       else  
           node = (node.left!=null)?node.left:node.right;  
       return node;       
   }

?

二叉排序樹的查找分析

1) 二叉排序樹上查找某關鍵字等于給定值的結點過程，其實就是走了一條從根到該結點的路徑。

比較的關鍵字次數＝此結點的層次數;

最多的比較次數＝樹的深度（或高度），即 ?log2 n? 1

2) 一棵二叉排序樹的平均查找長度為：

其中： n_i 是每層結點個數； C_i 是結點所在層次數； m 為樹深。

?

最壞情況：即插入的n個元素從一開始就有序， ——變成單支樹的形態(tài)！ 此時樹的深度為n ; ASL= (n 1)/2 此時查找效率與順序查找情況相同。

最好情況：即：與折半查找中的判定樹相同（形態(tài)比較均衡）

樹的深度為：?log 2n ? 1 ； ASL=log 2(n 1) –1 ；與折半查找相同。

?