# 2.2 二叉搜索树

2.2.1 二叉搜索树的查找
2.2.2 二叉搜索树的插入

二叉搜索树也是二叉树，拥有二叉树的特性。

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值
每个节点中的值必须小于（或等于）存储在其右子树中的任何值

左小右大

分而治之的思想

1 2 3 4 5 6 7

注意：对于任何一个二叉搜索树，采用中序遍历的方式，一定可以得到一个递增的序列。

# 2.2.1 二叉搜索树的查找 (opens new window)

var searchBST = function(root, val) {
    if (val < root.val) {
        return root.left ? searchBST(root.left, val) : null;
    }
    if (val > root.val) {
        return root.right ? searchBST(root.right, val) : null;
    }
    if (root.val === val) {
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11

# 2.2.2 二叉搜索树的插入 (opens new window)

var insertIntoBST = function(tree, val) {
    searchBST(tree, val);
    return tree;
    function searchBST(root, val) {        
        if (val < root.val) {
            if (root.left) {
                searchBST(root.left, val)
            } else {
                root.left = new TreeNode(val);
            }
        }
        if (val > root.val) {
            if (root.right) {
                searchBST(root.right, val)
            } else {
                root.right = new TreeNode(val);
            }
        }
        if (root.val === val) {
            root.left = new TreeNode(val);
        }
    };
};

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

← 2.1 二叉树 2.3 Trie 树 →