二叉搜索树BST总结_bst中序遍历的作用是什么

1. 概念

二叉搜索树又称二叉排序树，一颗BST应该满足以下特点：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；

上图就是一颗二叉搜索树，对它进行中序遍历后得到的结果是[1,2,3,4,5,6,7,8,9]，我们不难发现它是一个递增的序列，注意这是二叉搜索树的一个重要性质：BST中序遍历的结果呈增序排列。
在很多涉及BST的问题中都要先考虑以下这个性质。

2. 基本操作

2.1 查找

利用BST中序遍历是递增序列这一性质，定义一个遍历指针cur，用来遍历并返回查找到的节点。根节点值与给定值key作比较，若根节点值小于key，那么根节点的右子树一定是大于key的值，此时递归右子树；若根节点值大于key，那么根节点的左子树一定是小于key的值，此时递归左子树。

public Node search(Node root,int key) {
   
        Node cur = root;
        while (cur != null) {
   
            if (cur.val == key) {
   
                return cur;
            } else if (cur.val < key) {
   
                cur = cur.left;
            } else {
   
                cur = cur.right;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2 插入

如果树为空树，即根 == null，直接插入；

如果树不是空树，按照查找逻辑确定插入位置，插入新结点；