JAVA实现平衡二叉树_java 什么是平衡二叉树

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhouhang
 */
public class BalenceBinaryTree {
    private int size;
    private Node root;


    public BalenceBinaryTree() {
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public Node getRoot() {
        return root;
    }


    /**
     * 先序遍历 根左右
     *
     * @param root
     */
    public void firstTraversal(Node root) {
        System.out.print(root.getValue());
        if (root.getLeft() != null) {
            firstTraversal(root.getLeft());
        }
        if (root.getRight() != null) {
            firstTraversal(root.getRight());
        }
    }

    /**
     * 中序遍历 左根右
     *
     * @param root
     */
    public void midTraversal(Node root) {
        if (root.getLeft() != null) {
            midTraversal(root.getLeft());
        }
        System.out.print(root.getValue());
        if (root.getRight() != null) {
            midTraversal(root.getRight());
        }
    }

    /**
     * 后序遍历 左右根
     *
     * @param root
     */
    public void lastTraversal(Node root) {
        if (root.getLeft() != null) {
            lastTraversal(root.getLeft());
        }
        if (root.getRight() != null) {
            lastTraversal(root.getRight());
        }
        System.out.print(root.getValue());
    }

    /**
     * 往树上追加子节点
     *
     * @param value 待添加的值
     * @param node  被附加的节点
     * @return 平衡后的子树的根节点
     */
    public Node append(int value, Node node) {
        if (size == 0) {
            size++;
            root = new Node(value);
            return root;
        }
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value < node.getValue()) {
            //添加到左子节点
            node.setLeft(append(value, node.getLeft()));
        } else if (value > node.getValue()) {
            //添加到右子节点
            node.setRight(append(value, node.getRight()));
        } else {//节点值等于待添加值
            System.out.println("节点已存在，不再添加");
            return node;
        }
        return rotate(node);
    }

    /**
     * 查看某个值在树种树否存在
     *
     * @param value 待查看的值
     * @return
     */
    public Node find(int value) {
        Node temp = root;
        if (size == 0) {
            return null;
        }
        while (true) {
            if (value < temp.getValue()) {
                if (temp.getLeft() == null) {
                    return null;
                } else {
                    temp = temp.getLeft();
                }
            } else if (value == temp.getValue()) {
                return temp;
            } else if (value > temp.getValue()) {
                if (temp.getRight() == null) {
                    return null;
                } else {
                    temp = temp.getRight();
                }
            }
        }
    }

    /**
     * 树根深度定义为1
     *
     * @return 该节点深度
     */
    public int depth(int value) {
        if (size == 0) {
            return 0;
        }
        Node temp = root;
        int depth = 1;//当前遍历的节点的深度
        while (true) {
            if (value == temp.getValue()) {
                return depth;
            } else if (value < temp.getValue()) {
                if (temp.getLeft() == null) {
                    System.out.println("找不到节点");
                    return 0;
                } else {
                    depth++;
                    temp = temp.getLeft();
                }
            } else if (value > temp.getValue()) {
                if (temp.getRight() == null) {
                    System.out.println("找不到节点");
                    return 0;
                } else {
                    depth++;
                    temp = temp.getRight();
                }
            }
        }
    }

    /**
     * 层序打印二叉树
     *
     * @param value
     * @return
     */
    public void printTree() {
        ArrayList<Node> list = new ArrayList<Node>();
        if (root == null) {
            System.out.println("空树不打印");
            return;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);//添加节点
        while (!queue.isEmpty()) {
            Node treeNode = queue.poll();//首节点出列
            if (treeNode.getLeft() != null) {
                queue.offer(treeNode.getLeft());//左子节点入列
            }
            if (treeNode.getRight() != null) {
                queue.offer(treeNode.getRight());//右子节点入列
            }
            list.add(treeNode);
        }
        for (int i = 0; i < size; i++) {
            System.out.print(list.get(i).getValue());
            System.out.print(" ");
            if (size >= i + 2 && depth(list.get(i).getValue()) != depth(list.get(i + 1).getValue())) {
                System.out.println();
            }
        }
        System.out.println();
    }


    /**
     * 不平衡产生于右子树的右子树，需要左旋
     * 把右子树的左子树作为根的右子树，把右子树的根作为新根
     *
     * @return
     */
    public Node leftRotate(Node node) {
        Node right = node.getRight();
        node.setRight(right.getLeft());
        right.setLeft(node);
        node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        right.setHeight(Math.max(height(right.getLeft()), height(right.getRight())) + 1);
        if(node==root){
            root=right;
        }
        return right;
    }

    /**
     * 不平衡产生于左子树的左子树，需要右旋
     * 把左子树的右子树作为根的左子树，把左子树的根作为新根
     *
     * @return
     */
    public Node rightRotate(Node node) {
        Node left = node.getLeft();
        node.setLeft(left.getRight());
        left.setRight(node);
        node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        left.setHeight(Math.max(height(left.getLeft()), height(left.getRight())) + 1);
        if(node==root){
            root=left;
        }
        return left;
    }


    
    /**
     * 旋转
     *
     * @param node
     * @return
     */
    public Node rotate(Node node) {
        if (node == null) {
            return null;
        }

        //不平衡来源于左子
        if (height(node.getLeft()) > height(node.getRight()) + 1) {//左子树比右子树高
            if (height(node.getLeft().getLeft()) >= height(node.getLeft().getRight())) {//左子的左子高于左子的右子
                node = rightRotate(node);//当前树右旋
            } else {//左子的右子高于左子的左子
                Node temp = leftRotate(node.getLeft());//左子左旋
                node.setLeft(temp);//左子更新
                node=rightRotate(node);//当前树右旋
            }
        } else if (height(node.getRight()) > height(node.getLeft()) + 1) {//不平衡来源于右子
            if (height(node.getRight().getRight()) >= height(node.getRight().getLeft())) {//右子的右子高于右子的左子
                node = leftRotate(node);//当前树左旋
            } else {
                Node temp = rightRotate(node.getRight());//右子右旋
                node.setRight(temp);//更新右子
                node=leftRotate(node);//当前树左旋
            }
        }else{//平衡 不旋转 只更新节点高度
            node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
        }

        return node;
    }


    /**
     * 树叶的高度定义为1
     *
     * @return 该节点高度
     */
    public int height(Node node) {
        return node == null ? -1 : node.getHeight();
    }

    /**
     * 入口
     *
     * @param args
     */
    public static void main(String[] args) {
        BalenceBinaryTree bt = new BalenceBinaryTree();
        bt.append(9, null);
        bt.append(8, bt.getRoot());
        bt.append(3, bt.getRoot());
        bt.append(4,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(7,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(6,bt.getRoot());//BUG
        bt.append(1,bt.getRoot());
        bt.append(2,bt.getRoot());
        bt.append(5,bt.getRoot());
        bt.append(0,bt.getRoot());
        bt.append(10,bt.getRoot());
        bt.append(11,bt.getRoot());
        bt.append(12,bt.getRoot());
        bt.append(13,bt.getRoot());
        bt.append(14,bt.getRoot());
        bt.append(15,bt.getRoot());
        bt.append(16,bt.getRoot());
        bt.append(17,bt.getRoot());
        bt.firstTraversal(bt.getRoot());
        System.out.println();
        bt.midTraversal(bt.getRoot());
        System.out.println();
        bt.lastTraversal(bt.getRoot());
        System.out.println();
        bt.printTree();
        System.out.println("树总高度" + bt.height(bt.getRoot()));

    }
}


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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325

/**
 * @author zhouhang
 */
public class Node {

    private Node left;
    private Node right;
    private int value;
    private int height;

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public Node(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

}

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