1.树导论

1.1.基础定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因
为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

这是一颗树

1.2.树的特性

一棵树中任意两个结点有且仅有唯一的一条路径连通。
一棵树如果有n个节点， 那么它一定有n-1条边。
在一棵树中添加一条边将会构成一个回路。
一棵有 n个节点的无向树，所有节点的度数和为2× (?? ? 1) 。
树形结构以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。树形结构
中元素之间有着明显的层次关系，每一个元素可以和下层的多个元素相关， 但只能和上层
中一个元素相关。

1.3.树与链表

链表是一棵特殊的树。我们可以将链表的头节点看作树的根。树的每个节点可以有多个
next ，我们称之为子节点。所以链表是一棵每个节点都只有一个子节点的树。

1.4.树的基本操作-树的存储与创建

在创建一棵树的时候， 使用什么方法去存储呢？
可以采用与链表类似的方法。但由于子节点的数量不确定， 因此我们想到用vector来存储
树的子节点。
在一般树中，子节点的数量没有限制，所以常用的存储方法是使用vector数组G， G[0]保
存编号为0的顶点连接到的所有顶点， 由于n个结点的树只有n-1条边， vector数组实际占
用的空间为O(n) 。
每读到一条边(u,v) ，如果不知道谁是父亲谁是儿子，我们可以先在G[u]中添加一个v ，再
在G[v]中添加一个u 。
如果知道父子关系，可以只在父节点中添加儿子，而不用将边保存两份。

vector G[100005]; //每个vector用来记录所有子节点的编号
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
    int u, v;
    scanf("%d %d",&u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
    }
    return 0;
}

1.5.删除树的点和边

删除节点u时需要删除该节点的所有边。
Del(当前节点u){
    for(u有连边的节点v){
        从G[v]中删除u;
    }
    清空G[u];
}
删除边(u,v) 。
Del(边(u,v)){
    从G[v]中删除u;
    从G[u]中删除v;
}

1.6.树的遍历

遍历树的方式有很多，最常用的方式是DFS 。
DFS(当前节点u){
    for(u的所有子节点v){
        DFS(v);
    } 
}
如果是在不知父子的情况下，保存了双向边，那么需要做如下处理。
DFS(当前节点u, 父节点p){
    for(u有连边的节点v){
        if(v不是p)
            DFS(v, u);
    } 
}

1.7.例题:叶子节点的数量

给出一棵n个节点的树，节点编号为1-n（根节点编号为1），求这棵树叶子结点的数量。
例如：
1─2─4─5
└─3
其中3和5是叶子节点，输出2。
1.7.1.输入

第一行：1个数n（1 < n <= 1000），表示树的节点数量。
后面n-1行：每行2个数x y，表示节点x是节点y的父节点（1 <= x, y <= n）。

1.7.2.输出

输出1个数，表示这棵树有多少个叶子节点。

1.7.3.输入样例

5
1 2
1 3
2 4
4 5

1.7.4.输出样例

2

1.7.5.分析
可以用一个bool数组t[i]来存储每一个节点，t[i]表示第i个节点是否有子节点，如果没有，i就是叶子节点。但要注意输入 n-1次，判断t[i]是否为false时要循环n次。t数组要开在外边，否则在main函数里要memset初始化一下。
1.7.6.代码

#include 
using namespace std;
bool t[1010]; 
int main() {
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        t[a] = true;
    }
    for(int i = 1; i <= n; i++) if(!t[i]) ans++;
    cout << ans << endl;
    return 0;
}

1.8 树的高度与子树-求节点的深度

在这个问题中，我们最初可以知道根节点的深度为1，而且除了根节点以外的每个节点的深度都等于他父节点的深度加1。所以我们需要再DFS的过程中记录两个变量，一个变量是当前节点的编号，另一个是当前节点父节点的编号，这样我们就可以开始树上DFS。

