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

准备工作

• 由于用到了@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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120