PTA A_1102 Invert a Binary Tree

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805365537882112

解：
二叉树的遍历

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<queue>
   
4. 
   
5. using namespace std;
   
6. 
   
7. typedef struct node{
   
8.     int lchild, rchild;
   
9. } BTNode;
   
10. 
    
11. int ttl;
    
12. 
    
13. void reverse_tree(int root, BTNode tree[])
    
14. {
    
15.     if (root == -1) return;
    
16. 
    
17.     reverse_tree(tree[root].lchild, tree);
    
18.     reverse_tree(tree[root].rchild, tree);
    
19.    
    
20.     int temp = tree[root].lchild;
    
21.     tree[root].lchild = tree[root].rchild;
    
22.     tree[root].rchild = temp;
    
23. }
    
24. 
    
25. void BFS(int root, BTNode tree[])
    
26. {
    
27.     queue<int> q;
    
28. 
    
29.     q.push(root);
    
30. 
    
31.     while (!q.empty())
    
32.     {
    
33.         int index = q.front();
    
34.         q.pop();
    
35. 
    
36.         printf("%d", index);
    
37.         if (--ttl) putchar(' ');
    
38. 
    
39.         if (tree[index].lchild != -1) q.push(tree[index].lchild);
    
40.         if (tree[index].rchild != -1) q.push(tree[index].rchild);
    
41.     }
    
42. 
    
43.     putchar('\n');
    
44. }
    
45. 
    
46. void print_inorder(int root, BTNode tree[])
    
47. {
    
48.     if (root == -1) return;
    
49. 
    
50.     print_inorder(tree[root].lchild, tree);
    
51.     printf("%d", root);
    
52.     if (--ttl) putchar(' ');
    
53.     print_inorder(tree[root].rchild, tree);
    
54. }
    
55. 
    
56. int main(void)
    
57. {
    
58.     int n, hash_table[15] = {0};
    
59.     BTNode tree[15];
    
60. 
    
61.     memset(tree, -1, sizeof(tree));
    
62.    
    
63.     scanf("%d", &n);
    
64.     if (!n) return 0;
    
65.     getchar();
    
66.     for (int i = 0; i < n; i++)
    
67.     {
    
68.         char s[5];
    
69. 
    
70.         fgets(s, 5, stdin);
    
71.         if (s[0] != '-') ++hash_table[tree[i].lchild = s[0] - '0'];
    
72.         if (s[2] != '-') ++hash_table[tree[i].rchild = s[2] - '0'];
    
73.     }
    
74. 
    
75.     for (int i = 0; i < n; i++)
    
76.         if (!hash_table[i])
    
77.         {
    
78.             reverse_tree(i, tree);
    
79.             ttl = n;
    
80.             BFS(i, tree);
    
81.             ttl = n;
    
82.             print_inorder(i, tree);
    
83.             break;
    
84.         }
    
85. 
    
86.     return 0;
    
87. }

复制代码