7-1 列出叶结点（25 分）
对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。 输入格式：
首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-“。编号间以 1 个空格分隔。 输出格式：
在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。 输入样例：
8 1 - - - 0 - 2 7 - - - - 5 - 4 6
输出样例：
4 1 5
思路 先找出 根节点
怎么找呢 可以想到 根节点 不会是任何一个结点的 儿子 那么 我们只要标记一下 那些儿子 剩下的哪一个 就是 根节点
然后从根节点 往下遍历
遍历到 一个结点 没有儿子的 那么就将它 push 进一个 vector
然后最后 输出就可以了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; int v[10]; struct Node { int l, r; }q[10]; void init() { CLR(q); CLR(v); } queue <int> Q; vector <int> ans; void bfs() { int len = Q.size(); for (int i = 0; i < len; i++) { int num = Q.front(); Q.pop(); if (q[num].l == -1 && q[num].r == -1) ans.pb(num); if (q[num].l != -1) Q.push(q[num].l); if (q[num].r != -1) Q.push(q[num].r); } if (Q.size()) bfs(); } int main() { init(); int n; scanf("%d", &n); char a, b; for (int i = 0; i < n; i++) { scanf(" %c %c", &a, &b); if (a == '-') q[i].l = -1; else { q[i].l = a - '0'; v[a - '0'] = 1; } if (b == '-') q[i].r = -1; else { q[i].r = b - '0'; v[b - '0'] = 1; } } int root; for (int i = 0; i < n; i++) { if (v[i] == 0) { root = i; break; } } Q.push(root); bfs(); vector <int>::iterator it; for (it = ans.begin(); it != ans.end(); it++) { if (it != ans.begin()) printf(" "); printf("%d", *it); } cout << endl; }转载于:https://www.cnblogs.com/Dup4/p/9433187.html
相关资源：用C语言求二叉树叶子结点