树的深度优先搜索

问题引入 PTA A1004

问题描述

有一个树，求每个层次的叶节点数目。通俗的理解就是，给个家谱，求每代没后代的。

输入描述

先给出结点数n和叶节点数m，在接下来的m行的每行里，先给出父节点的编号ID，再给出子节点的个数K，在给出K个子节点的编号ID[1]、ID[2]······、ID[K]。

输出描述

依次给出每个层次的叶节点数目。

问题分析

树的遍历有两种，DFS和BFS，这里以DFS为例。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int ans[100], mx;	//ans[]记录每个层次的叶节点数目，mx记录最大层次。
vector<int> v[100];	//用vector存图
void dfs(int k, int fa)
//第k层次以及当前父节点
{
    int len = v[fa].size();
    if (!len) {	//len为0，无子节点。即叶节点
        ++ans[k];	//第k层的答案+1
        mx = max(mx, k);	//记录最大层数
        return;
    }
    for (int i = 0; i < len; ++i) dfs(k+1, v[fa].at(i));//迭代深搜
}
int main()
{
    int n, m, id, k, ch;
    while (cin >> n >> m && n) {
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < m; ++i) {
            cin >> id >> k;
            for (int j = 0; j < k; ++j) {
                cin >> ch;
                v[id].push_back(ch);
            }
        }
        dfs(0, 1);//从第0层开始dfs，根节点编号为01
        printf("%d", ans[0]);
        for (int i = 1; i <= mx; ++i) printf(" %d", ans[i]);
    }
    return 0;
}

树的dfs

原文：https://www.cnblogs.com/xdaniel/p/12682696.html