二叉搜索树(二叉查找树,排序二叉树,有序二叉树)

定义

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行选择

【注2】：没有键值相等的结点。

实现

// 二叉搜索树类
public class BinarySearchTree{ 
    // 节点类
    private class Node{ 
        // 数据域
        int data; 
        // 右子树
        Node right; 
        // 左子树
        Node left; 
    }
    // 根节点    
    private Node root; 


//insert
    public void insert(int key){
        // 待插入的节点
        Node p = new Node(); 
        p.data = key;
        if (root == null){
            root = p;
        }else{
            Node parent = new Node();
            Node current = root;
            while (true){
                parent = current;
                if (key > current.data){
                    current = current.right; // 右子树
                    if (current == null){
                        parent.right = p;
                        return;
                    }
                }else {
                // 本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
                    current = current.left; // 左子树
                    if (current == null){
                        parent.left = p;
                        return;
                    }
                }
            }
        }
    }
//delete
//寻找要删除节点的中序后继结点
    private Node getSuccessor(Node delNode){
        Node successorParent=delNode;
        Node successor=delNode;
        Node current=delNode.right;
        //用来寻找后继结点
        while(current!=null){
            successorParent=successor;
            successor=current;
            current=current.left;
        } 
        //如果后继结点为要删除结点的右子树的左子，需要预先调整一下要删除结点的右子树
        if(successor!=delNode.right) {
            successorParent.left=successor.right;
            successor.right=delNode.right;
        }
        return successor;
     }
     
    public boolean delete(int key){
        Node current = root;
        Node parent = new Node();
        boolean isRightChild = true;
        while (current.data != key)
            parent = current;
            if (key > current.data){
                current = current.right;
                isRightChild = true;
            }else{
                current = current.left;
                isRightChild = false;
            }
            // 没有找到要删除的结点
            if (current == null) return false; 
        // 此时current就是要删除的结点,parent为其父结点
        // 要删除结点为叶子结点
        if (current.right == null && current.left == null)  {
            if (current == root){
                root = null; // 整棵树清空
            }else{
                if (isRightChild)
                    parent.right = null;
                else
                    parent.left = null;
            }
            return true;
        }else if(current.left==null){
        //要删除结点有一个子结点
            if(current==root)
                root=current.right;
            else if(isRightChild)
                parent.right=current.right;
            else
                parent.left=current.right;
            return true;
        }else if(current.right==null){
            if(current==root)
                root=current.left;
            else if(isRightChild)
                parent.right=current.left;
            else
                parent.left=current.left;
            return true;
        }else{ 
         //要删除结点有两个子结点
         //找到要删除结点的后继结点
            Node successor=getSuccessor(current);   
            if(current==root)
                root=successor;
            else if(isRightChild)
                parent.right=successor;
            else
                parent.left=successor;
            
            successor.left=current.left;
            return true;
        }
    } 
    
    

//update


//select
     // 选择以何种方式遍历
    public void traverse(int traverseType){ 
        switch (traverseType){
        case 1:
            System.out.print("preOrder traversal ");
            preOrder(root);
            System.out.println();
            break;
        case 2:
            System.out.print("inOrder traversal ");
            inOrder(root);
            System.out.println();
            break;
        case 3:
            System.out.print("postOrder traversal ");
            postOrder(root);
            System.out.println();
            break;
        }
    }
    // 前序遍历,"中左右"
    public void preOrder(Node root){ 
        if (root != null){
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    
     // 中序遍历,"左中右"
    public void inOrder(Node root){
        if (root != null){
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
    }
     // 后序遍历,"左右中"
    public void postOrder(Node root){
        if (root != null){
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + " ");
        }
    }
    // 从树中按照关键值查找元素
    public Node find(int key){ 
        Node current = root;
        while (current.data != key){
            if (key > current.data)
                current = current.right;
            else
                current = current.left;
            if (current == null) return null;
        }
        return current;
    }
    //输出节点的数据域
    public void show(Node node){    
        if(node!=null)
            System.out.println(node.data);
        else
            System.out.println("null");
    }
    public static void main(String[] args){
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(39);
        tree.insert(24);
        tree.insert(64);
        tree.insert(23);
        tree.insert(30);
        tree.insert(53);
        tree.insert(60);
        /**
         * 		    39
         * 		   /  \
         * 		 24    64
         * 		/  \  /
         *             23 30  53
         * 		        \
         * 			60
         * 
         */
        tree.traverse(1);
        //preOrder traversal 39 24 23 30 64 53 60 
        tree.traverse(2);
        //inOrder traversal 23 24 30 39 53 60 64 
        tree.traverse(3);
        //postOrder traversal 23 30 24 60 53 64 39 
        
        tree.show(tree.find(23));
        //23
        
        //tree.show(tree.find(60));
        //tree.show(tree.find(64));
        
        tree.delete(23);
        //tree.delete(60);
        //tree.delete(64);
        
        tree.show(tree.find(23));
        //
        
        //tree.show(tree.find(60));
        //tree.show(tree.find(64));
    }
}