欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

二叉搜索树的插入、删除、查找等操作：Java语言实现

程序员文章站 2022-06-29 13:32:17
...

1 二叉搜索树介绍

 二叉搜索树（BST， Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
1. 非空左子树的所有键值小于其根结点的键值。
2. 非空右子树的所有键值大于其根结点的键值。

3. 左、右子树都是二叉搜索树。

2 二叉搜索树的主要操作

2.1 二叉搜索树的查找操作
 查找从根结点开始，如果树为空，返回NULL

 若搜索树非空，则根结点关键字和X进行比较， 并进行不同处理：
 若X小于根结点键值，只需在左子树中继续搜索；
 如果X大于根结点的键值， 在右子树中进行继续搜索；

 若两者比较结果是相等，搜索完成，返回指向此结点的指针。

//查找元素：递归方法
    BinarySearchTreeNode find(BinarySearchTreeNode 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);//在右子树中继续查找
        else
            return root;//查找成功， 返回找到的结点的地址
    }

    //查找元素：非递归方法
    BinarySearchTreeNode iterFind(BinarySearchTreeNode root, int data) {
        while (root != null) {
            if (data < root.getData())
                root = root.getLeft();//向左子树中移动， 继续查找
            else if (data > root.getData())
                root = root.getRight();//向右子树中移动， 继续查找
            else
                return root;//查找成功， 返回找到的结点的地址
        }
        return null;//查询失败
    }

2.2 查找最大和最小元素

 最大元素一定是在树的最右分枝的端结点上
 最小元素一定是在树的最左分枝的端结点上

 最小元素一定是在树的最左分枝的端结点上
//查找最小元素：递归方法 (最小元素一定是在树的最左分枝的端结点上)
    BinarySearchTreeNode findMin(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        else if (root.getLeft() == null)
            return root;//找到最左叶结点并返回
        else
            return findMin(root.getLeft());//沿左分支继续查找
    }

    //查找最小元素：非递归方法 (最小元素一定是在树的最左分枝的端结点上)
    BinarySearchTreeNode iterFindMin(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        while (root.getLeft() != null)
            root = root.getLeft();//沿左分支继续查找
        return root;//找到最左叶结点并返回
    }

    //查找最大元素：递归方法 (最大元素一定是在树的最右分枝的端结点上)
    BinarySearchTreeNode findMax(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        else if (root.getRight() == null)
            return root;//找到最右叶结点并返回
        else
            return findMax(root.getRight());//沿右分支继续查找
    }

    //查找最大元素：非递归方法 (最大元素一定是在树的最右分枝的端结点上)
    BinarySearchTreeNode iterFindMax(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        while (root.getRight() != null)
            root = root.getRight();//沿右分支继续查找
        return root;//找到最右叶结点并返回
    }
2.3 二叉搜索树的插入

       将元素X插入二叉搜索树BST中，关键是要找到元素应该插入的位置。位置的确定可以利用与查找函数Find类似的方法，如果在树BST中找到X，说明要插入的元素已存在，可放弃插入操作。如果没找到X，查找终止的位置就是X应插入的位置。

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

2.4 二叉搜索树的删除

     考虑三种情况：

 要删除的是叶结点： 直接删除， 并再修改其父结点指针---置为null 

二叉搜索树的插入、删除、查找等操作：Java语言实现

  要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点


二叉搜索树的插入、删除、查找等操作：Java语言实现
 要删除的结点有左、右两棵子树：用另一结点替代被删除结点： 右子树的最小元素 或者 左子树的最大元素

二叉搜索树的插入、删除、查找等操作：Java语言实现

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

2.5 二叉搜索树的遍历

       二叉搜索树的遍历，与普通的二叉树的遍历一样。不太懂的，可以看下我的这两篇文章，《二叉树的非递归遍历：Java语言实现》、《二叉树的递归遍历：Java语言实现》。

       需要注意的是：中序遍历二叉搜索树时，将得到一个有序表。

//中序遍历：递归方法  (中序遍历二叉搜索树时，将得到一个有序表)
    void InOrderRecursive(BinarySearchTreeNode root) {
        if(root == null)
            return;
        InOrderRecursive(root.getLeft());//中序遍历其左子树
        System.out.print(root.getData() + " ");//访问根结点
        InOrderRecursive(root.getRight());//中序遍历其右子树
    } 

3 Java整体代码实现

3.1 建立二叉搜索树结点类

package Binary_Tree_Study;

/**
 * Created by Administrator on 2018/5/20.
 */
public class BinarySearchTreeNode {
    private int data;//结点的数据
    private BinarySearchTreeNode left;//指向左孩子结点
    private BinarySearchTreeNode right;//指向左孩子结点

    public BinarySearchTreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right =null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinarySearchTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinarySearchTreeNode left) {
        this.left = left;
    }

    public BinarySearchTreeNode getRight() {
        return right;
    }

    public void setRight(BinarySearchTreeNode right) {
        this.right = right;
    }
}

