7-3 列出叶结点 (25分)

 

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

输入格式：

首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 "-"。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8 1 - - - 0 - 2 7 - - - - 5 - 4 6

输出样例：

4 1 5

 

#include<iostream> #include<cstdio> #include<string> #include<ctype.h> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<queue> #include<set> using namespace std; const int inf=0x3fffffff; const int maxn=10010; vector<int> v; struct Node{ int father; int data; int lchild,rchild; Node(){ father = lchild = rchild = -1; } }node[11]; int findfather(int i){ while(node[i].father!=-1) i = node[i].father; return i; } int main(){ int n; cin>>n; getchar(); char a,b; string str; for(int i=0;i<n;i++){ getline(cin,str); a=str[0],b=str[2]; if(a!='-'){ node[i].lchild = a-'0'; node[a-'0'].father=i; } if(b!='-'){ node[i].rchild = b-'0'; node[b-'0'].father=i; } node[i].data=i; } int f = findfather(0); queue<Node> q; q.push(node[f]); while(q.size()!=0){ Node t = q.front(); q.pop(); if(t.lchild!=-1) q.push(node[t.lchild]); if(t.rchild!=-1) q.push(node[t.rchild]); if(t.lchild==-1 && t.rchild==-1){ v.push_back(t.data); } } for(int i=0;i<v.size();i++){ if(i) cout<<" "; cout<<v[i]; } return 0; }