树

由n (n>=0) 个有限节点组成一个具有层次关系的集合。根朝上，叶朝下

特点：

  1. 每个节点有零个或多个子节点

  2. 没有父节点的节点成为根节点

  3. 每一个非根节点有且仅有一个父节点；除了叶子节点外，每个子节点可以分为多个不相交的子树

二叉树

每一个节点最多含有两个子树

满二叉树： 除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树

完全二叉树： 除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点

注意到：

  1. 左儿子编号 = 父亲编号 * 2 ；

    右儿子编号 = 父亲编号 * 2 + 1；

  2. 父亲编号 = [儿子编号 / 2] (取整）

树的遍历

—— 二叉树的先序遍历、中序遍历、后序遍历和层序遍历

alt

先序遍历（根-左-右）： 先访问根，然后遍历左子树，最后遍历右子树；遍历左、右子树时仍然先访问根节点，然后遍历左子树，右子树。如果二叉树为空则返回。

顺序：1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

中序遍历（左-根-右）： 首先遍历左子树，然后访问根节点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根节点，最后遍历右子树。

后序遍历（左-右-根）： 首先遍历左子树，然后遍历右子树，最后访问根节点，在遍历左、右子树时，仍然先便利左子树，然后遍历右子树，最后遍历根节点。

层序遍历： 按二叉树每一层的顺序来遍历，即先访问根，然后访问第一层，接着访问第二层。

例： alt

先序：ABDGHCEIFJ

中序(特点：整体上从左往右）：GDHBAIECJF

后序：GHDBIEJFCA

层序：ABCDEFGHIJ

例1：给出二叉树的前序和中序求后序

eg：前序：ABCDFE 中序：BADFCE

思路：

前序遍历的第一个是整个树的根，即A

则在中序遍历中A左边是左子树，A右边是右子树

在中序中看，C是右子树的下一个根

得：后序：BFDECA

注意：给出前序和后序无法得出中序（问题：不知道左子树和右子树的分割点）

例：[NOIP2001]求先序序列

#include<bits/stdc++.h>
using namespace std;
string zhong, hou;
void deal(int l1, int r1, int l2, int r2)
{
    if (l1 > r1) return ;
    cout << hou[r2];
    int pos = -1;
    for (int i = l1; i <= r1; i++)
    {
        if (zhong[i] == hou[r2]) pos = i;
    }
    
    deal(l1, pos-1, l2, l2 + (pos-1-l1));
    deal(pos+1, r1, l2 + (pos-1-l1)+1, r2-1);
}

int main()
{
    cin >> zhong >> hou;
    int l = zhong.length();
    deal(0, l-1,0,l-1);
    return 0;
}