目录

二叉排序树

基本介绍

先看一个需求,给你一个数列{7,3,10,12,5,1,9},要求高效地完成对数据的查询和添加。

解决方案分析:

  1. 使用数组 无序数组 优点:直接在数组尾添加,速度快。 缺点:查找速度慢. 有序数组 优点:可以使用二分查找,查找速度快,缺点:为了保证数组有序,在添加新数据时,找到插入位 置后,后面的数据需整体移动,速度慢。
  2. 链表 不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。

此时可以考虑使用二叉排序树

二叉排序树:BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点(不推荐有相同的值)

二叉排序树的创建和遍历

一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树,比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ,创建成对应的二叉排序树为 https://gitee.com/lienhui68/picStore/raw/master/null/20200629013734.png

二叉排序树的删除

二叉排序树的删除分3种情况考虑:

  1. 删除叶子节点 1.1. 如果是父节点的左子节点,parent.left=null; 1.2. 如果是父节点的右子节点,parent.right=null;
  2. 删除只有一颗子树的节点 将删除节点的子节点挂在父节点上,分4种情况, 根节点单独处理 2.1 删除节点是父节点的左子节点 && 删除节点的子节点为左子节点, parent.left = cur.left; 2.2 删除节点是父节点的左子节点 && 删除节点的子节点为右子节点, parent.left = cur.right; 2.3 删除节点是父节点的右子节点 && 删除节点的子节点为左子节点, parent.right = cur.left; 2.4 删除节点是父节点的右子节点 && 删除节点的子节点为右子节点, parent.left = cur.right;
  3. 删除有两棵子树的节点 找到要删除的值所在节点,记为cur, 找到cur左子树的最大值节点删除,cur置置为刚才删除的节点值; 或者找到cur右子树的最小值节点删除,cur值置置为刚才删除的节点值

代码实现

  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
package com.eh.ftd.dsa.ds;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/29 01:53
 */
public class BinarySortTree {
    /**
     * 定义节点
     */
    class Node {
        int value;
        Node left;
        Node right;

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

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

    /**
     * 二叉树根节点
     */
    Node root;

    /**
     * 添加节点
     *
     * @param value
     */
    public void add(int value) {
        Node node = new Node(value);
        if (root == null) {
            root = node;
            return;
        }
        Node cur = root;
        while (true) {
            // 如果值比当前节点小
            if (value < cur.value) {
                // 如果当前节点左节点为空,将左节点指向新节点
                if (cur.left == null) {
                    cur.left = node;
                    return;
                } else { // 继续跟当前节点的左节点比较
                    cur = cur.left;
                }
            }
            if (value > cur.value) {
                if (cur.right == null) {
                    cur.right = node;
                    return;
                } else {
                    cur = cur.right;
                }
            }
        }

    }

    public void inOrderList(Node node) {
        if (node != null) {
            inOrderList(node.left);
            System.out.print(node + " ");
            inOrderList(node.right);
        }
    }

    /**
     * 查找一个节点
     *
     * @param value
     * @return
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        Node cur = root;
        while (cur != null) {
            if (value == cur.value) {
                return cur;
            } else if (value < cur.value) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }

    /**
     * 删除一个节点
     *
     * @param value
     * @return true-删除成功,false-不存在
     */
    public boolean delete(int value) {
        if (root == null) {
            return false;
        }
        // 1. 找到目标节点(并且保存父节点的引用,用于删除)
        Node parent = null, cur = root;
        while (cur != null && value != cur.value) {
            parent = cur;
            if (value < cur.value) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        // 没找到直接返回
        if (cur == null) {
            return false;
        }
        // 父节点为空表示找到的节点就是根节点,也要分3种情况考虑
        if (parent == null) {
            // 1. 如果父节点是叶子节点
            if (cur.left == null && cur.right == null) {
                root = null;
            } else if (cur.left == null && cur.right != null) { // 2.1 如果只有1颗是右子树
                root = cur.right;
            } else if (cur.right == null && cur.left != null) { // 2.2 如果只有1颗是左子树
                root = cur.left;
            } else {
                // 3. 有两棵子树情况
                deleteLeftMaxNode(cur);
            }
            return true;

        }
        // 有父节点有子节点, 分三种情况处理
        // 1. cur是叶子节点
        if (cur.left == null && cur.right == null) {
            // 判断cur是父节点的左子节点还是右子节点
            if (cur.value == parent.left.value) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            return true;
        }
        // 2. cur是只有一颗子树的节点
        // 2.1 只有右子树
        if (cur.left == null && cur.right != null) {
            // 2.1.1 是父节点的左子节点
            if (cur.value == parent.left.value) {
                parent.left = cur.right;
            } else {
                // 2.1.2 是父节点的右子节点
                parent.right = cur.right;
            }
            return true;
        }
        // 2.2 只有左子树
        if (cur.left != null && cur.right == null) {
            // 2.2.1 是父节点的右子节点
            if (cur.value == parent.right.value) {
                parent.right = cur.left;
            } else {
                // 2.2.2 是父节点的左子节点
                parent.left = cur.left;
            }
            return true;
        }
        // 3. 只剩下有两颗子树的情况
        // 找到要删除的值所在节点,记为cur, 找到cur左子树的最大值节点删除,cur置置为刚才删除的节点值;
        // 或者找到cur右子树的最小值节点删除,cur值置置为刚才删除的节点值,这里我们找左节点最大值节点
        deleteLeftMaxNode(cur);
        return true;
    }

    private int deleteLeftMaxNode(Node cur) {
        Node leftMaxNode = cur.left;
        while (leftMaxNode.right != null) {
            leftMaxNode = leftMaxNode.right;
        }
        int leftMaxValue = leftMaxNode.value;
        // 删除该节点
        delete(leftMaxValue);
        // 将cur的值置为leftMaxValue
        cur.value = leftMaxValue;
        return leftMaxValue;
    }

    public static void main(String[] args) {
        BinarySortTree binarySortTree = new BinarySortTree();
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        for (int i : arr) {
            binarySortTree.add(i);
        }
//        binarySortTree.inOrderList(binarySortTree.root);
//        Node node = binarySortTree.search(15);
//        System.out.println(node);
//        node = binarySortTree.search(10);
//        System.out.println(node);
        for (int i = 0; i < 14; i++) {
            System.out.print("删除节点:" + i + ", ");
            boolean res = binarySortTree.delete(i);
            if (!res) {
                System.out.println("不存在该节点!");
            } else {
                System.out.print("成功删除,剩余节点: ");
                binarySortTree.inOrderList(binarySortTree.root);
                System.out.println();
            }
        }
    }


}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200629031518.png