本文主要是介绍03-2. List Leaves (25) 树的层次遍历,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
首先,根据输入的信息建树,然后寻找根节点。
寻找根节点的方法:用一个数组来标记每一个节点是否是其他节点的孩子节点,在输入中出现过得肯定不是根节点,因为输入的为节点左右孩子编号。
之后从根开始层次遍历,将叶子节点保存在数组中,再按格式输出即可。
/************************************************ Author: fisty* Created Time: 2015/1/11 21:11:06* File Name : 03-2.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << "x" << x <<endl
const int INF = 0x3f3f3f3f;
#define MAX_N 14
vector<char> G[MAX_N];
int used[MAX_N]; //记录数根
int find(int *a, int n){//寻找根节点int root = 0;for(int i = 0;i < n; i++){if(!a[i]){root = i; break;}}return root;
}
int main() {//freopen("in.txt", "r", stdin);cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;memset(used, 0, sizeof(used));for(int i = 0;i < n; i++){char a;for(int j = 0;j < 2; j++){cin >> a;if(a != '-'){G[i].push_back(a-'0');//如果被当做儿子,那么一定不会是树根used[a-'0'] = 1;}}}int root = find(used, n);//层次遍历,从上到下,从左到右输出叶子节点int ans[MAX_N]; int cnt = 0;queue <int> que;que.push(root);while(!que.empty()){int v = que.front(); que.pop();int ok = 0;for(int i = 0;i < G[v].size(); i++){//遍历v的孩子节点ok = 1; //如果有孩子节点que.push(G[v][i]); //压入队列}if(!ok) {//如果没有孩子节点,保存ans[cnt++] = v;}}for(int i = 0;i < cnt; i++){printf("%d%c", ans[i], i == cnt-1 ? '\n' : ' ');}return 0;
}
这篇关于03-2. List Leaves (25) 树的层次遍历的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!