概述

一颗二叉搜索树可以为空，但如果不为空，必须满足以下性质：

• 非空左子树的所有键值小于其根结点的键值
• 非空右子树的所有键值大于其根结点的键值
• 左、右子树都是二叉搜索树

二叉树搜索树的操作

查找操作 Find

• 查找从根结点开始，如果数为空，则返回 null
• 若搜索数为非空，则根节点关键字和 X 进行对比，并进行不同处理：
  • 若 X 小于根结点键值，只需在左子树中继续搜索
  • 如果 X 大于根结点的键值，在右子树中继续搜索
  • 若两者比较结果是相等，搜索完成，返回指向此结点的指针

递归实现

BinaryTreeNode find(BinaryTreeNode root, int data){
    if(root == null) return null;
    if(data < root.getData() )
        return find(root.getLeft(), data);      /*在左子树中继续查找*/      
    else if(data > root.getData())
        return find(root.getRight(), data);   /*在右子树中继续查找*/
    return root;                             /*查找成功*/
}
// 时间复杂度：O(n)      空间复杂度：O(n)

非递归实现

BinaryTreeNode find(BinaryTreeNode root, int data){
    if(root == null) return null;
    while(root != null){
        if(data < root.getData())
            root = root.getLeft();        /*在左子树中继续查找*/        
        else if(data > root.getData())
            root = root.getRight();      /*在右子树中继续查找*/
        else
            return root;                 /*查找成功*/  
    }
    return null;
}
// 时间复杂度：O(n)      空间复杂度：O(1)

查找最大和最小元素

• 最小元素一定是在树的最左分支的端结点上 findMin
• 最大元素一定是在树的最右分支的端结点上 findMax

递归实现

BinaryTreeNode findMin(BinaryTreeNode root){
    if(root == null) 
        return null;
    else if(root.getLeft() != null)
        return findMin(root.getLeft())          /*沿左分支继续查找*/   
    else
        return root       /*找到最左叶结点并返回*/
}

BinaryTreeNode findMax(BinaryTreeNode root){
    if(root == null) 
        return null;
    else if(root.getRight() != null)
        return findMax(root.getRight())     /*沿右分支继续查找*/
    else
        return root
}

非递归实现

BinaryTreeNode findMin(BinaryTreeNode root){
    if(root == null)
        return null;
    while(root.getLeft() != null) 
        root = root.getLeft();        /*沿左分支继续查找*/        
    return root;       /*找到最左叶结点并返回*/
}


BinaryTreeNode findMax(BinaryTreeNode root){
    if(root == null)
        return null;
    while(root.getRight() != null) 
        root = root.getRight();       /*沿右分支继续查找*/
    return root;
}

插入操作 Insert

插入操作关键是要找到元素应该插入的位置，可以采用与 find 类似的方法

递归实现

BinaryTreeNode insert(BinaryTreeNode root, int data){
    if(root == null) 
        /*若原树为空，生成并返回一个新结点*/
        root = new BinaryTreeNode();
        root.setData(data);
        root.setRight(null);
        root.setLeft(null);
    else    /*开始找要插入元素的位置*/
        if(data < root.getData())
            // 递归插入左子树
            root.setLeft(insert(root.getLeft(), data));      
        else if(data > root.getData())
            // 递归插入右子树
            root.setRight(insert(root.getRight(), data));
    // 将生成的新结点返回
    return root;
}

删除操作 Delete

考虑三种情况：

1）要删除的是叶结点：直接删除，并再修改其父结点指针 --- 置为 null。例如下：删除 35

2）要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点。例如下：删除 33

3）要删除的结点有左、右两棵子树：用另一个结点替代被删除的结点，右子树的最小元素或者左子树的最大元素。例如下：用右子树最小 50 或左子树最大 35 代替 41 的值，且删除 35 或 50 所在的位置，此位置一定是叶子结点或只有一个孩子结点（此步骤又变成了上面第1条和第2条）

BinaryTreeNode delete(int data, BinaryTreeNode root){
    BinaryTreeNode tmp;
    if(root == null) 
        System.out.println("要删除的元素未找到");
    else if(data < root.getData())
        root.setLeft(delete(data, root.getLeft()));   /*左子树递归删除*/
    else if(data > root.getData())
        root.setRight(delete(data, root.getRight()))   /*右子树递归删除*/
    else
        if(root.getLeft() && root.getRight()){     /*被删除结点存在左右两个子结点*/
            tmp = findMin(root.getRight());    /*右子树中找最小的元素填充删除结点*/
            root.setData(tmp.getData());
            // 删除结点的右子树中删除最小元素
            root.setRight(delete(root.getData(), root.getRight()));    
        }else{  /*被删除结点有一个或无子结点*/
            tmp = root;
            if(root.getLeft() == null)   /*有右孩子或无子结点*/
                root = root.getRight();
            if(root.getRight() == null)  /*有左孩子或无子结点*/
                root = root.getLeft();
        }
    return root;     
}