【图论】树的基本概念、存储与遍历

更新于 2023-04-07 分类于 ACM ，图论阅读次数：本文字数： 3.8k 阅读时长 ≈ 3 分钟

树的基本概念、存储与遍历相关内容

基本概念

树：特殊的图

无根树

无根树等价定义：

$n$ 个节点， $n-1$ 条边的连通无向图
无向无环的连通图
任意两个结点之间有且仅有一条简单路径的无向图
任何边均为桥的连通图
没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图

有根树

有根树：无根树指定一个根节点

父节点（父亲）（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。根结点没有父结点。
祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。
子结点（孩子）（child node）：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子结点。子结点的顺序一般不加以区分（例外：二叉树）
兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
后代（descendant）：子节点及其后代
子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

特殊的树

链（chain/path graph）：满足与任一结点相连的边不超过 $2$ 条的树称为链。
菊花/星星（star）：所有节点都与某一个节点相连（除自身）
二叉树
- 有根二叉树（rooted binary tree）：每个结点最多只有两个孩子的有根树称为二叉树。常常对两个孩子的顺序加以区分，分别称之为左孩子和右孩子。
- 完整二叉树（full/proper binary tree）：每个结点的子结点数量均为 0 或者 2 的二叉树。换言之，每个结点或者是树叶，或者左右子树均非空。
- 完全二叉树（complete binary tree）：只有最下面两层结点的度数可以小于 2，且最下面一层的结点都集中在该层最左边的连续位置上。
- 完美二叉树（满二叉树）（perfect binary tree）：所有叶结点的深度均相同的二叉树称为完美二叉树。
- 平衡二叉树（AVL树）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 $n-1$ 条，将所有顶点连通。

二叉树计算公式

$n$ 个节点的二叉树一共有 $\frac{(2n)!}{n! (n+1)!}$ 种（Catalan数）
二叉树的第 $k$ 层最多有 $2^{k-1}$ 个节点（以 $1$ 起计数）
$n_0,n_1,n_2$ 表示节点度数为 $0,1,2$ 的节点个数，总节点数 $n=n_0+n_1+n_2=0\times n_0+1\times n_1+2\times n_2=n_1+2n_2$ ，由此还可推出 $n_0=n_2+1$
$n$ 个节点的完全二叉树的深度为 $\lfloor log_2{n}\rfloor + 1$

存储

无根树

vector存相邻节点最方便，类比图的存法

有根树

~~一个只存在书上的~~左孩子右兄弟表示法：每个节点记录第一个孩子节点 $child[u]$ 和下一个兄弟节点 $sib[u]$ ，跟链式前向星一样的

//遍历
for (int v = child[u]; ~v; v = sib[v]) { //为空置为-1
	//...
}

二叉树

数组：左右孩子 $child[i][0/1]$
指针：左右孩子指针，节点值 $val$ 。~~但是作为一个oi是自学c语言上手的人，有一说一，个人觉得指针表示法确实清晰，但确实不利好oi~~

遍历

二叉树

先序遍历

根+左子树+右子树

void dfs (int u)
{
    if(u == -1) return;
    printf("%d ", u);
    dfs(child[u][0]);
    dfs(child[u][1]);
}

中序遍历

左子树+根+右子树

void dfs (int u)
{
    if(u == -1) return;
    dfs(child[u][0]);
    printf("%d ", u);
    dfs(child[u][1]);
}

后序遍历

左子树+右子树+根

void dfs (int u)
{
    if(u == -1) return;
    dfs(child[u][0]);
    dfs(child[u][1]);
    printf("%d ", u);
}

二叉树特性

知中序+前/后序可知另一个：

前序序列第一个是根，后序序列最后一个是根
每个子树看成一颗新树

//已知中序后续求先序
char post_order[9], in_order[9];
int len;
void dfs(int il, int ir, int pl, int pr) //[il,ir]/[pl,pr]这颗子树
{
    putchar(post_order[pr]);
    int i;
    for (i = il; i <= ir; i++)
        if (post_order[pr] == in_order[i]) //找根节点，将中序中的树分开
            break;
    if (i > il)
        dfs(il, i - 1, pl, pl + i - il - 1); //i-il是左子树的长度
    if (i < ir)
        dfs(i + 1, ir, pl + i - il, pr - 1);
}
int main()
{
    scanf("%s%s", in_order, post_order);
    len = strlen(post_order);
    dfs(0, len - 1, 0, len - 1);
    return 0;
}

也就是可以求出这棵树了，以后序+中序为例

int tree[N][2]; // tree[i][0/1]是左右子树的节点编号，空置-1
int porder[N],iorder[N]; // porder后序遍历，iorder中序遍历
// 递归处理porder[mid]为根节点的子树，子树的中序遍历范围是iorder[l...r]闭区间
int solve(int mid, int l, int r) 
{
    if(l == r) // 叶子节点
        return porder[mid];
    if(l > r) // 空节点，返回编号-1
        return -1;
    // 找到根节点porder[mid]在中序遍历中的位置pos，从而[l,pos-1]和[pos+1,r]就是左右子树的中序范围
    int pos=l; 
    for(pos;pos<=r;pos++)
        if(iorder[pos]==porder[mid])
            break; 
   	// 递归求解右子树，根节点显然是后序的mid-1，中序范围[pos+1,r]
    tree[m[mid]][1]=solve(mid-1,pos+1,r);
    // 递归求解左子树，由于右子树共有r-pos+1个节点，则左子树的根节点在mid-1-r+pos
    tree[m[mid]][0]=solve(mid-r+pos-1,l,pos-1);
    return m[mid];
}
//main函数
memset(tree, -1, sizeof(tree));
solve(n-1, 0, n-1); // 后序的最后一个点是根节点

已知前序后序，中序不唯一

观察可知，造成不唯一的原因是一棵子树只有一个子节点，即前序：根+子，后续：子+根
只需要统计这样的子树有 $cnt$ 个，答案是 $2^{cnt}$ （可能左可能右）

char inorder[N];
char postorder[N];
int main()
{
    scanf("%s%s", inorder, postorder);
    int cnt = 0, len1 = strlen(inorder), len2 = strlen(postorder);
    for (int i = 0; i < len1 - 1; i++)
        for (int j = 1; j < len2; j++)
            if (inorder[i] == postorder[j] && inorder[i + 1] == postorder[j - 1]) 
                cnt++; //根节点相同，遍历顺序相反
    printf("%d", 1 << cnt);
    return 0;
}

无根树

void dfs(int u, int from)
{
    for (int v : adj[u]) //遍历相邻节点
        if (v != from) //不走回头路
            dfs(v, u);
}
// 开始遍历时
dfs(root, -1); // 如果担心在dfs中访问下标from的数组越界这里写dfs(root,0)