【代码】树之二叉树

发表于 更新于 阅读次数：

前言

数之二叉（查找）树的Java版代码实现

源代码

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
package com;

public class BinaryTree<Key extends Comparable<Key>, Value> {

    public Node root;
    public int BinaryTreeLength;

    private class Node {
        public Key key;
        public Value value;
        public Node left;
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 获取元素的个数
     * @return
     */
    public int size() {
        return BinaryTreeLength;
    }

    /**
     * 向树中插入一个值
     * @param key
     * @param value
     */
    public void put(Key key, Value value) {
        root = put(key, value, root);
    }

    /**
     * 向指定树中插入一个值
     * @param key
     * @param value
     * @param node
     * @return 返回添加后的新树
     */
    private Node put(Key key, Value value, Node node) {
        // 如果子树为空
        if (node==null) {
            // 长度自增
            BinaryTreeLength++;
            return new Node(key, value, null, null);
        }
        // 如果子树不为空，进行比较
        int cmp = key.compareTo(node.key);
        // 如果key小于node树的key
        if (cmp < 0) {
            // 继续找node的左子树
            node.left = put(key, value, node.left);
        }
        // 如果key大于node树的key
        else if (cmp > 0) {
            // 继续找node的右子树
            node.right = put(key, value, node.right);
        }
        // 如果key等于node树的key
        else {
            // 替换对应树的value
            node.value = value;
        }
        return node;
    }

    /**
     * 根据Key获取Value
     * @param key
     * @return
     */
    public Value get(Key key) {
        return get(key, root);
    }

    /**
     * 根据Key获取指定树的Value
     * @param key
     * @param node
     * @return
     */
    public Value get(Key key, Node node) {
        // 如果子树为空
        if (node==null) {
            return null;
        }
        Value value = null;
        // 如果子树不为空，进行比较
        int cmp = key.compareTo(node.key);
        // 如果key小于node树的key
        if (cmp < 0) {
            // 继续找node的左子树
            return get(key, node.left);
        }
        // 如果key大于node树的key
        else if (cmp > 0) {
            // 继续找node的右子树
            return get(key, node.right);
        }
        // 如果key等于node树的key
        else {
            // 找到了当前结点的value
            return node.value;
        }

    }

    /**
     * 根据Key删除元素
     * @param key
     */
    public void delete(Key key) {
        delete(key, root);
    }

    /**
     * 根据Key删除指定树的元素
     * @param key
     * @param node
     * @return 返回删除后的新树
     */
    private Node delete(Key key, Node node) {
        if (node==null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            delete(key, node.left);
        } else if (cmp > 0) {
            delete(key, node.right);
        } else {
            // 完成真正的删除结点的操作

            // 长度自减
            BinaryTreeLength--;

            // 当左子树为空，那就直接返回右子树
            if (node.left==null) {
                return node.right;
            }
            // 当右子树为空，那就直接返回左子树
            if (node.right==null) {
                return node.left;
            }
            // 找到右子树中最小的结点
            // 一直找左子树，直到没有左子树为止
            Node minNode = node.right;
            while (minNode.left!=null) {
                minNode = minNode.left;
            }
            // 删除右子树中最小的结点
            Node n = node.right;
            while (n.left!=null) {
                if (n.left.left==null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            // 让当前结点的左子树成为minNode结点的左子树
            minNode.left = node.left;
            // 让当前结点的右子树成为minNode结点的右子树
            minNode.right = node.right;
            // 让当前结点的父结点成为minNode结点的父结点
            node = minNode;
        }
        return node;
    }



}

完成

参考文献

哔哩哔哩——黑马程序员