#2020寒假集训#树形入门（Tree）代码笔记

树的基础定义

【无根树】一棵没有固定根结点的树（树→图：无向图）

（补充一）无根树可以任意指定一个节点作为根节点，将根节点“提起”，其它节点自然“垂下”

【无根树】在无根树的基础上，指定一个结点称为根 （树→图：有向图）

（补充二）有根树在很多时候仍以无向图表示，只是规定了结点之间的上下级关系

Part One 适用于无根树&有根树

• 森林（Forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林
• 生成树（Spanning Tree）：一个连通无向图的生成子图，同时要求是树。即在图的边集中选择N-1条，将所有顶点连通
• 结点的深度（Depth）：到根结点的路径上的边数
• 结点的度数（Degree）：结点拥有子结点的数量
• 树的高度（Height）：所有结点的深度的最大值
• 无根树的叶结点（Leaf Node）：度数不超过1的结点（N==1时，只有一个结点，度数为0）
• 有根树的叶结点（Leaf Node）：没有子结点的结点。

Part Two 只适用于有根树

• 父亲结点**（Parent Node）：从该结点到根路径上的第二个**结点（自己是第一个）根结点没有父结点
• 祖先结点**（Ancestor）：一个结点到根结点的路径上**，除了它本身外的结点；根结点的祖先集合为空
• 子结点**（Child Node）：如果 u 是 v 的父亲，那么 v 是 u 的子结点（二叉树区分子结点顺序**）
• 兄弟结点**（Sibling）：同一个父亲的多个子结点**互为兄弟
• 后代（Descendant）：子结点和子结点的后代**；如果 u 是 v 的祖先，那么 v 是 u 的后代（有些地方称子孙结点）
• 子树**（Subtree）**：删掉与父亲相连的边后，该结点所在的子图
  

特殊的树

• 链（Chain/Path Graph）：满足与任一结点相连的边不超过2条的树
• 菊花/星星（Star）：满足存在 u 使得所有除 u 以外结点均与 u 相连的树
• 二叉树（Binary Tree）：每个结点最多只有两个儿子（子结点，且分左子结点和右子结点）
• 有根二叉树 （Rooted Binary Tree）：二叉树中的有根树；大多数情况下， 二叉树一词均指有根二叉树
• 完整二叉树 （Full/Proper binary tree）：每个结点的子结点数量均为 0 或者 2 （叶子结点or左右子树均非空）的二叉树
• 完全二叉树 （Complete Binary Tree）：仅叶子结点度数为1，其他度数都达到最大，叶子结点从左到右依次排布
• 完美二叉树 （Perfect Binary Tree）：所有叶子结点的深度均相同的二叉树（满二叉树：多指完美二叉树）

树的存储

Part One 链式前向星

#define fzhead EDGE(int _from,int _to,int _w,int _next)
#define fzbody from(_from),to(_to),w(_w),next(_next)
using namespace std;
const int maxn=1e5+10;
int head[maxn],edgecount;
struct EDGE
{
	int from,to,w,next;
/*
	Edge(){}是个用来给变量初始化0的函数
	fzhead:fzbody{}为结构体赋初值
*/
	EDGE(){}//后面别加分号 
	fzhead:fzbody{}//后面别加分号 
}edge[maxn];
void init()
{
	memset(head,-1,sizeof(head));
	edgecount=-1;
}
/*
	i：边的编号；从u到v；w：权值；next：下一条边的编号
	head[i]：由i出发的第一条边的编号
	仅插入一条从u1开始的边，则next是-1，head[u1]为该边的编号
	再读入u1开始的边，则其为第一条边，next是上一条边的编号 
*/
void addEdge(int from,int to,int w)//链序和读入顺序相反 
{
	edge[++edgecount]=EDGE(from,to,w,head[from]);
	head[from]=edgecount;
}

Part Two Vector邻接表