vector G[maxn];
int dep[maxn];
void dfs(int rt, int fa) //rt为当前节点编号， fa为当前节点的父节点编号
{
	//深度等于父节点深度+1
	dep[rt] = dep[fa] + 1;
	for(int i = 0; i < G[rt].size(); i++)
	{
		int to = G[rt][i];
		if(to == fa) continue; //不走父节点那条边
		dfs(to, rt);
	}
}

1.9 树的高度与子树-求字树大小

在这个问题中我们首先可以知道的是叶子节点的子树大小为 1，而且除了叶子节点以外的每个节点的子树大小都等于他所有子节点子树大小之和。之后再从叶子向根节点计算每棵子树的大小即可。

vector G[maxn];
int size[maxn];
void dfs(int rt, int fa) //rt为当前节点编号， fa为当前节点的父节点编号
{
	//深度等于父节点深度+1
	size[rt] = 1;
	for(int i = 0; i < G[rt].size(); i++)
	{
		int to = G[rt][i];
		if(to == fa) continue; //不走父节点那条边
		dfs(to, rt);
		size[rt] += size[to]; //处理完子节点最后再处理父节点
	}
}

2.树模型

2.1.特殊的树-二叉树

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（leftsubtree）和“右子树”（right subtree）。

这部分知识，我们在之前的学习中已经介绍过，这里只是回顾一下。下图就是一棵二叉树。

二叉树是特殊的树，也是很常用的数据结构，许多树模型以及数据结构模型，都是建立在二叉树的基础上

2.2.B树

1970 年， R.Bayer和E.mccreight提出了一种适用于外查找的，它是一种平衡的多叉树，称为B树。

与平衡二叉树类似，只是他是多叉的。

可以想象，假如每一层的分叉达到上千个，在这个树里做查找，近乎于顺序查找。

相比平衡二叉树所对应的二分查找，效率要低很多，那么这样的数据结构，有什么用处呢？

实际上是因为对于很多存储设备来说，顺序读的速度经常是随机读的数十倍，比如我们的机械硬盘，在这种设备上，用二叉的方式来做查询，时间将全部花在寻道上。这时B-Tree的优势就体现出来了。

2.3.例题:叶子节点的路径

2.3.1题目

请去http://www.51nod.com/Challenge/Problem.html#problemId=3039查看

2.3.2分析

对每个节点的子节点，按照节点编号从小到大排序，这样在遍历树的过程中，路径的字典序是从小到大的。

遍历过程中，用一个数组保存保存从根到当前节点路径中的所有节点。遍历到叶子节点时直接输出即可。

2.3.3 代码

#include
using namespace std;
const int maxn=1e5+50;
vector G[maxn];
int path[maxn];
void dfs(int rt, int fa, int deep)
{
	int count = 0;
	path[deep] = rt;
	for(int i = 0; i < G[rt].size(); i++)
	{
		int to = G[rt][i];
		if(to == fa) continue;
		count++;
		dfs(to, rt, deep + 1);
	}
	if(count == 0)
	{
		for(int i = 0; i <= deep;i++)
			cout << path[i] << " ";
		cout << endl;
	}
}
int main(){
	int n, u, v;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0,0);
	return 0;
}

2.4 最近公共祖先

最近公共祖先是相对于两个节点来说的，一般来说，最近公共祖先为节点u和节点v的最近的公共祖先。若u为v的祖先或者v为u的祖先，则LCA(u,v)就是作为祖先的那个节点。示例图中86和67的LCA是75 ， 61和85的LCA也是75 。

2.5 树的权值

在之前的内容中，叶子的深度代表从根到叶子，经过的边的数量。假如我们认为每条边的长度是不同的，那么叶子的深度就是从根到叶子的所有边长度的和。

在这里边的长度称为边权（边的权值）。

同样，在计算子树大小时，如果每一个点都有不同的大小，那么子树的大小就是当前节点大小 + 所有子孙的大小之和。

在这里点的大小称为点权（点的权值）。

之前所学的一些模型是比较特殊的模型，即边权和点权都等于 1。作为更一般的情况，则可能边有边权，点有点权。

总结

谢谢大家看到这里，记得点赞哦！

不懂的可以在评论去提问，博主很乐意回答!