[OJ]1005:Binary Search Tree analog

2019-1-11 写技术

Input

The first integer of the input is T, the number of test cases. Each test case has two lines. The first line contain an integer N,(1<=N<=1000), the number of numbers need to be inserted into the BST. The second line contain N integers separated by space, each integer is in the range of [0,230].


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

typedef struct _Node{
        int data;
        struct _Node *left;
        struct _Node *right;
}Node;



void insert(Node *T, int x){
        Node *p = T;
        Node *f = T;
        while(p != NULL){
                f = p;
                if(x<p->data){
                        p = p->left;
                }else{
                        p = p->right;
                }
        }
        p = malloc(sizeof(Node));
        p->data = x;
        p->left = p->right = NULL;
        if(x<f->data){
                f->left = p;
        }else{
                f->right = p;
        }
}

void pre_order(Node *T){
        if(T == NULL){
                return;
        }
        printf("%d ", T->data);
        pre_order(T->left);
        pre_order(T->right);
}

void in_order(Node *T){
        if(T == NULL){
                return;
        }
        in_order(T->left);
        printf("%d ", T->data);
        in_order(T->right);
}

void post_order(Node *T){
        if(T == NULL){
                return;
        }
        post_order(T->left);
        free(T->left);
        T->left = NULL;
        post_order(T->right);
        free(T->right);
        T->right = NULL;
        printf("%d ", T->data);
}

void main(){
        int t, vertices, vertex;
        Node *T=NULL;

        scanf(" %d", &t);
        while(t--){
                scanf(" %d", &vertices);
                while(vertices--){
                        scanf(" %d", &vertex);
                        if(T == NULL){
                                T = malloc(sizeof(Node));
                                T->data = vertex;
                                T->left = NULL;
                                T->right = NULL;
                        }else{
                                insert(T, vertex);
                        }
                }
                pre_order(T);
                printf("\n");
                in_order(T);
                printf("\n");
                post_order(T);
                printf("\n");
                free(T);
                T = NULL;
        }
}

标签: C

发表评论:

Powered by anycle 湘ICP备15001973号