AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

BST（二叉搜索树）原理解析及代码实现_要解析数据才行,拿bst当例子就是得完整看到bst的波形

作者：AllinToyou | 2024-05-15 10:07:51

踩

要解析数据才行,拿bst当例子就是得完整看到bst的波形

文章目录

简介
二叉搜索树介绍
二叉树的中序遍历
插入结点
删除结点
完整代码：

简介

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；

二叉搜索树介绍

二叉排序树：BST（Binary Search Tree），对于二叉搜索树的任何一个非叶子结点。要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或者右子节点。

二叉搜索树是能够高效地进行如下操作的数据结构

插入一个数值
查询是否包含某个数值
删除某个数值

在二叉搜索树中：

若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
任意结点的左、右子树也分别为二叉搜索树。

比如数据（7，3，10，12，5，1，9），对应的二叉排序树为
在这里插入图片描述

再次基础上插入2：
在这里插入图片描述

二叉树的中序遍历

在这里插入图片描述
如上图中序遍历（先输出左子节点然后是当前节点最后是右节点）后的输出为：
1，2，3，5，7，9，10，12
为递增序列

代码：

Node节点中的方法：（以便于在tree中调用）

public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right != null) {
            this.right.infixOrder();
        }
    }
1
2
3
4
5
6
7
8
9
10
11

在二叉搜索树中的中序遍历：

 public void infixOrder(){
       if (root!=null){
           root.infixOrder();
       }else {
           System.out.println("树为空，无法遍历");
       }
    }
1
2
3
4
5
6
7

插入结点

插入结点比较简单，主要逐个比较要插入结点，与当前结点的值的大小即可，如果小于当前结点的值。就继续往左边找，大于等于往右边找；

