pta 编程题7 List Leaves

其它pta数据结构编程题请参见：pta

这次的编程作业要求从上到下，从左到右输出一棵树的叶子节点，即树的层序遍历，用队列的方式来实现。

注意enqueue和dequeue函数参数为Queue &q，而不是Queue q，即用引用的方式才能改变实参的值。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct Node
 5 {
 6     int left;
 7     int right;
 8 };
 9 
10 struct Queue
11 {
12     int data[10];
13     int first = -1;
14     int end = -1;
15     int maxSize = 10;
16 };
17 
18 int buildTree(Node tree[]);
19 void enqueue(Queue &q, int i);
20 int dequeue(Queue &q);
21 bool empty(Queue q);
22 
23 int main()
24 {
25     Node tree1[10];
26     int root = buildTree(tree1);
27     Queue q, leaves;
28     int t, cnt = 0;
29     enqueue(q, root);
30     while (!empty(q))
31     {
32         t = dequeue(q);
33         if (tree1[t].left == -1 && tree1[t].right == -1)
34             enqueue(leaves, t);
35         if (tree1[t].left != -1) enqueue(q, tree1[t].left);
36         if (tree1[t].right != -1) enqueue(q, tree1[t].right);
37     }
38     while (!empty(leaves))
39     {
40         if (cnt > 0) cout << " ";
41         cout << dequeue(leaves);
42         cnt++;
43     }
44     return 0;
45 }
46 
47 int buildTree(Node tree[])
48 {
49     int num, i, root = -1;
50     char l, r;
51     cin >> num;
52     int judgeRoot[10] = {};
53     for (i = 0; i < num; i++)
54     {
55         cin >> l >> r;
56         if (l != '-')
57         {
58             tree[i].left = l - '0';
59             judgeRoot[l - '0'] = 1;
60         }
61         else tree[i].left = -1;
62         if (r != '-')
63         {
64             tree[i].right = r - '0';
65             judgeRoot[r - '0'] = 1;
66         }
67         else tree[i].right = -1;
68     }
69     for (i = 0; i < num; i++)
70     {
71         if (judgeRoot[i] == 0) root = i;
72     }
73     return root;
74 }
75 
76 void enqueue(Queue &q, int i)
77 {
78     q.end = (q.end + 1) % 10;
79     q.data[q.end] = i;
80 }
81 
82 int dequeue(Queue &q)
83 {
84     q.first = (q.first + 1) % 10;
85     return q.data[q.first];
86 }
87 
88 bool empty(Queue q)
89 {
90     return q.end == q.first;
91 }