记录下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
package com.yunos.tv.test;
 
/**
 * 二叉树算法
 *
 * @author 冻番茄 phpd.cn
 */
import com.alibaba.fastjson.JSON;
 
public class BstTest {
 
    public static void main(String[] args) {
        //初始化一个二叉树
        int[] n = { 8, 3, 10, 1, 6, 14, 4, 7, 13, 13, 1 };
        Node root = null;
        for (int i : n) {
            root = insert(root, i);
        }
        System.out.println(JSON.toJSONString(root, true));
        System.out.println(JSON.toJSONString(search(root, 6), true));
        root = delete(root, 8);
        root = delete(root, 1);
        System.out.println(JSON.toJSONString(root, true));
    }
 
    /**
     * 二叉树删除节点
     * @param node
     * @param key
     * @return
     */
    private static Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }
        //根据二叉树算法，当前节点小于key从左边查找并删除，反之从右边查找并删除
        if (key < node.getKey()) {
            node.setLeftNode(delete(node.getLeftNode(), key));
        } else if (key > node.getKey()) {
            node.setRightNode(delete(node.getRightNode(), key));
        } else {
            /*
             * 查找到的话进行删除操作，删除分三种情况
             * 1、该节点没有左右子节点则直接删除。
             * 2、同时有左节点并且有右节点需要从最左边取最大节点替换或从最右边取最小节点替换。
             * 3、只有左节点或只有右节点，把左节点或右节点直接替换被删除的节点
             */
            if (node.getLeftNode() == null && node.getRightNode() == null) {
                node = null;
            } else if (node.getLeftNode() != null && node.getRightNode() != null) {
                //从左边查找最大节点进行替换
                node = deleteByLeft(node, node.getLeftNode(), key);
                //从右边查找最小节点进行替换
                //node = deleteByRight(node, node.getRightNode(), key);
            } else if (node.getLeftNode() != null) {
                node = node.getLeftNode();
            } else if (node.getRightNode() != null) {
                node = node.getRightNode();
            }
        }
        return node;
    }
 
    /**
     * 要删除的节点同时有左右子节点时，从该删除节点右边查找出最小值的节点替换到删除的节点位置
     * @param sourceNode
     * @param rightNode
     * @param key
     * @return
     */
    private static Node deleteByRight(Node sourceNode, Node rightNode, int key) {
        if (rightNode.getLeftNode() == null) {
            sourceNode.setKey(rightNode.getKey());
            Node tmp = delete(sourceNode.getRightNode(), rightNode.getKey());
            sourceNode.setRightNode(tmp);
            return sourceNode;
        }
        return deleteByRight(sourceNode, rightNode.getLeftNode(), key);
 
    }
     
    /**
     * 要删除的节点同时有左右子节点时，从该删除节点左边查找出最大值的节点替换到删除的节点位置
     * @param sourceNode
     * @param leftNode
     * @param key
     * @return
     */
    private static Node deleteByLeft(Node sourceNode, Node leftNode, int key) {
 
        if (leftNode.getRightNode() == null) {
            sourceNode.setKey(leftNode.getKey());
            Node tmp = delete(sourceNode.getLeftNode(), leftNode.getKey());
            sourceNode.setLeftNode(tmp);
            return sourceNode;
        }
        return deleteByLeft(sourceNode, leftNode.getRightNode(), key);
 
    }
 
    /**
     * 在二叉树中快速查找一个节点
     * @param node
     * @param key
     * @return
     */
    private static Node search(Node node, int key) {
        if (node == null) {
            return null;
        }
        if (node.getKey() == key) {
            return node;
        }
        if (node.getKey() > key) {
            return search(node.getLeftNode(), key);
        } else {
            return search(node.getRightNode(), key);
        }
    }
 
    /**
     * 在二叉树中插入一个节点
     * @param node
     * @param key
     * @return
     */
    private static Node insert(Node node, int key) {
        if (node == null) {
            node = new Node();
            node.setKey(key);
        } else if (key == node.getKey()) {
            return node;
        } else if (key < node.key) {
            node.setLeftNode(insert(node.getLeftNode(), key));
            return node;
        } else {
            node.setRightNode(insert(node.getRightNode(), key));
        }
        return node;
    }
 
    public static class Node {
 
        private int     key;
        private Node    leftNode;
        private Node    rightNode;
 
        public int getKey() {
            return key;
        }
 
        public void setKey(int key) {
            this.key = key;
        }
 
        public Node getLeftNode() {
            return leftNode;
        }
 
        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }
 
        public Node getRightNode() {
            return rightNode;
        }
 
        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }
 
    }
 
}