代码：
Node结点中的add代码

 //添加结点的方法
    public void add(Node node) {
        if (node == null) {
            return;
        }

        if (node.getData() < this.getData()) {
            //如果小就往左边插入
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
            //大于等于向右添加
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

BinarySortTree 中的插入结点的代码：

public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
1
2
3
4
5
6
7

删除结点

叶子节点：直接删除，不影响原树。

思路：
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.根据targetNode是parent结点的左子节点还是右子结点
4.根据对应的情况进行删除
如果是parent的左子节点：parent.left = null；
如果是parent的右子节点：parent.right = null；

仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。

思路：
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.根据targetNode是parent结点的左子节点还是右子结点
4.1如果是parent的左子节点
如果target.left=null,那么令parent.left = target.right即可
如果target.right = null，那么令parent.left = target.left即可
4.2如果是parent的右子节点
如果target.left=null,那么令parent.right = target.right即可
如果target.right = null，那么令parent.right = target.left即可

既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。

思路：
上面我们可以直到中序遍历的结果是一个升序的输出，那么我们是不是可以找一个结点代替这个要删除的结点，找那个了，就找输出序列根target相邻的结点，即左子树的最大值，或者右子树的最小值，具体是那个？你如果你插入值得时候相同得值放在右子树，那么删除得时候就找左子树得最大值，反之亦然。
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.从target得左子树或者右子树找到代替得点
4.用一个临时变量保存这个结点
5.然后删除这个结点
6.令target.value = temp.value即可

代码实现：

Node中得查找目标结点，查找父节点

  //查找要删除的结点
    public Node search(int value) {

        //如果要查找的值等于当前结点的值 则直接返回
        if (this.getData() == value) {
            return this;
        }

        //如果不是当前值，并且要查找的值小于当前结点的值 则往左边进行查找
        if (value < this.data) {
            //如果左结点不为空 则向左查找
            if (this.getLeft() != null) {
                return this.getLeft().search(value);
            } else {//为空则直接返回null 即没找到
                return null;
            }
        } else {//在右边查找
            //右子结点不为空 在右边查找
            if (this.getRight() != null) {
                return this.getRight().search(value);
            } else {
                return null;
            }
        }

    }

    //得到要删除结点的父节点
    public Node searchParent(int value) {
        //如果要删除的是根节点  逻辑在tree中处理即可
        //如果当前结点的子结点就是要删除的结点  则直接返回
        if ((this.left != null && this.left.data == value) || (this.right != null && this.right.data == value)) {
            return this;
        } else {
            //如果查找的值 小于当前结点的值 就向左边查找
            if (value < this.data && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.data && this.right != null) {//向右
                return this.right.searchParent(value);
            } else {
                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

BinarySortTree中得删除代码：

public void deleteNode(int value){
        //如果数为空 则直接结束
        if (root==null){
            return;
        }

        //首先得到目标结点

        Node target = search(value);
        //如果没有找到  则直接结束
        if (target==null){
            return;
        }

        //如果二叉树只有根节点 说明待删除的结点就是根节点
        if (root.getLeft()==null && root.getRight()==null){
            root = null;
            return;
        }

        //得到父节点 开始删除

        Node parent = searchParent(value);

        if (target.getLeft()==null && target.getRight()==null){//需要删除得是叶子结点
            //进行判断需要删除得结点得父结点

            if (parent.getLeft()==target){
                parent.setLeft(null);
            }else {
                parent.setRight(null);
            }
        }else if (target.getLeft()!=null && target.getRight()!=null){//有两个结点得时候
            int min = GetMaxNode(target.getLeft());

            target.setData(min);


        }else {//删除单节点

            //如果删除得是左子树
            if (target.getLeft()!=null){
                if (parent!=null){
                    if (parent.getLeft()==target){
                        parent.setLeft(target.getLeft());
                    }else {
                        parent.setRight(target.getLeft());
                    }
                }else {
                    root = target.getLeft();
                }

            }else {//删除右子树

                if (parent!=null){
                    if (parent.getLeft()==target){
                        parent.setLeft(target.getRight());
                    }else {
                        parent.setRight(target.getRight());
                    }
                }else {
                    root = target.getRight();
                }
            }

        }




    }

    //得到当前子树得最小值

    private  int GetMaxNode(Node node){
        Node target =node;
        while (target.getRight()!=null){
            target = target.getRight();
        }

        deleteNode(target.getData());

        return target.getData();
    }

    //得到需要删除的结点
    private Node search(int value){
        if (root == null){
            return null;
        }
        return root.search(value);
    }

    //得到需要删除的父节点
    private Node searchParent(int value){
        if (root!=null){
            if (value==root.getData()){
                return null;
            }else {
                return root.searchParent(value);
            }
        }
        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
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

完整代码：

Node结点：

package binarysorttree;

/**
 * @ClassName: Node
 * @Author
 * @Date 2022/1/25
 */
public class Node {
    private int data;
    private Node left;
    private Node right;

    //构造方法
    public Node(int data) {
        this.data = data;
    }

    //添加结点的方法
    public void add(Node node) {
        if (node == null) {
            return;
        }

        if (node.getData() < this.getData()) {
            //如果小就往左边插入
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
            //大于等于向右添加
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

    }

    //查找要删除的结点
    public Node search(int value) {

        //如果要查找的值等于当前结点的值 则直接返回
        if (this.getData() == value) {
            return this;
        }

        //如果不是当前值，并且要查找的值小于当前结点的值 则往左边进行查找
        if (value < this.data) {
            //如果左结点不为空 则向左查找
            if (this.getLeft() != null) {
                return this.getLeft().search(value);
            } else {//为空则直接返回null 即没找到
                return null;
            }
        } else {//在右边查找
            //右子结点不为空 在右边查找
            if (this.getRight() != null) {
                return this.getRight().search(value);
            } else {
                return null;
            }
        }

    }

    //得到要删除结点的父节点
    public Node searchParent(int value) {
        //如果要删除的是根节点  逻辑在tree中处理即可
        //如果当前结点的子结点就是要删除的结点  则直接返回
        if ((this.left != null && this.left.data == value) || (this.right != null && this.right.data == value)) {
            return this;
        } else {
            //如果查找的值 小于当前结点的值 就向左边查找
            if (value < this.data && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.data && this.right != null) {//向右
                return this.right.searchParent(value);
            } else {
                return null;
            }
        }

    }

    //中序遍历

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right != null) {
            this.right.infixOrder();
        }
    }

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

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

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

BinarySortTree代码：

package binarysorttree;



/**
 * @ClassName: BinarySortTree
 * @Author
 * @Date 2022/1/25
 */
public class BinarySortTree {

    Node root = null;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }



    public void deleteNode(int value){
        //如果数为空 则直接结束
        if (root==null){
            return;
        }

        //首先得到目标结点

        Node target = search(value);
        //如果没有找到  则直接结束
        if (target==null){
            return;
        }

        //如果二叉树只有根节点 说明待删除的结点就是根节点
        if (root.getLeft()==null && root.getRight()==null){
            root = null;
            return;
        }

        //得到父节点 开始删除

        Node parent = searchParent(value);

        if (target.getLeft()==null && target.getRight()==null){//需要删除得是叶子结点
            //进行判断需要删除得结点得父结点

            if (parent.getLeft()==target){
                parent.setLeft(null);
            }else {
                parent.setRight(null);
            }
        }else if (target.getLeft()!=null && target.getRight()!=null){//有两个结点得时候
            int min = GetMaxNode(target.getLeft());

            target.setData(min);


        }else {//删除单节点

            //如果删除得是左子树
            if (target.getLeft()!=null){
                if (parent!=null){
                    if (parent.getLeft()==target){
                        parent.setLeft(target.getLeft());
                    }else {
                        parent.setRight(target.getLeft());
                    }
                }else {
                    root = target.getLeft();
                }

            }else {//删除右子树

                if (parent!=null){
                    if (parent.getLeft()==target){
                        parent.setLeft(target.getRight());
                    }else {
                        parent.setRight(target.getRight());
                    }
                }else {
                    root = target.getRight();
                }
            }

        }




    }

    //得到当前子树得最小值

    private  int GetMaxNode(Node node){
        Node target =node;
        while (target.getRight()!=null){
            target = target.getRight();
        }

        deleteNode(target.getData());

        return target.getData();
    }

    //得到需要删除的结点
    private Node search(int value){
        if (root == null){
            return null;
        }
        return root.search(value);
    }

    //得到需要删除的父节点
    private Node searchParent(int value){
        if (root!=null){
            if (value==root.getData()){
                return null;
            }else {
                return root.searchParent(value);
            }
        }
        return null;
    }




    public void infixOrder(){
       if (root!=null){
           root.infixOrder();
       }else {
           System.out.println("树为空，无法遍历");
       }
    }




}

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

测试代码：

package binarysorttree;

/**
 * @ClassName: Test
 * @Author
 * @Date 2022/1/25
 */
public class Test {
    public static void main(String[] args) {
        BinarySortTree bs = new BinarySortTree();

        int[] arr =  {7,7,3,10,12,5,1,9};

        for (int i : arr){
            bs.add(new Node(i));
        }

        System.out.println("插入后");
        bs.infixOrder();

        bs.deleteNode(7);
        bs.deleteNode(3);
        bs.deleteNode(10);
        bs.deleteNode(12);
        bs.deleteNode(5);
        bs.deleteNode(1);
        bs.deleteNode(9);
        bs.deleteNode(9);
        System.out.println("-----------------");

        System.out.println("删除后");

        bs.infixOrder();


    }
}

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

结果：
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/572325

BST（二叉搜索树）原理解析及代码实现_要解析数据才行,拿bst当例子 就是得完整看到bst的波形