#define fzhead EDGE(int _to,int _w)
#define fzbody to(_to),w(_w)
using namespace std;
const int maxn=1e5+10;
int n; 
struct EDGE
{
	int to,w;
/*
	Edge(){}是个用来给变量初始化0的函数
	fzhead:fzbody{}为结构体赋初值
*/
	EDGE(){}//后面别加分号 
	fzhead:fzbody{}//后面别加分号 
};
vector<EDGE> edge[maxn];
void init()
{
	for(int i=1;i<=n;++i) edge[i].clear();
}
/*
	i：边的编号；从u到v；w：权值；next：下一条边的编号
	head[i]：由i出发的第一条边的编号
	仅插入一条从u1开始的边，则next是-1，head[u1]为该边的编号
	再读入u1开始的边，则其为第一条边，next是上一条边的编号 
*/
void addEdge(int from,int to,int w)//链序和读入顺序相反 
{
	edge[from].push_back(EDGE(to,w));
}

树的遍历

前言

• 按照结点被访问的顺序，进行标号，可以形成DFS序和BFS序
• 【DFS序的性质】
• 记录某结点第一次被访问到的序号和第二次被访问到的序号(也就是递归完退回来时候的序号)
  两个序号之差就是子树的大小，同时两个序号之间连续的一段都在子树内
  也就是说子树的关系被压缩到一维了，可以用一维的数据结构来维护了，比如线段树
• 对于树上任何一个结点，它祖先的DFS序一定小于它自己
• 【BFS序的性质】
• 深度越深的结点标号越大，按照标号从大到小遍历，就相当于从子树向根遍历了，不用递归

二叉树的深度优先搜索

• 先序遍历
  先访问根节点，然后依次访问左儿子和右儿子
• 中序遍历
  先访问左儿子，然后依次访问根节点和右儿子
• 后序遍历
  先访问左儿子，然后依次访问右儿子和根节点
• 已知中序遍历和另外一个，可以还原整颗树
• ps：三序遍历的顺序可按照根结点被遍历的位置来记忆

Part One DFS深度优先搜索

**以链式前向星存储为例**
void DFS(int root)//传入根结点序号
{
	num[root]=1;
	vis[root]=true;
	for(int i=head[root];i!=-1;i=edge[i].next)
	{
		if(vis[edge[i].to]==true) continue;//如果子结点已被访问则跳过（防无向图）
		DFS(edge[i].to);
	}
}

Part Two BFS广度优先搜索

**以链式前向星存储为例**
void BFS(int u)//传入根结点序号
{
    Max=0;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(u);
    vis[u]=true;
    while(!Q.empty())
	{
        int root=Q.front();
        Q.pop();
        for(int i=head[root];i!=-1;i=edge[i].next)
		{
            if(vis[edge[i].to]==true) continue;//如果子结点已被访问则跳过（防无向图）
			Q.push(edge[i].to);
            vis[edge[i].to]=true;
        }
    }
}

树的重心

定义

• 对于树上的每一个点，计算其所有子树中最大的子树结点数，这个值最小的点就是这棵树的重心
• 此定义中的 “子树”指无根树的子树，即包括“向上”的那棵子树，并且不包括整棵树自身

性质

• 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半
• 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样
• 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上
• 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离

求法（代码）

int get_barycenter(int root,int dady)
{
	size[root]=1;//记录一棵子树的结点数（一棵子树的大小），root作根结点初始大小为1 
	Max[root]=0;
	for(int i=head[root];i!=-1;i=edge[i].next)
	{
    	if (edge[i].to!=dady)
		{
			get_barycenter(edge[i].to,root);//递归，从叶子结点大小为 1 开始回推赋值 
			size[root]+=size[edge[i].to];//结点数累加，对root根结点而言的 
			Max[root]=max(Max[root],size[edge[i].to]);//对root子树而言的 
			//对于树上的每一个root，计算其所有子树中最大的子树结点数 
		}
	}
	Max[root]=max(Max[root],n-size[root]);
	/*
		n为总结点数，定义中的**子树**指无根树的子树
		size[edge[i].to]是向下的；n-size[root]是向上的
		减去自身这整棵树的结点数，剩下的就是向上的子树的结点数啦 
		用向下的最大值，与向上的比较得到最终的最大值 
	*/
	if (center==0||Max[root]<Max[center]) center=root;
	//center初始化为0，还未被更新过值或得到更小的最大子树结点数，就用当前root更新重心center 
	return center;//center为重心编号
}

树的直径

树形DP

树链剖分

虚树

例题

更新中-ing