二叉树

什么是二叉树

每个节点最多有两个子树的树形结构

二叉树的四种遍历

  1. 层序遍历:从上到下,从左往右
  2. 先序遍历:根左右
  3. 中序遍历:左根右
  4. 后序遍历:左右根

层序遍历采取bfs(广度优先搜索)进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct tree {
    int val;
    tree *r, *l;
    tree() {
        r = NULL;
        l = NULL;
    }
};
void bfs(tree* root) {
    queue<tree*> q;
    q.push(root);
    while (!q.empty()) {
        root = q.front();
        q.pop();
        if (root == NULL) {
            continue;
        }
        cout << root->val;  //输出当前节点
        q.push(root->l);
        q.push(root->r);
    }
}

先,中,后序遍历采取dfs(深度优先搜索)进行遍历

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
//先中后序遍历
struct tree {
    int val;
    tree *r, *l;
    tree(){
        l = NULL;
        r = NULL;
    }
};
void dfs(tree* root) {
    if (root == NULL) {
        return;
    }
    // cout << root->val;
    // 先序遍历(先输出'根',然后再进行'左'和'右')
    // 根左右
    dfs(root->l);
    // cout << root->val;
    // 中序遍历(在'左'进行完之后输出'根')
    // 左根右
    dfs(root->r);
    // cout << root->val;
    // 后序遍历(在'左'和'右'都进行完之后输出'根')
    // 左右根
}

我们不难发现只要在递归中改变输出位置即可实现

建树

如果要进行建树,必须要有中序遍历,再加上先序或者后序遍历其一即可,如果没有中序遍历则建成的树可能不止一颗

这里只以用先序和中序来建树为例,节点数量为n

思路

按照先序的顺序不断从找当前点在中序当中的位置

令先序当前点在中序中找到的位置为now,当前区间为[l, r]

那么左节点就是2 * idx,区间为[l, now - 1]

右节点就是2 * idx + 1,区间为[now + 1, r]

数组建树(有局限)

**局限:**在极其特殊的情况下会出现越界,比如所有节点均只有左子树/右子树,下标访问超过了1e7

思路:根节点为1,令当前节点为idx,往左孩子走就是idx * 2,往右孩子走就是idx * 2 + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int M = 1e6 + 7;
int front[M], mid[M], point = 0;  //先序遍历,中序遍历,point指向当前要找的位置
int n;                            //有n个节点
int tree[M];
void build(int idx, int l, int r) {
    if (point == n || l > r || l < 0 || r >= n) {  //越界停止
        return;
    }
    tree[idx] = front[point++];
    int now = l;
    while (tree[idx] != mid[now] && now <= r) {
        now++;
    }
    build(idx * 2, l, now - 1);
    build(idx * 2 + 1, now + 1, r);
}

结构体建树(有局限)

局限:所有元素均不能超过1e7

思路:考虑到节点元素不会重复,所以我们可以直接存值(题目一般不会出重复点刁难你,出重复点一般在二叉搜索树中,会在后面讲)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int front[M], mid[M], point = -1;  //先序遍历,中序遍历,point指向当前要找的位置
int n;                             //有n个节点
struct Tree {
    int l = -1, r = -1;
} tree[M];
int build(int l, int r) {
    if (point == n - 1 || l > r || l < 0 || r >= n) {  //越界停止
        return 0;
    }
    point++;
    int now = l;
    while (front[point] != mid[now] && now <= r) {
        now++;
    }
    tree[mid[now]] = {build(l, now - 1), build(now + 1, r)};
    return mid[now];
}

指针建树(专业呀~)

**局限:**如此专业怎么会有局限?

**思路:**如果节点root有子节点则new一个节点,将root的子节点与这个新节点相连,与结构体建树有异曲同工之处

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
const int M = 1e6 + 7;
int front[M], mid[M], point = -1;  //先序遍历,中序遍历,point指向当前要找的位置
int n;                             //有n个节点
struct Tree {
    int val;
    Tree *l, *r;
    Tree(int val) {
        this->val = val;
        l = NULL;
        r = NULL;
    }  //构造函数,每次new一个新节点的时候对新节点进行初始化.
};
Tree* build(int l, int r) {
    if (point == n - 1 || l > r || l < 0 || r >= n) {  //越界停止
        return NULL;
    }
    point++;
    int now = l;
    while (front[point] != mid[now] && now <= r) {
        now++;
    }
    Tree* root = new Tree(front[point]);
    root->l = build(l, now + 1);
    root->r = build(now + 1, r);
    return root;
}