pat 1020

1020.c

#include <stdlib.h>
#include <stdio.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} node_t;

typedef struct queue {
    int *data;
    int first;
    int count;
    int size;
} queue_t;

void init_queue(queue_t *q, int size) {
    q->data = malloc(size * sizeof(int));
    q->first = 0;
    q->count = 0;
    q->size = size;
}

void enqueue(queue_t *q, int num) {
    int pos = (q->first + q->count) % q->size;
    q->data[pos] = num;
    q->count++;
}

int dequeue(queue_t *q) {
    int ret = q->data[q->first];
    q->first = (q->first + 1) % q->size;
    q->count--;
    return ret;
}

int is_empty_queue(queue_t *q) {
    return q->count == 0;
}

void destory_queue(queue_t *q) {
    if (q->data) {
        free(q->data);
    }
}


void build_tree(node_t *nodes, int *postorder, int *inorder, int p_start, int i_start, int length ){
    node_t *node = &nodes[postorder[p_start + length - 1]];
    node->data = postorder[p_start +length - 1 ];
    int i = 0;
    int left_length = 0;
    int right_length = 0;
    for (i = i_start; i < i_start + length; i++){
        if (inorder[i] == postorder[p_start + length - 1] ){
            left_length = i - i_start;
            break;
        }
    }
    if (left_length == 0) {
        node->left = NULL;
    } else {
        node->left = &nodes[postorder[p_start + left_length - 1]];
        build_tree( nodes, postorder, inorder, p_start, i_start, left_length );
    }
    right_length = length - left_length - 1;
    if (right_length == 0) {
        node->right = NULL;
    } else {
        node->right = &nodes[postorder[p_start + length - 2]];
        build_tree( nodes, postorder, inorder, p_start + left_length, i_start+left_length + 1, right_length );
    }
}

void print_tree(node_t *nodes, int root, int *list, int length) {
    queue_t q;
    init_queue(&q, length);
    enqueue(&q, root);
    int *p = list;
    while (!is_empty_queue(&q)) {
        int node = dequeue(&q);
        *p++ = nodes[node].data;
        if (nodes[node].left) {
            enqueue(&q, nodes[node].left->data);
        }
        if (nodes[node].right) {
            enqueue(&q, nodes[node].right->data);
        }
    }
    destory_queue(&q);

    int i;
    for (i = 0; i < length - 1; i++) {
        printf("%d ", list[i]);
    }
    printf("%d", list[length-1]);
}

node_t nodes[50];
int postorder[50];
int inorder[50];
int list[50];

int main(){
    int length;
    scanf("%d", &length );
    int i;
    for (i = 0; i < length; i++) {
        scanf("%d", &postorder[i]);
    }
    for(i = 0; i < length; i++) {
        scanf("%d", &inorder[i]);
    }

    build_tree(nodes, postorder, inorder, 0, 0, length);
    print_tree(nodes, postorder[length-1], list, length);

    return 0;
}