03-树2 List Leaves (25分)
原题如下： Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.
Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.
Output Specification: For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
4 1 5
分析
这道题其实就是两个关键点，输入存储与层次遍历 关于输入与存储，这道题和上一道题特别像 树的同构 只不过这道题比那道题还简单，每个结点的值就是数组下标。 关于输入，其实就是层次遍历的变种，层次遍历输出时，加一个判断是否左右子树为空，如果为空就是叶子节点了。之后注意一下输出的空格的格式就可以了
完整代码实现
#include <iostream>
#include <queue>
#define NULL -1
using namespace std
;
struct TreeNode
{
int num
;
int left
;
int right
;
}T
[10];
int buildTree()
{
int n
;
int root
= 0;
char left
,right
;
cin
>>n
;
if(!n
){
return NULL;
}
for(int i
=0;i
<n
;i
++){
T
[i
].num
= i
;
cin
>>left
>>right
;
if(left
== '-'){
T
[i
].left
= NULL;
}else{
T
[i
].left
= left
-'0';
root
-= T
[i
].left
;
}
if(right
== '-'){
T
[i
].right
= NULL;
}else{
T
[i
].right
= right
- '0';
root
-= T
[i
].right
;
}
root
+= T
[i
].num
;
}
return root
;
}
void LevelOrder(int root
)
{
queue
<struct TreeNode
> queue
;
struct TreeNode t
;
int flag
= 0;
if(root
== NULL){
printf("-");
return;
}
queue
.push(T
[root
]);
while(!queue
.empty()){
t
= queue
.front();
queue
.pop();
if(t
.left
== NULL && t
.right
== NULL){
if(flag
!= 0){
printf(" ");
}else{
flag
= 1;
}
printf("%d",t
.num
);
}
if(t
.left
!= NULL){
queue
.push(T
[t
.left
]);
}
if(t
.right
!= NULL){
queue
.push(T
[t
.right
]);
}
}
}
int main()
{
int root
;
root
= buildTree();
LevelOrder(root
);
return 0;
}
