二叉搜索树的模拟实现——Java数据结构

ゝ一纸荒年。 2024-04-23 15:34 45阅读 0赞

## 概念： ##

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

> **?若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值** 
> 
> **?它的左右子树也分别为二叉搜索树**

![090fb26ecb0c4f39964194f3c7f3eb56.png][]

模拟实现的代码：

public class BinarySearchTree {
    
    
       static class TreeNode {
            public int key;
            public TreeNode left;
            public TreeNode right;
            TreeNode(int key) {
                this.key = key;
            }
        }
        public TreeNode root;
        public void insert(int key) {
            if (root == null) {
                root = new TreeNode(key);
            }
            else {
                TreeNode parent = null;
                TreeNode cur = root;
                TreeNode node = new TreeNode(key);
                while (cur != null) {
                    // 为什么不在while循环了出现node,因为对于二叉搜索树来说，我们都是在叶子结点的位置插入元素，你想想后面的元素是要先遍历到叶子结点，然后在插入
                    // 因为每次插入新结点都要从上到下遍历一遍二叉树，不能在中间就把结点盲目的插入了，这样不符合二叉搜索树的要求
                    if (cur.key > key) {
                        parent = cur;
                        cur = cur.left;
                    }
                    else if (cur.key < key) {
                        parent = cur;
                        cur = cur.right;
                    }
                    else {
                        return; // 插入元素的值不能相同，二叉搜索树的要求
                    }
                }
                // 当程序走到这，cur == null
                if (parent.key > key) {
                    parent.left = node;
                }
                else {
                    parent.right = node;
                }
            }
        }
        // 如果是二叉搜索树，中序遍历的值就是有序的
        public void inorder(TreeNode root) {
            if (root == null) {
                return;
            }
            inorder(root.left);
            System.out.print(root.key + " ");
            inorder(root.right);
        }
        // 二叉搜索树的查找
        public TreeNode search(int key) {
            TreeNode cur = root;
            while (cur != null) {
                if (cur.key < key) {
                    cur = cur.right;
                }
                else if (cur.key > key) {
                    cur = cur.left;
                }
                else {
                    return cur;
                }
            }
    
            return null;
        }
        // 二叉搜索树的删除操作
        public boolean remove(int key) {
            TreeNode cur = root;
            TreeNode parent = null;
            while (cur != null) {
                if (cur.key > key) {
                    parent = cur;
                    cur = cur.left;
                }
                else if (cur.key < key) {
                    parent = cur;
                    cur = cur.right;
                }
                else {
                    removeKey(parent, cur);
                    return true;
                }
            }
            return false;
        }
        // 删除结点的具体操作
        public void removeKey(TreeNode parent, TreeNode cur) {
            if (cur.right == null) {
                if (cur == root) {
                    root = cur.left;
                }
                if (parent.key < cur.key) {
                    parent.right = cur.left;
                }
                else {
                    parent.left = cur.left;
                }
            }
            else if (cur.left == null) {
                if (cur == root) {
                    root = cur.right;
                }
                if (parent.key < cur.key) {
                    parent.right = cur.right;
                }
                else {
                    parent.left = cur.right;
                }
            }
            else {  // 当要删除结点的左右子结点都不为空的时候
                TreeNode targetParent = cur;
                TreeNode target = cur.right; // 我们所寻找的target就是要删除结点cur的右子树的最小值
                // 寻找要删除结点cur的右子树的最小值，将该最小值所对应的结点的值覆盖掉要删除的结点的值，
                // 此时要删除的结点就相当于是删除了，并且此时满足二叉搜索树的性质（不要忘了把最小值的原位置结点给删除）
                // 对于最小值结点来说，他的左子结点一定为空（删除方法和我们上面的方法是一样的）
                while (target.left != null) {
                    targetParent = target;
                    target = target.left;
                }
                // 此时的target要删除结点cur的右子树的最小值所对应的结点
                cur.key = target.key;  // 用target的值覆盖掉要删除结点cur的值
                // 覆盖掉后把target结点删除， 对于最小值结点来说，他的左子结点一定为空（删除方法和我们上面的方法是一样的）
                if (targetParent.key > target.key) {
                    targetParent.left = target.right;
                }
                else {
                    targetParent.right = target.right;
                }
            }
        }
    }

测试代码

>     public class Test {
>         public static void main(String[] args) {
>             BinarySearchTree binarySearchTree = new BinarySearchTree();
>             int[] array = {12, 32, 2, 43, 21, 14};
>             for (int i = 0; i < array.length; i++) {
>                 binarySearchTree.insert(array[i]);
>             }
>             binarySearchTree.inorder(binarySearchTree.root);
>             System.out.println();
>             // 如果TreeNode不是静态内部类需要这样实例化——BinarySearchTree.TreeNode treeNode = binarySearchTree.new TreeNode(12);
>             // 静态内部类直接— BinarySearchTree.TreeNode treeNode = new BinarySearchTree.TreeNode(12);
>             BinarySearchTree.TreeNode ret = binarySearchTree.search(423);
>             try {
>                 System.out.println(ret.key);
>             } catch (NullPointerException e) {
>                 System.out.println("该二叉搜索树中没有你要查找的结点");
>                 //e.printStackTrace();
>             }
>             System.out.println("==========================");
>             binarySearchTree.remove(32);
>             binarySearchTree.inorder(binarySearchTree.root);
>         }
>     }

![c13a32e5d25645d08b4e0b8865c60b7b.png][]

[090fb26ecb0c4f39964194f3c7f3eb56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fa02ab3922c44b71ae3ba64a647c89ed.png
[c13a32e5d25645d08b4e0b8865c60b7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/64f944aebbf641acaefad1d05a363441.png