数据结构10：二叉树专题_数据结构二叉树专题

二叉树实现插入节点、查找节点、删除节点、前序遍历、中序遍历、后序遍历。

package ch13;
/*
 * 二叉树类
 */
public class Tree {
    //根节点
    public Node root;

    /**
     * 插入节点
     * @param value
     */
    public void insert(long value,String sValue) {
        //封装节点
        Node newNode = new Node(value,sValue);
        //引用当前节点
        Node current = root;
        //引用父节点
        Node parent;
        //如果root为null，也就是第一插入的时候
        if(root == null) {
            root = newNode;
            return;
        } else {
            while(true) {
                //父节点指向当前节点
                parent = current;
                //如果当前指向的节点数据比插入的要大,则向左走
                if(current.data > value) {
                    current = current.leftChild;
                    if(current == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                } else {
                    current = current.rightChild;
                    if(current == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    /**
     * 查找节点
     * @param value
     */
    public Node find(long value) {
        //引用当前节点，从根节点开始
        Node current = root;
        //循环，只要查找值不等于当前节点的数据项
        while(current.data != value) {
            //进行比较，比较查找值和当前节点的大小
            if(current.data > value) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            //如果查找不到
            if(current == null) {
                return null;
            }
        }
        return current;
    }

    /**
     * 删除节点
     * @param value
     */
    public boolean delete(long value) {
        //引用当前节点，从根节点开始
        Node current = root;

        //应用当前节点的父节点
        Node parent = root;
        //是否为左节点
        boolean isLeftChild = true;

        while(current.data != value) {
            parent = current;
            //进行比较，比较查找值和当前节点的大小
            if(current.data > value) {
                current = current.leftChild;
                isLeftChild = true;
            } else {
                current = current.rightChild;
                isLeftChild = false;
            }
            //如果查找不到
            if(current == null) {
                return false;
            }
        }

        //删除叶子节点，也就是该节点没有子节点
        if(current.leftChild == null && current.rightChild == null) {
            if(current == root) {
                root = null;
            } else if(isLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        } else if(current.rightChild == null) {
            if(current == root) {
                root = current.leftChild;
            }else if(isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
        } else if(current.leftChild == null) {
            if(current == root) {
                root = current.rightChild;
            } else if(isLeftChild) {
                parent.leftChild = current.rightChild;
            } else {
                parent.rightChild = current.rightChild;
            }
        } else {
            Node successor = getSuccessor(current);
            if(current == root) {
                root = successor;
            } else if(isLeftChild) {
                parent.leftChild = successor;
            } else{
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
        }

        return true;


    }

    public Node getSuccessor(Node delNode) {
        Node successor = delNode;
        Node successorParent = delNode;
        Node current = delNode.rightChild;

        while(current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }

        if(successor != delNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }

    /**
     * 前序遍历
     */
    public void frontOrder(Node localNode) {
        if(localNode != null) {
            //访问根节点
            System.out.println(localNode.data + ", " + localNode.sData);
            //前序遍历左子树
            frontOrder(localNode.leftChild);
            //前序遍历右子树
            frontOrder(localNode.rightChild);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder(Node localNode) {
        if(localNode != null) {
            //中序遍历左子树
            inOrder(localNode.leftChild);
            //访问根节点
            System.out.println(localNode.data + ", " + localNode.sData);
            //中旬遍历右子树
            inOrder(localNode.rightChild);
        }
    }

    /**
     * 后序遍历
     */
    public void afterOrder(Node localNode) {
        if(localNode != null) {
            //后序遍历左子树
            afterOrder(localNode.leftChild);
            //后序遍历右子树
            afterOrder(localNode.rightChild);
            //访问根节点
            System.out.println(localNode.data + ", " + localNode.sData);
        }
    }
}
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