树与二叉树

· · 个人记录

树

  1. 定义：由 n(n \ge 30) 个节点的有限级。（n=0 时成为空树）

  2. 结点的度：子节点的度

  3. 结点关系：

    A 是 BC 的父结点

    BC 是 A 的子结点

    DEF 是兄弟结点

  4. 结点层次：

  5. 树的深度：结点的最大层次数

  6. 树的宽度：每一层结点个数最大值

二叉树

特点

  1. 每个结点最多 2 个子结点，所以二叉树中结点的度 \le 2
  2. 每个结点最多 2 个子结点，称为左儿子和右儿子，他们有顺序的，且顺序不能任意颠倒
  3. 二叉树第 i 层最多 2^{i-1} 个结点
  4. 深度为 i 的二叉树最多 2^i - 1 个结点

满二叉树

  1. 所有分支节点都有两个子结点
  2. 所有叶结点都在同一层上
  3. 结点 i 的左儿子 i 右儿子 i+1
  4. 结点 i 的父结点 \left\lfloor \dfrac{i}{2} \right\rfloor

重复二叉树

所有结点位置与满二叉树相同

二叉树的存储

struct node {
    int left, right, father;
} dot[1005];

或

left[1005], right[1005], father[1005];

二叉树的遍历

结构体：

void dfs(int id, int depth) {
    dfs(dot[i].left, depth + 1);
    dfs(dot[i].right, depth + 1);
}

二维数组：

void dfs(int id, int fa)
  1. 遍历：从根结点出发，按照某种次序访问二叉树中的所有结点，每个结点，有且仅有一次访问
  2. 次序：前序遍历，中序遍历，后序遍历 （dfs）层次遍历（bfs）

前序遍历

  1. dfs 时，第 1 次搜到某个结点就输出

  2. 根左右：先搜根 -> 左儿子 -> 右儿子

  3. 输出

    dfs：

    1. 输出 root ........... 根
    2. dfs（左子树）.... 左
    3. dfs（右子树）.... 右

中序遍历

  1. dfs 时，第 2 次搜到某个结点就输出

  2. 左根右：先搜左儿子 -> 根 -> 右儿子

  3. 输出

    dfs：

    1. dfs（左子树）.... 左

  4. 输出 root ........... 根

    1. dfs（右子树）.... 右

后序遍历

  1. dfs 时，第 3 次搜到某个结点就输出

  2. 左右根：先搜左儿子 -> 右儿子 -> 根

  3. 输出

    dfs：

    1. dfs（左子树）.... 左

    2. dfs（右子树）.... 右

    3. 输出 root ........... 根

层次遍历

bfs 进行遍历

前中定后，中后定前，前后定中

前：ABCDEF 中：CBAEDF 后：CBEFDA

例题

[LuoguP1087][NOIP2004 普及组] FBI 树

Link

Solution

看样例：

欲求后序遍历，模板题，套模板即可。

Code
// Problem: P1087 [NOIP2004 普及组] FBI 树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1087
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#define ll long long
using namespace std;
int n;
string s;

void maketree(int x, int y) {
    if (y > x) {
        maketree(x, (x + y) / 2); //左
        maketree((x + y) / 2 + 1, y); //右
    }
    bool B = true, I = true;
    for (int i = x; i <= y; i++) {
        if (s[i] == '1') B = false;
        else if (s[i] == '0') I = false;
    }
    if (B == true) cout << "B";
    else if (I == true) cout << "I";
    else cout << "F";
}
int main() {
    cin >> n >> s;
    maketree(0, s.size() - 1);
    puts("");
    return 0;
}

二叉排序树（Binary Sort Tree）

也称二叉查找树

特点

  1. 若左子树不空，则左子树上所有结点的值 \leq root
  2. 若右子树不空，则右子树上所有结点的值 \geq root
  3. 左右子树也都是二叉排序树

建立二叉排序树

void insert(int x, int s) {
    if (s < x) {
         if (dot[x].left) insert(dot[x].left, s);
        else dot[x].left = s;
    }
    else if (s > x) {
         if (dot[x].right) insert(dot[x].right, s);
         else dot[x].right = s;
    }
}
for (int i = 2; i <= n; i++)
    insert(a[1], a[i]); //将数字 a[i] 插入结点 a[1] 下方