二叉排序树查询删除结点和删除结点的父节点(代码实现) [Java]

二叉排序树查询删除结点和删除结点的父节点(代码实现)

因为我们执行二叉排序树的删除结点的操作的时候都要先获取删除结点和待删除结点的父节点, 所以我们就先编写查询待删除结点和待删除结点的父节点的方法

由于查询二叉排序树中待删除结点的方法和查询二叉排序树中待删除结点的父节点的操作中都要使用到递归, 所以这个时候我们还是使用之前的方式将我们的递归方法编写到Node结点类中

Node类中的查询删除结点和删除结点的父节点的递归方法:

//结点类中查找待删除结点的递归方法
public Node search(int val){
    //1. 递归结束条件
    if(this.value == val){
        //如果当前节点的value值等于val值, 那么就表示当前节点就是我们要查询的结点
        return this;
    }

    //如果val值大于当前节点的value值, 那么就向右子树去判断
    else if(val > this.value){
        if(this.right == null){
            return null;
        }else{
            //此时一定要记得将我们查询到的结点一层一层的返回回来, 因为我们此时其实就是要求我们的待删除结点, 当找到了待删除结点之后一定要将待删除结点返回, 如果找不到就返回一个null
            return this.right.search(val);
        }
    }

    //如果val值小于当前节点的value值, 那么就向左子树去判断
    else{
        if(this.left == null){
            //如果左子节点为null的时候就表示当前二叉排序树中没有我们正在查询的结点
            return null;
        }else{
            return this.left.search(val);
        }
    }
}

//Node类中的递归查找待删除结点的父节点的方法
public Node searchParent(int val){
    //1. 递归终止条件
    // 如果当前节点的左子节点或者右子节点的值等于val值, 那么就表明当前的结点为待删除结点的父节点, 我们就直接将当前节点返回即可
    if((this.left != null && this.left.value == val) || (this.right != null && this.right.value == val)){
        return this;
    }

    //如果当前节点的左右孩子节点的值都不和val相等, 那么就判断当前节点的value属性值和val值的大小
    //如果当前节点的value属性值大于val值, 那么就去左子树上进行查找
    if(this.value > val && this.left != null){
        return this.left.searchParent(val);
    }

    if(this.value < val && this.right != null){
        return this.right.searchParent(val);
    }

    return null;
}
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

二叉排序树中对外提供的查询待删除结点和待删除结点的父节点的方法:

//查询待删除节点的方法
public Node search(int val){
    if(root != null) {
        //判断引用是否为空,如果引用不为空就调用递归方法
        return root.search(val);
    }else{
        //如果引用为空, 返回一个null
        return null;
    }
}

