数据结构：二叉搜索树(图文并茂哦~)_二叉排序树查找代码

每日一言

记忆是一张很小的渔网，只能网住很少的鱼，并且漏走所有的水。

---

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

从上述概念以及图中可以看出，二叉搜索树具有以下特性：

1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧节点一定是树中最大的节点
2. 采用中序遍历遍历二叉搜索树，可以得到一个有序的序列

二叉搜索树的结构代码

    public static class TreeNode {
    
    	// 定义节点的三个属性
    	int val; // 节点的值
    	TreeNode left; // 子节点的引用，指向左子树
    	TreeNode right; // 子节点的引用，指向右子树

		// 构造函数，用于创建一个具有指定值的节点
        public TreeNode(int val) {
            this.val = val;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.二叉搜索树的查找

既然将其称之为二叉搜索树，因此这棵树最主要的作用是进行查询，而且其查询原理特别简单，具体如下:
假如要查找一个值val，

1. 首先从根节点开始查找，如果根节点为空，返回null
2. 如果根节点不为空，则将val与根节点的值进行比较，此时会分为3种情况
   a. 根节点的值 等于 val ，返回当前引用。
   b. 根节点的值 大于 val，由于根节点右边的值都比根节点的值大，所以我们去根节点的左子树进行查找。
   c. 根节点的值 小于 val，由于根节点左边的值都比根节点的值小，所以我们去根节点的右子树进行查找。

举个例子：在以下二分搜索树中寻找 43 元素

1. 根节点的42元素小于43元素，向右查找
   
2. 当前节点的59元素大于43元素，向左查找
   
3. 当前节点的51元素大于41元素，向左查找
   
4. 当前节点的43元素等于43元素，找到了！

二叉搜索树的查找代码

    //查找
    public TreeNode search(int key) {
    	// 初始化一个指针cur，指向根节点root
        TreeNode cur = root;
        // 开始一个while循环，只要cur不为null，就继续查找
        while (cur != null) {
        	// 如果cur节点的值小于key，说明key应该在cur的右子树中
            if (cur.val < key) {
            	// 将cur更新为其右子节点，继续在右子树中查找
                cur = cur.right;
            // 如果cur节点的值大于key，说明key应该在cur的左子树中
            } else if (cur.val > key) {
            	// 将cur更新为其左子节点，继续在左子树中查找
                cur = cur.left;
            // 如果cur节点的值等于key，说明找到了匹配的节点
            } else {
            	// 直接返回当前节点
                return cur;
            }
        }
        //没找到，返回null
        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

3.二叉搜索树的插入

关于二叉搜索树的插入，我们首先要知道：

1. 新插入的节点一定在叶子节点上。
2. 二叉搜索树中不能插入重复的元素

原因：

1. 新插入的节点最终会位于叶子节点上。这是因为插入操作会从根节点开始，沿着树向下寻找合适的位置来放置新节点。新节点会与路径上的每个节点进行比较，直到找到一个空的位置（即叶子节点），然后将新节点插入到这个位置。
2. 如果允许插入重复的元素，那么这些重复的元素既可以放在左子树也可以放在右子树，这会破坏二叉搜索树的性质，导致树的结构混乱，从而影响搜索、插入和删除等操作的效率。

二叉搜索树插入新节点的一般步骤：

1. 从根节点开始，比较新节点的值与当前节点的值。
2. 如果新节点的值小于当前节点的值，则移动到当前节点的左子节点；如果新节点的值大于当前节点的值，则移动到当前节点的右子节点。
3. 重复步骤2，直到找到一个空的位置（即叶子节点）。
4. 将新节点插入到这个空位置。

举个例子：向如下二分搜索树中插入元素 61

1. 需要插入的元素 61 比 42 大，比较 42 的右子树根节点。
   
2. 61 比 59 大，所以需要把 61 移动到 59 右子树相应位置，而此时为空，直接插入作为 59 的右子节点。
   

二叉搜索树的插入代码

    // 插入操作，将给定值插入到二叉搜索树中
    public void insert(int val) {
    	// 创建一个新节点
        TreeNode node = new TreeNode(val);
        // 如果根节点为空，则将新节点作为根节点
        if (root == null) {
            root = node;
            return;
        }
        
        // 定义当前节点为根节点，父节点初始化为空
        TreeNode cur = root;
        TreeNode parent = null;

		// 在二叉搜索树中查找插入位置
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
            	// 如果当前节点值小于插入值，则向右子树移动
                cur = cur.right;
            } else if (cur.val > val) {
				 // 如果当前节点值大于插入值，则向左子树移动
                cur = cur.left;
            } else {
                //在二叉搜索树中相同的值不能重新插入
                return;
            }
        }
		
		// 将新节点插入到找到的位置
        if (parent.val < val) {
        	// 如果父节点值小于插入值，则将新节点作为右子节点
            parent.right = node;
        } else {
        	// 如果父节点值大于插入值，则将新节点作为左子节点
            parent.left = 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

4.二叉搜索树的删除

对于二叉搜索树的删除，相对来说就比较麻烦了。因为要考虑以下三种情况：
1.要删除的是叶子结点
2.要删除的结点只有一个孩子结点
3.要删除的结点有左、右两棵子树

一. 删除只有左孩子的节点，如下图节点 58。

删除掉元素 58，让左子树直接代替 58 的位置，整个二分搜索树的性质不变。

二. 删除只有右孩子的节点，如下图节点 58。

删除掉元素 58，让右子树直接代替 58 的位置，整个二分搜索树的性质不变。

三.删除左右都有孩子的节点，如下图节点 58。

a.找到右子树中的最小值，为节点 59（替罪羊）

b.节点 59 代替待删除节点 58，并删除掉节点59

小小的总结一下：

根据该节点的子节点情况，分三种情况进行删除：

1. 如果要删除的节点没有左子节点，则将该节点的右子节点替换该节点。
2. 如果要删除的节点没有右子节点，则将该节点的左子节点替换该节点。
3. 如果要删除的节点既有左子节点又有右子节点，则找到该节点右子树中最小的节点（替罪羊），将该节点的值替换为要删除的节点的值，然后删除该节点。

二叉搜索树的删除代码

// 删除给定值的节点
public boolean remove(int key) {
    TreeNode cur = root; // 从根节点开始查找
    TreeNode parent = null; // 记录当前节点的父节点

    while (cur != null) { // 循环直到找到节点或者遍历完整棵树
        if (cur.val > key) { // 如果当前节点值大于要删除的值
            parent = cur; // 记录当前节点为父节点
            cur = cur.left; // 向左子树移动
        } else if (cur.val < key) { // 如果当前节点值小于要删除的值
            parent = cur; // 记录当前节点为父节点
            cur = cur.right; // 向右子树移动
        } else { // 如果当前节点值等于要删除的值
            // 找到了要删除的节点，开始删除
            removeNode(cur, parent);
            return true; // 返回删除成功
        }
    }
    return false; // 没有找到要删除的值，返回删除失败
}

// 删除节点的具体操作
public void removeNode(TreeNode cur, TreeNode parent) {
    if(cur.left == null) { // 如果要删除的节点没有左子树
        if(cur == root) { // 如果要删除的节点是根节点
            root = cur.right; // 将根节点指向其右子节点
        } else if (cur == parent.right) { // 如果要删除的节点是父节点的右子节点
            parent.right = cur.right; // 将父节点的右子节点指向要删除节点的右子节点
        } else { // 如果要删除的节点是父节点的左子节点
            parent.left = cur.right; // 将父节点的左子节点指向要删除节点的右子节点
        }
    } else if (cur.right == null){ // 如果要删除的节点没有右子树
        if(cur == root) { // 如果要删除的节点是根节点
            root = cur.left; // 将根节点指向其左子节点
        } else if (cur == parent.left) { // 如果要删除的节点是父节点的左子节点
            parent.left = cur.left; // 将父节点的左子节点指向要删除节点的左子节点
        } else { // 如果要删除的节点是父节点的右子节点
            parent.right = cur.left; // 将父节点的右子节点指向要删除节点的左子节点
        }
    } else { // 如果要删除的节点既有左子树又有右子树
        // 找到要删除节点的右子树中的最小节点，即右子树中的最左节点
        TreeNode remove = cur.right;
        TreeNode prev = cur;
        while (remove.left != null) { // 循环找到最左节点
            prev = remove; // 记录当前节点为前一个节点
            remove = remove.left; // 向左移动
        }
        cur.val = remove.val; // 将当前节点的值替换为最小节点的值
        if(cur == prev) { // 如果要删除的节点的右子树只有一个节点
            cur.right = remove.right; // 将当前节点的右子树指向最小节点的右子树
        } else { // 如果要删除的节点的右子树有多个节点
            prev.left = remove.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

5.二叉搜索树的查询性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为:$lo{g}_2(N)$
最差情况下，二叉搜索树退化为单支树，其平均比较次数为:
$N/2$

6. 全部代码

public class BinarySearchTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    //插入
    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                //在二叉搜索树中相同的值不能重新插入
                return;
            }
        }

        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

    }

    //查找
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }


    //删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur != null) {
            if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                //找到了，开始删除
                removeNode(cur, parent);
                return true;
            }
        }
        return false;
    }

    public void removeNode(TreeNode cur, TreeNode parent) {

        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            } else if (cur == parent.right) {
                parent.right = cur.right;
            } else {
                parent.left = cur.right;
            }
        } else if (cur.right == null){
            if(cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            //都不为空
            TreeNode remove = cur.right;
            TreeNode prev = cur;
            while (remove.left != null) {
                prev = remove;
                remove = remove.left;
            }
            cur.val = remove.val;
            if(cur == prev) {
                cur.right = remove.right;
            } else {
                prev.left = remove.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

---

结语

请给自己些耐心，不要急于求成。
山外青山楼外楼，莫把百尺当尽头。
保持空杯心态加油努力吧！

---

都看到这里啦！真棒(*^▽^*)

可以给作者一个免费的赞赞吗，这将会鼓励我继续创作，谢谢大家

如有纰漏或错误，欢迎指正

---