满树的遍历--题解

题干：

考察多叉树的遍历

主要实现的功能：

1. 根据输入的父节点关系构建一棵树
2. 计算树的度（最大子节点数）
3. 判断是否是k阶满树（所有非叶子节点的子节点数都相等）
4. 输出前序遍历序列

具体代码实现如下：

#include<bits/stdc++.h> using namespace std; vector<int>g[100010]; // 邻接表存储树，g[i]存储节点i的所有子节点 int root; // 根节点编号 int maxdegree; // 树的度（最大子节点数） bool kflg=0; // 标志位：0表示是满树，1表示不是满树 vector<int>pre; // 存储前序遍历结果 // 深度优先搜索（前序遍历） void dfs(int ver){ // 判断当前节点是否违反满树条件 // 条件：如果当前节点不是叶子节点(g[ver].size()!=0) // 并且它的子节点数不等于最大度(g[ver].size()!=maxdegree) if(g[ver].size()!=0 && g[ver].size()!=maxdegree){ kflg=1; // 标记为不是满树 // 更新最大度（这行逻辑有问题，后面分析） maxdegree=max(maxdegree,(int)g[ver].size()); } pre.push_back(ver); // 前序遍历：先访问根节点 // 递归访问所有子节点 // 注意：这里没有对子节点排序，但题目要求兄弟节点按编号升序排列 for(int i=0;i<g[ver].size();i++){dfs(g[ver][i]);}return;}intmain(){intn;cin>>n; // 输入节点个数 // 构建树结构 for(int i=1;i<=n;i++){ int x; cin>>x; // 输入第i个节点的父节点编号 if(x==0) root=i; // 如果父节点为0，则i是根节点 else g[x].push_back(i); // 否则将i加入x的子节点列表 } // 初始化最大度：至少包含根节点的子节点数 maxdegree=max(maxdegree,(int)g[root].size()); dfs(root); // 从根节点开始前序遍历 // 输出树的度 cout<<maxdegree<<' '; // 输出是否是满树 if(kflg==0) cout<<"yes\n"; else cout<<"no\n"; // 输出前序遍历序列 for(int i=0;i<pre.size();i++){ if(i) cout<<" "; cout<<pre[i]; } return 0; }