树的基本概念

树是一种数据结构。

树的定义：一棵树使用 $n(n>0)$ 个结点组成的有限集合，其中：

1. 每一个元素被称为结点
2. 有一个根节点或者说是树根
3. 除根结点外，其余节点能被分成 $m$ 个互不相交的有限集合 $T_0,T_1\dots T_{m-1}$。每一个子集也是一棵树，被称为子树。

树的表示方法

父亲表示法

struct node {
    int data, parent;
}

孩子表示法

struct node {
    // m 表示树的度
    int data, children[m];
}

父亲孩子表示法

struct node {
    // m 表示树的度
    int data, parent, children[m];
}

二叉树

二叉树(BT)是一种特殊的树。二叉树的度最大为 $2$。如果一个结点有两个孩子，则分别称为左孩子和有孩子。

二叉树的性质：

1. 在二叉树的第 $i$ 层上至多有 $2^{i-1}$个结点（$i\ge 1$）。
2. 深度为 $k$ 的二叉树至多有 $2^k-1$个结点（$k\ge 1$）。
3. 对于任何一颗二叉树 $T$，如果其终端结点数为 $n_0$，度为 $2$ 的结点数为 $n_2$，则 $n_0=n_2+1$。
4. 具有 $n$ 个节点的完全二叉树深为 $[log{2}^n]+1$（$[log{2}^n]$ 下取整）。
5. 如果对一颗有 $n$ 个结点的完全二叉树（其深度为 $[log{2}^n]+1$）的结点按层序编号（从第一层到 $[log{2}^n]+1$ 层，每层从左到右），对任一结点 $i$（$1\le i\le n$）:
   1. 如果 $i=1$，则结点 $i$ 是二叉树的根，无双亲，如果 $i>1$,则其双亲结点是结点 $[i/2]$
   2. 如果 $2i>n$，则结点 $i$ 无左孩子（结点 $i$ 为叶子结点）否则左孩子是结点 $2i$。
   3. 如果 $2i+1>n$,则结点 $i$ 无右孩子，否则其右孩子是结点 $2i+1$.

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 $k(k\ge 1)$，且结 点总数是 $2^k-1$，则它就是满二叉树。

• 完全二叉树:设二叉树的深度为 $h$，除第 $h$ 层外，其它各层 $(1～h-1)$ 的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边。

建立二叉树

孩子表示法

struct node {
    int data, left, right;
} bt[N];

注意：满二叉树和完全二叉树我们一般直接使用数组表示，根据其性质可以直接找到所需结点。

二叉树的遍历

1. 先序遍历：根左右

   void preorder(int root) {
       if(root) {
           cout << node[root].data << endl;
           preorder(node[root].left);
           preorder(node[root].right);
       }
   }

2. 中序遍历：左根右

   void midorder(int root) {
       if(root) {
           midorder(node[root].left);
           cout << node[root].data << endl;
           midorder(node[root].right);
       }
   }

3. 后序遍历：左右根

   void postorder(int root) {
       if(root) {
           postorder(node[root].left);
           postorder(node[root].right);
           cout << node[root].data << endl;
       }
   }

4. 层序遍历：一层一层的遍历

   void bfs(int root) {
       int h = 0, t = 1, q[h] == root;
       while(h != t) {
           int n = q[h++];
           cout << n << endl;
           if(node[u].left) {
               q[t] = node[u].left;
               t++;
           }
           if(node[u].right) {
               q[t] = node[u].right;
               t++;
           }
       }
   }

例题：小球坠落

#include <iostream>
#include <cmath>
using namespace std;

const int N = 1100000;

int fbt[N][2], n, m;

int main() {
    cin >> n >> m;

    for(int i = 1; i <= pow(2, n) - 1; i++) {
        fbt[i][0] = i;
        fbt[i][1] = false;
    }

    int i;
    for(int k = 0; k < m; k++) {
        for(i = 1; i <= pow(2, n) - 1; ) {
            if(!fbt[i][1]) {
                fbt[i][1] = true;
                i = 2 * i;
            } else {
                fbt[i][1] = false;
                i = 2 * i + 1;
            }
        }
    }

    cout << i / 2 << endl;


    return 0;
}

例题：FBI 树

表达式求值