//查询待删除结点的父节点的方法
public Node searchParent(int val){
    if(root != null) {
        //如果引用是否为空, 如果引用为空, 那么调用方法的时候出现空指针, 所以我们要避免这种空指针
        return root.searchParent(val);
    }else{
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试代码:

/**
     * 测试方法, 测试我们编写的二叉排序树类中的方法是否是正确的
     * @param args
     */
public static void main(String[] args) {
    //创建一个二叉排序树类
    BinarySortTree binarySortTree = new BinarySortTree();

    //我们先创建几个结点
    Node node1 = new Node(2);
    Node node2 = new Node(31);
    Node node3 = new Node(42);
    Node node4 = new Node(1);
    Node node5 = new Node(1);
    Node node6 = new Node(24);
    Node node7 = new Node(12);

    //然后调用我们添加结点的方法将我们节点添加到我们的二叉排序树类中
    binarySortTree.add(node1);
    binarySortTree.add(node2);
    binarySortTree.add(node3);
    binarySortTree.add(node4);
    binarySortTree.add(node5);
    binarySortTree.add(node6);
    binarySortTree.add(node7);

    //调用中序遍历方法进行一个测试
    binarySortTree.infixOrder();
    System.out.println("---------------------------------------------------");

    //查询42
    Node search = binarySortTree.search(42);
    System.out.println(search);

    //查询值为42的结点的父节点
    Node node = binarySortTree.searchParent(42);
    System.out.println(node);
}
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

接下来我们给出整个的二叉排序树类代码包括测试代码:

• 其中包括向二叉排序树中添加结点的方法和遍历的方法, 还有查询待删除结点和查询待删除结点的父节点的方法

package com.ffyc.tree.threadedbinarytree;

//首先我们先来创建一个Node结点类, 我们创建一个Node结点类之后在Node结点类中实现两个递归方法, 一个方法是递归来增加结点的方法, 一个是来递归遍历的方法
class Node{
    int value;
    Node left;
    Node right;

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

    //添加结点的方法
     //递归的形式添加结点, 注意: 需要满足是二叉排序树的需求

    /**
     * @param node 这个node是待添加的结点
     */
    public void add(Node node){
        //这个递归方法我们每次递归的时候是改变的方法的调用者

        //1.判断入参
          // 注意: 这个时候只是我们对入参的判断 , 并不是递归的结束条件
        if(node == null){//如果待添加结点是一个null的时候那么我们就不用添加这个节点了, 直接就退出就可以了
            return; //由于此时我们实现的递归方法是没有返回值的, 所以这个时候我们我们直接退出就可以了
        }

        //如果node的值不为空, 那么就说明这个节点是合法的, 所以我们就要来判断这个节点要添加的位置
        if(node.value < this.value) {//如果这个时候node节点的value值要小于我们的this的value的值, 那么我们肯定是要去左子树上继续查找, 所以这个时候我们就要使用左子节点来递归调用此方法
            if(this.left != null){
                //如果当前节点的左子节点不为空的时候此时我们才继续向左子树去遍历,如果这个时候左子节点为空了, 那么就表明这个位置其实我们是已经找到了
                this.left.add(node);
            }else{
                //如果当前节点的左子节点为空, 那么就证明这个位置就是我们节点要添加的位置, 我们此时就就将我们的节点直接放到当前节点的左子节点的位置即可
                this.left = node;
            }
        }else { //如果node的值(也就是待添加结点的值大于或者是等于我们当前节点的value值的时候我们就要向右子树上进行遍历)
                  // 这个时候一定要注意: 我们此时如果等于的时候也是向右子树去查找位置了, 就说明最后的时候我们如果两个结点的值是一样大的, 那儿我们将这个节点添加到了右子树上
                  // 对应的如果执行其他的二叉排序树的操作的时候如果我们要判断两个值相同的情况的时候我们就要去右子树上去看
            if(this.right != null) {
                //判断当前节点的右子节点是否为null ,如果不为空的时候我们就递归的向右子树进行一个遍历
                this.right.add(node);

            }else{
                //如果此时当前节点的右子节点为空了,那么就表示我们找到了待插入节点的插入位置, 我们直接将我们的待插入节点插入即可
                this.right = node;
            }
        }
    }

    //中序遍历(注意: 我们的二叉排序树的中序遍历之后的结果是一个有序序列, 如果这个时候我们构建的二叉排序树使用中序遍历之后的结果是一个有序的序列的时候我们就说明我们这个二叉排序树是没有问题的)
      // 注意:我们此时的中序遍历只是为了判断我们的当前的二叉排序树的创建和添加元素的方法是否是正确的
    //因为此时我们的二叉排序树的中序遍历的方法是编写到了Node结点类中, 所以其实执行递归调用的时候改变的是这个遍历方法的调用者
    public void infixOrder(){
        //此递归方法中我们并没有将递归终止条件写明, 这个方法时没有返回值的, 所以我们这里采用的方式是如果满足递归条件的时候我们才执行递归操作,
        //如果不满足递归条件的时候我们就直接执行完了, 因为这个方法中没有任何是需要执行的

        if(this.left != null) {
            //递归的向左判断
            this.left.infixOrder();
        }

        //输出当前元素
        System.out.println(this.value);

        if(this.right != null) {
            //递归的向右判断
            this.right.infixOrder();
        }
    }

    //结点类中查找待删除结点的递归方法
    public Node search(int val){
        //1. 递归结束条件
        if(this.value == val){
            //如果当前节点的value值等于val值, 那么就表示当前节点就是我们要查询的结点
            return this;
        }

        //如果val值大于当前节点的value值, 那么就向右子树去判断
        else if(val > this.value){
            if(this.right == null){
                return null;
            }else{
                //此时一定要记得将我们查询到的结点一层一层的返回回来, 因为我们此时其实就是要求我们的待删除结点, 当找到了待删除结点之后一定要将待删除结点返回, 如果找不到就返回一个null
                return this.right.search(val);
            }
        }

        //如果val值小于当前节点的value值, 那么就向左子树去判断
        else{
            if(this.left == null){
                //如果左子节点为null的时候就表示当前二叉排序树中没有我们正在查询的结点
                return null;
            }else{
                return this.left.search(val);
            }
        }
    }

    //Node类中的递归查找待删除结点的父节点的方法
    public Node searchParent(int val){
        //1. 递归终止条件
          // 如果当前节点的左子节点或者右子节点的值等于val值, 那么就表明当前的结点为待删除结点的父节点, 我们就直接将当前节点返回即可
        if((this.left != null && this.left.value == val) || (this.right != null && this.right.value == val)){
            return this;
        }

        //如果当前节点的左右孩子节点的值都不和val相等, 那么就判断当前节点的value属性值和val值的大小
         //如果当前节点的value属性值大于val值, 那么就去左子树上进行查找
        if(this.value > val && this.left != null){
            return this.left.searchParent(val);
        }

        if(this.value < val && this.right != null){
            return this.right.searchParent(val);
        }

        return null;
    }

    //重写toString()方法

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

/**
 * 创建一个二叉排序树类,在二叉排序树类中向外提供添加元素和遍历的方法
 */
public class BinarySortTree {
    //声明当前二叉排序树类的根节点
    private Node root;

    //创建添加元素的方法
    public void add(Node node){
        //这个时候我们要使用root引用数据来调用add()方法, 此时我们就要在调用方法之前判断当前的root引用是否为空, 要做一个合法性判断
        if(root != null){
            root.add(node);
        }else{
            //如果根节点为空的时候就直接将这值副给根节点即可
            root = node;
        }
    }

    //中序遍历方法
    public void infixOrder(){
        //这个时候同样我们也是要使用root引用数据来调用方法, 所以我们就要判断这个root引用是否为空
        if(root != null){
            root.infixOrder();
        }else{
            //如果这个root值不为空的时候就直接退出即可,顺便可以打印一个提示信息
            System.out.println("当前链表为空~~~");
            return;
        }
    }

    //查询待删除节点的方法
    public Node search(int val){
        if(root != null) {
            //判断引用是否为空,如果引用不为空就调用递归方法
            return root.search(val);
        }else{
            //如果引用为空, 返回一个null
            return null;
        }
    }

    //查询待删除结点的父节点的方法
    public Node searchParent(int val){
        if(root != null) {
            //如果引用是否为空, 如果引用为空, 那么调用方法的时候出现空指针, 所以我们要避免这种空指针
            return root.searchParent(val);
        }else{
            return null;
        }
    }


    /**
     * 测试方法, 测试我们编写的二叉排序树类中的方法是否是正确的
     * @param args
     */
    public static void main(String[] args) {
        //创建一个二叉排序树类
        BinarySortTree binarySortTree = new BinarySortTree();

        //我们先创建几个结点
        Node node1 = new Node(2);
        Node node2 = new Node(31);
        Node node3 = new Node(42);
        Node node4 = new Node(1);
        Node node5 = new Node(1);
        Node node6 = new Node(24);
        Node node7 = new Node(12);

        //然后调用我们添加结点的方法将我们节点添加到我们的二叉排序树类中
        binarySortTree.add(node1);
        binarySortTree.add(node2);
        binarySortTree.add(node3);
        binarySortTree.add(node4);
        binarySortTree.add(node5);
        binarySortTree.add(node6);
        binarySortTree.add(node7);

        //调用中序遍历方法进行一个测试
        binarySortTree.infixOrder();
        System.out.println("---------------------------------------------------");

        //查询42
        Node search = binarySortTree.search(42);
        System.out.println(search);

        //查询值为42的结点的父节点
        Node node = binarySortTree.searchParent(42);
        System.out.println(node);
    }

}
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