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
题意:给定一棵树,输出它的叶子结点,是层序输出
思路:既然给出的数是一组组数据,那最好就是用顺序存储的第二种方式(二叉树顺序存储第二种方式),一开始我以为结构体只需要两个数据,即左右地址,但是当我们输出的时候是输出结点值,此时我们还是需要第三个数据来存储结点的值,结点的值是啥?就是第一行值就是1,题目是从第0行开始的。之后,直接遍历就行了。实现了遍历,比如输出叶子结点,或者输出结点个数,或者计算结点值在二叉树的层次等等都易如反掌,这一类我在二叉树有一个专题(由二叉树遍历衍生出来的各种函数算法)。
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 |
#include<iostream> #include<queue> #define null -1 using namespace std; struct treenode { int data; int right; int left; }t1[10]; int createtree(struct treenode t[]) { int n, i; char cl, cr; cin >> n; int check[10]; int root = null; if (n) { for (i = 0; i < n; i++)check[i] = 0; for (i = 0; i < n; i++) { t[i].data = i; cin >> cl >> cr; if (cl != '-') { t[i].left = cl - '0'; check[t[i].left] = 1; } else t[i].left = null; if (cr != '-') { t[i].right = cr - '0'; check[t[i].right] = 1; } else t[i].right = null; } for (i = 0; i < n; i++) if (!check[i])break; root = i; } return root; } void printleaves(int r1) { queue <struct treenode> q; q.push(t1[r1]); struct treenode t; bool flag = false; if (r1 == null) { cout << "-"; return; } while (!q.empty()) { t = q.front(); q.pop(); if (t.left == -1 && t.right == -1) { if (flag) cout << " "; else flag = true; cout << t.data; } if (t.left != -1) q.push(t1[t.left]); if (t.right != -1) q.push(t1[t.right]); } } //这里我审题不注意,写成了前序遍历,要认真审题啊, //void preleaves(int r1) { // if ( r1 != -1){ // if(t1[r1].left==-1&&t1[r1].right==-1) // cout << t1[r1].data << " "; // preleaves(t1[r1].left); // preleaves(t1[r1].right); // } //} int main() { int r1 = createtree(t1); // cout<<r1<<endl; // for(int i=0;i<8;i++) // cout<<t1[i].data<<" "; printleaves(r1); return 0; } |