3.2 二叉搜索树的上述操作代码实现

package Binary_Tree_Study;

/**
 * Created by Administrator on 2018/5/20.
 */
public class BinarySearchTree {
    private BinarySearchTreeNode root;//根结点

    public BinarySearchTree() {
        this.root = null;
    }

    //查找元素：递归方法
    BinarySearchTreeNode find(BinarySearchTreeNode 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);//在右子树中继续查找
        else
            return root;//查找成功， 返回找到的结点的地址
    }

    //查找元素：非递归方法
    BinarySearchTreeNode iterFind(BinarySearchTreeNode root, int data) {
        while (root != null) {
            if (data < root.getData())
                root = root.getLeft();//向左子树中移动， 继续查找
            else if (data > root.getData())
                root = root.getRight();//向右子树中移动， 继续查找
            else
                return root;//查找成功， 返回找到的结点的地址
        }
        return null;//查询失败
    }

    //查找最小元素：递归方法 (最小元素一定是在树的最左分枝的端结点上)
    BinarySearchTreeNode findMin(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        else if (root.getLeft() == null)
            return root;//找到最左叶结点并返回
        else
            return findMin(root.getLeft());//沿左分支继续查找
    }

    //查找最小元素：非递归方法 (最小元素一定是在树的最左分枝的端结点上)
    BinarySearchTreeNode iterFindMin(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        while (root.getLeft() != null)
            root = root.getLeft();//沿左分支继续查找
        return root;//找到最左叶结点并返回
    }

    //查找最大元素：递归方法 (最大元素一定是在树的最右分枝的端结点上)
    BinarySearchTreeNode findMax(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        else if (root.getRight() == null)
            return root;//找到最右叶结点并返回
        else
            return findMax(root.getRight());//沿右分支继续查找
    }

    //查找最大元素：非递归方法 (最大元素一定是在树的最右分枝的端结点上)
    BinarySearchTreeNode iterFindMax(BinarySearchTreeNode root) {
        if (root == null)
            return null;//空的二叉搜索树，返回null
        while (root.getRight() != null)
            root = root.getRight();//沿右分支继续查找
        return root;//找到最右叶结点并返回
    }

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

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

    //中序遍历：递归方法  (中序遍历二叉搜索树时，将得到一个有序表)
    void InOrderRecursive(BinarySearchTreeNode root) {
        if(root == null)
            return;
        InOrderRecursive(root.getLeft());//中序遍历其左子树
        System.out.print(root.getData() + " ");//访问根结点
        InOrderRecursive(root.getRight());//中序遍历其右子树
    }

    //以下函数调用相应的方法
    public void callFindMin() {
        BinarySearchTreeNode cur = findMin(root);
        System.out.println("\n最小元素为：" + cur.getData());
    }

    public void callIterFindMin() {
        BinarySearchTreeNode cur = iterFindMin(root);
        System.out.println("\n最小元素为：" + cur.getData());
    }

    public void callFindMax() {
        BinarySearchTreeNode cur = findMax(root);
        System.out.println("\n最大元素为：" + cur.getData());
    }

    public void callIterFindMax() {
        BinarySearchTreeNode cur = iterFindMax(root);
        System.out.println("\n最大元素为：" + cur.getData());
    }

    public void callInsert(int data) {
        root = insert(root, data);
    }

    public void callDelete(int data) {
        root = delete(root, data);
    }

    public void callInOrderRecursive() {
        InOrderRecursive(root);
    }
}

3.3 测试

package Binary_Tree_Study;

/**
 * Created by Administrator on 2018/5/20.
 */
public class BinarySearchTreeTest {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        /* 创建如下的二叉搜索树
              5
           /     \
          3       7
         /  \    /  \
        2   4   6   8 */
        tree.callInsert(5);
        tree.callInsert(3);
        tree.callInsert(2);
        tree.callInsert(4);
        tree.callInsert(7);
        tree.callInsert(6);
        tree.callInsert(8);
        System.out.println("中序遍历为：");
        tree.callInOrderRecursive();//2 3 4 5 6 7 8
        tree.callFindMin();//最小元素为：2
        tree.callFindMax();//最大元素为：8
        System.out.println("\nD删除结点数据 2");
        tree.callDelete(2);
        System.out.println("删除删除结点数据2后的中序遍历为：");
        tree.callInOrderRecursive();//3 4 5 6 7 8
        tree.callIterFindMin();//最小元素为：3
        tree.callIterFindMax();//最大元素为：8
    }
}

4 参考资料

[1] 浙大数据结构慕课

[2] Binary Search Tree | Set 1 (Search and Insertion)

[3] Binary Search Tree

相关标签： 数据结构 二叉搜索树 Java Binary Search Tree

上一篇： 二叉搜索树(Binary Search Tree)

下一篇： 线性数据结构——顺序表

推荐阅读