树及树的遍历

几个概念和性质

·树可以没有结点,此情况下称为空树(empty tree)
·树的层次(layer)从根结点开始算起,即根节点为第一层
·把节点的子树棵树称为结点的度(degree),而树中结点的最大值的度称为树的度
·树的边数等于结点数减1,反之,满足连通且边数等于结点数减1即为树
·结点深度自顶向下累加,结点高度自底向上累加

树的静态写法

1
2
3
4
struct node{
typename data;
vector<int> child;
}Node[maxn];

若data值为下标本身,则直接建立vector数组

1
vector<int> v[maxn];

树的先根遍历(即DFS)

1
2
3
4
5
void dfs(int root){
printf("%d",Node[root].data); //访问当前结点,此处将data输出
for(int i=0;i<Node[root].child.size();i++)
dfs(Node[root].child[i]);
}

树的层序遍历(即BFS)

(如要记录结点层号,在node结构体定义中增加layer变量)

1
2
3
4
5
struct node{
int data;
int layer;
vector<int> child;
}Node[maxn];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bfs(int root){
queue<int> q;
q.push(root);
Node[root].layer=0;
while(!q.empty()){
int front=q.front();
printf("%d",Node[front].data); //访问当前结点
q.pop();
for(int i=0;i<Node[front].child.size();i++){
int child=Node[front].child[i];
Node[child].layer=Node[front].layer+1;
q.push(child);
}
}
}