树

树的定义

• 每个元素称为节点。
• 有一个特定的节点，称为根节点或树根。
• 除根节点外，其余节点能分成$m(m\ge 0)$个互不相交的有限集合$T_0,T_1,T_2,...,T_{m-1}$。其中每个子集又都是一棵树，这些集合称为这棵树的子树。

树的基本概念

• 树是递归定义。
• 一棵树中至少有1个节点。这个节点就是根节点，它没有前驱，其余每个节点都有唯一的一个前驱节点，每个节点可以有$0$或多个后继节点。
• 一个节点的子树个数，称为这个节点的度，而节点的度的最大值称为这棵树的度。
• 在树型结构中，前驱节点是当前节点的父亲，同一层的节点为兄弟。
• 定义一棵树的根节点的层次（$level$）为$1$，其它节点的层次等于它的父节点层次加$1$。
• 对于树中任意两个不同的节点，如果从一个节点出发，自上而下沿着树中连着的节点的边能到达另一个节点，称它们之间存在着一条路径，路径的长度等于路径上的节点个数减1。
• 多棵互不相交的树组成森林。

树的存储结构

父亲表示法

结构体写法

const int m = 10;
struct node{
	int data,father;
}tree[m];

数组写法

const int m = 10;
int data[m],father[m];

结构体都可以拆成数组写法，但用结构体表达更清晰。

孩子表示法

结构体写法
一个变量保存节点的值，一个数组保存孩子的位置。

const int m = 10;
struct node{
	int data,child[m];
}tree[MAXN];  //假设有MAXN个节点

假设有$n$个节点，每个节点告诉你：$data$，节点数$k$，$k$个孩子节点编号（位置），那么读入方式如下：

#include<bits/stdc++.h>
using namespace std;
const int m= 10;
struct node{
	int data,child[m];
}tree[15];
int cnt,n;
int main()
{	
	cin>>n;
	for(int i = 1; i <= n; i++){  //假设按节点编号1到n给出
		int data,x,k;
		cin>>data>>k;
		tree[++cnt].data = x;
		for(int j = 1; j <= k; j++){
			int y;
			cin>>y;
			tree[cnt].child[j] = y;
		}	
	}
	return 0;
 } 

父亲孩子表示法

一个变量保存节点的值，一个变量保存父亲位置，一个数组保存孩子位置。

const int m = 10;
struct node{
	int data,father,child[m];
}tree[15];

因为节点编号是唯一的，所以可以用数组来模拟树型结构，节点间的联系用变量或数组来保存。

课后习题

1826-找树根和孩子