java数据结构-手写二叉搜索树（二叉排序树）

怼烎@ 2023-10-07 20:17 40阅读 0赞

#### 准备工作 ####

*  由于用到了`@Data`注释，所以引入Lombok依赖（可不用）
 *  `BinaryTree`类：二叉树对象，包含节点的新增、删除、查询方法
 *  `Node`类：树节点对象

#### 代码实现 ####

##### Node树节点对象 #####

import lombok.Data;
    
    /**
     * @Date: 2022/10/11 11:37
     * @Description: 二叉树节点
     */
    @Data
    public class Node {
        int value;
        Node left;
        Node right;
    
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

##### BinaryTree二叉树对象 #####

import lombok.Data;
    
    /**
     * @Date: 2022/10/11 16:18
     * @Description: 搜索二叉树，注意：没有重复的元素
     */
    @Data
    public class BinaryTree {
        /**
         * 根节点
         */
        private Node root;
    
        /**
         * 增加节点
         */
        public void add(int e) {
            root = addRecursive(root, e);
        }
    
        private Node addRecursive(Node current, int e) {
            if (current == null) {
                return new Node(e, null, null);
            }
            if (e > current.value) {
                current.right = addRecursive(current.right, e);
            } else if (e < current.value) {
                current.left = addRecursive(current.left, e);
            } else {
                //该节点已存在
                return current;
            }
            return current;
        }
    
        /**
         * 查询节点
         */
        public Node search(int e) {
            return searchRecursive(root, e);
        }
    
        private Node searchRecursive(Node currentNode, int e) {
            if (currentNode == null) {
                return null;
            }
            if (e > currentNode.value) {
                return searchRecursive(currentNode.right, e);
            } else if (e < currentNode.value) {
                return searchRecursive(currentNode.left, e);
            } else {
                return currentNode;
            }
        }
    
        /**
         * 删除节点
         */
        public Node delete(int e) {
            return deleteRecursive(root, e);
        }
    
        private Node deleteRecursive(Node current, int e) {
            if (current == null) {
                return null;
            }
            if (e > current.value) {
                current.right = deleteRecursive(current.right, e);
                return current;
            } else if (e < current.value) {
                current.left = deleteRecursive(current.left, e);
                return current;
            } else {
                //节点没有子节点 -这是最简单的情况; 我们只需要在其父节点中用 null 替换此节点
                if (current.left == null && current.right == null) {
                    return null;
                }
                //节点只有一个子节点 -在父节点中，我们用它唯一的子节点替换该节点。
                if (current.left == null) {
                    return current.right;
                }
                if (current.right == null) {
                    return current.left;
                }
                //节点有左右2个子节点时，用节点右侧最小节点代替被删除节点，再将右侧节点中删除该节点
                int smallestValue = findSmallestValue(current.right);
                current.value = smallestValue;
                current.right = deleteRecursive(current.right, smallestValue);
                return current;
            }
        }
    
        /**
         * 找出节点下最小节点
         */
        private int findSmallestValue(Node node) {
            return node.left == null ? node.value : findSmallestValue(node.left);
        }
    
    
        public static void main(String[] args) {
            BinaryTree binaryTree = new BinaryTree();
            binaryTree.add(5);
            binaryTree.add(3);
            binaryTree.add(8);
            binaryTree.add(2);
            binaryTree.add(4);
            binaryTree.add(7);
            binaryTree.add(15);
            binaryTree.add(13);
            binaryTree.add(14);
            binaryTree.add(10);
            binaryTree.add(12);
            binaryTree.add(11);
            System.out.println(binaryTree);
            System.out.println(binaryTree.search(8));
            binaryTree.delete(8);
            System.out.println(binaryTree);
        }
    }