对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶节点。
输入格式:
首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 “-“。编号间以 1 个空格分隔。
输出格式:
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
1 2 3 4 5 6 7 8 9
| 8 1 - - - 0 - 2 7 - - - - 5 - 4 6
|
输出样例:
思路:
题目是按结点编号给出的左右孩子,所以不采用链式存储。定义一个结构体,存放左右孩子,node[i]代表编号为i的结点,node[i].left和node[i].right分别代表编号i的结点的左右孩子的编号。
然后进行数据读入和存储,然后我们用数组pre记录各个结点的父亲,pre[i]记录的是编号i的父亲编号。
题目说的是按照从上到下,从左到右的顺序输出叶子结点,很明显是层序遍历
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<bits/stdc++.h> using namespace std;
struct Node{ int left,right; }; int main(){ int n; cin >> n; Node node[n]; for(int i = 0; i < n; ++i){ char a,b; cin >> a >> b; node[i].left = (a == '-') ? -1 : a - '0'; node[i].right = (b == '-') ? -1 : b - '0'; } int pre[n]; memset(pre,-1,sizeof(pre)); for(int i = 0; i < n;++i){ if(node[i].left != -1) pre[node[i].left] = i; if(node[i].right != -1) pre[node[i].right] = i; } int pos = 0; for(int i = 0 ; i < n;++i){ if(pre[i] == -1){ pos = i;break; } } int flag = 1; queue<int> qu; qu.push(pos); while(qu.size() > 0){ int t = qu.front(); qu.pop(); if(node[t].left != -1) qu.push(node[t].left); if(node[t].right != -1) qu.push(node[t].right); if(node[t].left == -1 && node[t].right == -1) { if(flag) { flag = 0; cout << t; } else { cout << " " << t; } } } }
|