前言

在准备考研复习专业课数据结构,所以我在mooc平台上找了浙江大学的数据结构课程重新学习,感觉老师留的课后题都很有趣,所以想记录下自己的学习过程。

题目:

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:

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

Sample Output:

1
4 1 5

题解

题目大意

​ 题目的意思是要求按照从上到下,从左到右的顺序依次输出二叉树的叶子结点。

题目分析

​ 这题没什么好说的,直接用一个辅助队列进行层次遍历就可以得到结果。

完整代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<cstdio>
#include<cstring>
#define empty -1
using namespace std;
typedef struct Btree{
int data;
int left;
int right;
};
struct Queue{
int front;
int rear;
int data[11];
}h_queue;//为了实现层序遍历的辅助队列
bool Init_queue(Queue &q){//初始化队列
q.front = 0;
q.rear = 0;
return true;
}
bool Is_empty(Queue &q){
if(q.rear==q.front)
return false;
else
return true;
}
bool Add_item(Queue &q,int x){//入队
if((q.rear+1)%11==q.front)
return false;
q.rear = (q.rear+1)%11;
q.data[q.rear] = x;
return true;
}
int Delete_item(Queue &q){//出队
if(q.rear==q.front)
return false;
q.front = (q.front+1)%11;
return q.data[q.front];
}
void read_leaves(Btree *q,Queue &h_queue,int head,int result[]){
int count = 0,i=0;
Add_item(h_queue,head);
while(Is_empty(h_queue)){
i = Delete_item(h_queue);
if(q[i].left==empty&&q[i].right==empty)
result[count++] = q[i].data;
if(q[i].left!=empty)
Add_item(h_queue,q[i].left);
if(q[i].right!=empty)
Add_item(h_queue,q[i].right);
}
}
int main(){
int n=0,judge[11]={0},head=0,result[11];
memset(result,-1,sizeof(result));
char save[3];
scanf("%d",&n);
Btree tree[11];
//读取二叉树
for(int i=0;i<n;i++){
scanf("\n%c %c",&save[0],&save[1]);
tree[i].data = i;
if(save[0]!='-'){
tree[i].left = save[0] - '0';
judge[tree[i].left] = 1;
}
else
tree[i].left = empty;
if(save[1]!='-'){
tree[i].right = save[1] - '0';
judge[tree[i].right] = 1;
}
else
tree[i].right = empty;
}
//找头节点
for(int i=0;i<n;i++){
if(!judge[i])
head = i;
}
//读取叶结点保存到result数组中
if(head!=empty){
Init_queue(h_queue);
read_leaves(tree,h_queue,head,result);
}
//打印结果
if(result[0]!=-1)
printf("%d",result[0]);
int i=1;
while(result[i]!=-1)
printf(" %d",result[i++]);
return 0;
}