레벨오더,인오더로 부터 이진나무 만들기

레벨오더,인오더로 부터 이진나무 만들기

#include <stdio.h>

#include <stdlib.h>

typedef struct _node *pnode;

typedef struct _node {

    int data;

    pnode  left;

    pnode  right;

} node;

void preorder(pnode);

void postorder(pnode);

void inorder(pnode);

// 새노드 만들기 자료는 n으로 주어진다.

pnode makeNode(int n) {

    pnode t=(pnode)malloc(sizeof(node));

    t->data=n;

    t->left=NULL;

    t->right=NULL;

    return t;

}

// 구간 low와 high 중에서 가장 레벨오더에서 먼저오는 노드가 들어 있는

// 인오더 운행상의 인덱스를 구한다. 이 인덱스가 구간을 분할하여

// 왼쪽나무와 오른쪽나무를 만들게 된다.

int find(int loi[], int low, int high) {

    int i, x;

    if(low>high) { return -1; }

    x=low;

    for(i=low+1;i<=high;i+=1) {

        if(loi[i]<loi[x]) { x=i; }

    }

    return x;

}

// level order와 inorder 순서가 주어진다.

// loi는 inorder로 주어진 노드들의 레벨오더에 나타낸는 순서를 나타낸다.

// low와 high구간 중에서 가장 loi의 값이 낮은 인덱스가 현재 구간의 루트가 되고

// 왼쪽은 왼쪽부나무, 오른쪾은 오른쪽부나무가 된다.

pnode insertNode(int lo[], int loi[], int io[], int low, int high) {

    pnode t, l, r;

    int i, j, pos;

    if(low>high) { return NULL; }

    // low, high 구간에서 lo[x]노드의 위치를 찾는다.

    // low와 high구간에서 가장 loi가 작은 인덱스를 구한다. pos이라고 한다.

    pos=find(loi, low, high);

    //printf("low=%d high=%d pos=%d ", low, high, pos); getchar();

    

    // 왼쪽구간 에서 인덱스를 구하여 i라고 한다.

    i=find(loi, low, pos-1);

    if(i<0) { 

        l=NULL; 

    } else { // 왼쪽부나무를 만들어서 l에 준다.

        l=insertNode(lo, loi, io, low, pos-1);

    }

    // pos에 들어 있는 자료로 노드를 만들어 현재 구간의 루트로 삼는다.

    t=makeNode(io[pos]);

    // 오른쪽구간에서 인덱스를 구하여 j라고 한다.

    j=find(loi, pos+1, high);

    if(j<0) {

        r=NULL;

    } else { // 오른쪽 부나무를 만들어서 r에 준다.

        r=insertNode(lo, loi, io, pos+1, high);

    } 

    t->left=l;     // t의 왼쪽부나무

    t->right=r;  // t의 오른쪽 부나무

    return t;     // t를 반환한다.

}

void preorder(pnode t) {

    if(t==NULL) { return; }

    printf("%d ", t->data);

    preorder(t->left);

    preorder(t->right);

}

void postorder(pnode t) {

    if(t==NULL) { return; }

    postorder(t->left);

    postorder(t->right);

    printf("%d ", t->data);

}

void inorder(pnode t) {

    if(t==NULL) { return; }

    inorder(t->left);

    printf("%d ", t->data);

    inorder(t->right);

}

int main() {

    pnode root;

    int ino[32]={0,};

    int lvo[32]={0,};

    int loi[32]={0,};

    int i, j, n, x;

    printf("노드갯수: ");

    scanf("%d", &n);

    for(i=0;i<n;i+=1) {

        scanf("%d", &lvo[i]);

    }

    for(i=0;i<n;i+=1) {

        scanf("%d", &ino[i]);

    }

    for(i=0;i<n;i+=1) {

        for(j=0;j<n;j+=1) {

            if(lvo[i]==ino[j]) {

                loi[j]=i;

            }

        }

    }

    // 전체구간을 잡아서 노드를 만들어서 root에 준다.

    // root는 이진나무의 루트노드를 가리키고 있다.

    root=insertNode(lvo, loi, ino, 0, n-1);

    // preorder운행을 해본다.

    printf("preorder: ");

    preorder(root);

    printf("\n");

    // postorder운행을 해본다.

    printf("postorder: ");

    postorder(root);            

    printf("\n");

    // inorder운행을 해본다. 입력한 inorder운행과 결과가 같이 나오는 것을 확인할 수 있다.

    printf("inorder: ");

    inorder(root);            

    printf("\n");

    return 0;

}