5.4 树、森林 Tree Forest

基础概念

相关提炼内容见 tree union-find。

树的存储结构

双亲表示法
孩子表示法
孩子兄弟表示法

树、森林与二叉树的转换

树和森林的遍历

先根遍历
后根遍历（部分教材也将森林中的中根遍历称为后根遍历）

树的应用——并查集

Union(S, Root1, Root2)
Find(S, x)
Initial(S)
并查集的结构定义

#define SIZE 100
int UFSets[SIZE];

并查集的初始化操作

void initUFSets(int S[]){
for(int i = 0; i < SIZE; i++)
S[i] = -1;
}

并查集的查找操作

int Find(int S[], int x){
if(S[x] >= 0) x = S[x];
return x;
}

并查集的合并操作

void Union(int S[], int Root1, int Root2){
S[Root2] = Root1;
}