PTA A_1102 Invert a Binary Tree

798236606

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

解：
二叉树的遍历

#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

typedef struct node{
    int lchild, rchild;
} BTNode;

int ttl;

void reverse_tree(int root, BTNode tree[])
{
    if (root == -1) return;

    reverse_tree(tree[root].lchild, tree);
    reverse_tree(tree[root].rchild, tree);
    
    int temp = tree[root].lchild;
    tree[root].lchild = tree[root].rchild;
    tree[root].rchild = temp;
}

void BFS(int root, BTNode tree[])
{
    queue<int> q;

    q.push(root);

    while (!q.empty())
    {
        int index = q.front();
        q.pop();

        printf("%d", index);
        if (--ttl) putchar(' ');

        if (tree[index].lchild != -1) q.push(tree[index].lchild);
        if (tree[index].rchild != -1) q.push(tree[index].rchild);
    }

    putchar('\n');
}

void print_inorder(int root, BTNode tree[])
{
    if (root == -1) return;

    print_inorder(tree[root].lchild, tree);
    printf("%d", root);
    if (--ttl) putchar(' ');
    print_inorder(tree[root].rchild, tree);
}

int main(void)
{
    int n, hash_table[15] = {0};
    BTNode tree[15];

    memset(tree, -1, sizeof(tree));
    
    scanf("%d", &n);
    if (!n) return 0;
    getchar();
    for (int i = 0; i < n; i++)
    {
        char s[5];

        fgets(s, 5, stdin);
        if (s[0] != '-') ++hash_table[tree[i].lchild = s[0] - '0'];
        if (s[2] != '-') ++hash_table[tree[i].rchild = s[2] - '0'];
    }

    for (int i = 0; i < n; i++)
        if (!hash_table[i])
        {
            reverse_tree(i, tree);
            ttl = n;
            BFS(i, tree);
            ttl = n;
            print_inorder(i, tree);
            break;
        }

    return 0;
}