二叉搜索树

什么是二叉搜索树

二叉搜索树简称为BST,又称二叉排序树,二叉查找树

二叉搜索树规定:左孩子的值小于根节点的值,右孩子的值大于等于根节点的值

建树

本文采取结构体建树,使用先序遍历建树

思路:

令先序序列为front

list序列的第一项为当前树的根节点,记第一项为root,用双指针的方法对后面的序列进行查找,指针定义为left和right,让left从第二项开始自左向右进行查找,right从最后一项开始自右向左开始查找,我们需要找到:

  1. list[left] >= list[root]
  2. list[right] < list[root]

如果此时right + 1 != left则说明无法构成二叉搜索树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int M = 1e6 + 7;
int front[M];
int n;  //有n个节点
struct Tree {
    int l = -1, r = -1, val;
} tree[M];
int build(int l, int r) {
    if (l >= n || r < 0 || l > r) {
        return -1;
    }
    int root = front[l++];  //从第二项开始
    int left = l, right = r;
    while (left <= r && front[left] < root) {
        left++;
    }
    while (right >= l && front[right] >= root) {
        right--;
    }
    tree[l - 1] = {build(l, right), build(left, r), front[l - 1]};
    return l - 1;  //返回第一项位置
}