二叉搜索树 §

又名二叉查找树，因为二叉查找树不是完全二叉树，因此通常使用链表方式存储。一个分布平均的二叉查找树的查找，插入，删除操作时间复杂度均为O(logn)；在极度不平衡的情况下，二叉查找树会退化为链表。

对二叉查找树进行中序遍历可以得到有序数组

结构要求 §

对于二叉查找树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，右子树节点的值都大于这个节点的值。

插入操作 §

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

删除操作 §

1. 要删除的节点没有子节点：直接将父节点中，指向要删除节点的指针置为 null
2. 要删除的节点只有一个子节点（只有左子节点或者右子节点）：只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点
3. 要删除的节点有两个子节点：找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点

如何处理重复数据 §

1. 通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上
2. 每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，将待插入数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。当要查找数据的时候，遇到值相同的节点，并不停止查找操作，继续在右子树中查找，直到遇到叶子节点，才停止。

// 二叉搜索树类
public class BinarySearchTree { 
    // 节点类
    private class Node {
        // 数据域
        int data; 
        // 右子树
        Node right; 
        // 左子树
        Node left; 
    }
 
    // 根节点
    private Node root;
 
    // 插入操作
    private void insert(int key) {
        Node p = new Node();
        p.data = key;
 
        if (null == root) {
            root = p;
        } else {
            Node parent = new Node();
            Node current = root;
            while (true) {
                parent = current;
                if (key > current.data) {
                    current = current.right;
                    if (null == current) {
                        parent.right = p;
                        return;
                    }
                } else {
                    current = current.left;
                    if (null == current) {
                        parent.left = p;
                        return;
                    }
                }
            }
        }   
    }
 
    // 查找节点
    public Node find(int key) {
        Node current = root;
        while (current.data != key) {
            if (key > current.data) {
                current = current.right;
            } else {
                current = current.left;
            }
            if (null == current) {
                return null;
            }
        }
        return current;
    }
 
 
    //寻找要删除节点的中序后继结点
    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;
        }
    }
 
 
 
 
}
 

---

Project Links：

Leetcode96 不同的二叉搜索树