二叉排序樹的建立，查找，插入，删除

1. 二叉排序樹或者是空樹，或者是具有以下性質的二叉樹：

   （1）若左子樹非空，則左子樹上所有結點的關鍵字的值均小于它的根結點的關鍵字的值

   （2）若右子樹非空，則右子樹上所有結點的關鍵字的值均大于等于它的根結點的關鍵字的值

   （3）左右子樹本身又是一顆二叉排序樹

2. 二叉排序樹的查找：

   二叉排序樹的查找與折半查找類似，根結點相當于查找區間的中點，左子樹相當于前半子區間，右子樹相當于後半子區間。查找過程為：若根結點的關鍵字值等于查找的關鍵字，成功。否則，若小于根結點的關鍵字值，查找左子樹。若大于根結點的關鍵字值，查找右子樹。若子樹為空，查找不成功。

3. 二叉排序樹的插入：

   二叉排序樹是一種動态樹表，其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上通路的最後一個結點的左孩子或右孩子結點。

4. 二叉排序樹的删除：

   在二叉排序樹删去一個結點，分三種情況讨論：

   (1). 若p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由于删去葉子結點不破壞整棵樹的結構，則可以直接删除此子結點。

   (2). 若p結點隻有左子樹PL或右子樹PR，此時隻要令PL或PR直接成為其雙親結點f的左子樹（當p是左子樹）或右子樹（當p是右子樹）即可，作此修改也不破壞二叉排序樹的特性。

   (3). 若p結點的左子樹和右子樹均不空。在删去p之後，為保持其它元素之間的相對位置不變，可按中序周遊保持有序進行調整，可以有兩種做法：（下面f是p的父結點）

   其一是令p的左子樹為f的左/右(依p是f的左子樹還是右子樹而定)子樹，s為p左子樹的最右下的結點（中序周遊的前驅），令p的右子樹為s的右子樹；

   其二是令p的直接前驅（或直接後繼）替代p，然後再從二叉排序樹中删去它的直接前驅（或直接後繼）－即讓f的左子樹(如果有的話)成為p左子樹的最左下結點(如果有的話)，再讓f成為p的左右結點的父結點。

5. 建立二叉排序樹，查找，插入，删除代碼如下，當删除結點含有左右子樹時，采用第二中方式。

import java.util.LinkedList;
public class BinarySortTree {
    /*使用二叉連結清單存儲二叉排序樹*/

    class Node{   //使用内部類定義二叉樹結點資料結構
        int data;
        Node right;
        Node left;
    }

    /*二叉排序樹的查找*/
    public Node BSTSearch(LinkedList<Node> list,int x){
        /* x為待查找的資料 */
        Node p,root=list.get();
        p=root;
        if(p==null) return null;
        while(p!=null){
            if(p.data==x) {
                System.out.println("查找成功");
                return p;
            }else if(p.data>x){
                p=p.left;
            }else {
                p=p.right;
            }
        }
        System.out.println("查找失敗");
        return null;    
    }

    /*二叉排序樹的插入
     * 在查找時，如果在二叉排序書中找不到指定元素，則插入
     */
    public void BSTInsert(LinkedList<Node> list,int x){
        Node p,q=null;              //q指向p的雙親結點
        if(list.size()==){  //list為空二叉排序樹,建立根結點
            p=new Node();
            p.data=x;
            p.left=null;
            p.right=null;
            list.add(p);
            return;
        }else{
            p=list.get();   //初始時p指向根結點
        }
        while(p!=null){
            q=p;
            if(p.data==x) {
                System.out.println("元素存在，則不插入");
                return;
            }if(p.data<x){
                p=p.right;
            }else{
                p=p.left;
            }
        }

        /*查找失敗,建立新結點則進行插入操作*/
        {
        p=new Node();
        p.data=x;
        p.left=null;
        p.right=null;
        list.add(p);
        if(q.data>x) q.left=p;
        else q.right=p;
        }
    }

    /*利用二叉排序樹的插入算法構造一個二叉排序樹*/
    public LinkedList<Node> CreatBSTree(int array[]){
        LinkedList<Node> list=new LinkedList<Node>();
        for(int i=;i<array.length;i++){
            BSTInsert(list,array[i]);
        }
        return list;
    }


    /*删除元素*/
    public void BSTDelete(Node root,int x){
        /*x為待删除的資料元素，root為根結點*/
        Node q=null,p=null,s=null;   //p指向删除結點，q指向删除結點的父結點，s指向删除結點的孩子結點
        p=root;
        /*在二叉排序樹中查找資料元素x*/
        while(p!=null &&p.data!=x){
            q=p;
            if(p.data<x)
                p=p.right;
            else p=p.left;
        }
        if (p==null) return;  //如果沒有找到x則不進行删除操作

        s=p;
        if(s.left!=null && s.right!=null){//被删除結點左右子樹均不為空，查找被删除結點的中序前驅結點，并用p指向它
            q=s;
            p=s.left;
            while(p.right!=null){
                q=p;
                p=p.right;
            }
            /*用中序前驅結點的資料覆寫被删除結點，此時中序前驅就變成了被删除結點，後面隻需删除中序前驅即可*/
            if(p!=s) s.data=p.data;
        }

        /*由于第(1)，第(3)種情況都轉化成了第2種情況，此時隻需考慮第(2)種情況即可*/
        s=(p.left!=null)?p.left:p.right;  //p的左子樹不為空，則s指向左子樹，否則s指向右子樹
        if(q==null)    //被删除結點為根結點，則删除後應修改根指針
            root=s; 
        else{
            if(q.left==p)
                q.left=s;
            else q.right=s;
        }

    }


    /*采用中序周遊輸出二叉排序樹*/
    public void InOrderTree(Node root){
        Node p=root;
        if(p==null) return;
        if(p.left!=null){
        InOrderTree(p.left);  //遞歸周遊左子樹
        }
        System.out.print(p.data+", ");
        if(p.right!=null){
        InOrderTree(p.right);  //遞歸周遊右子樹    
        }
    }

    public static void main(String[] args) {
        int array[]=new int []{,,,,,,,,,,,};
        LinkedList<Node>list=new LinkedList<Node>();

        BinarySortTree bs=new BinarySortTree();
        list=bs.CreatBSTree(array);
        Node root=list.get();  //root為根結點

        bs.InOrderTree(root);
        bs.BSTSearch(list,);
        bs.BSTDelete(root, );
        bs.InOrderTree(root);

    }

}