[자료구조] 이진트리(연결리스트), 전위순회, 중위순회, 후위순회 - C

이진트리 

이진트리는 완전 이진트리, 포화이진트리, 일반 이진트리 

 

 

 

위를 바탕으로 기본적인 코드를 작성해보겠다.

 

 

기본 코드

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

typedef struct _tree{
    struct _tree *left;
    int data;
    struct _tree *right;
} Tree;

void AddData(Tree **position, int value) {
    *position = (Tree *)malloc(sizeof(Tree)); 
    (*position)->data = value;
    (*position)->left = NULL;
    (*position)->right = NULL;
}

void initData(Tree **head) {
    AddData(head, 3); 

    AddData(&((*head)->left), 4); 
    AddData(&((*head)->left->left), 9);  

    AddData(&((*head)->left->right), 5); 

    AddData(&((*head)->right), 1); 
    AddData(&((*head)->right->left), 7); 

    AddData(&((*head)->right->left->right), 2); 
}



int main(void) {
    Tree *head = NULL; 

    initData(&head);

    return 0;
}

 

 

위 코드를 실행하면 아래와 같은 형태가 나온다.

 

 

 

이제 위 기본 형식에 대해서 전위 순회, 중위 순회, 후위 순회를 실행하는 코드를 작성해보겠다.

 

전위 순회

• VLR (View - Left - Right) : 조회, 왼쪽 요소, 오른쪽 요소 순으로 진행한다.
• 위 데이터로는 3 -> 4 -> 9 -> 5 -> 1 -> 7 -> 2 순서로 조회된다.

 

중위 순회

• LVR (Left - View - Right) : 왼쪽 요소, 조회, 오른쪽 요소 순으로 진행한다.
• 위 데이터로는 9 -> 4 -> 5 -> 3 -> 7 -> 2 -> 1 순서로 조회된다.

 

후위 순회

• LRV (Left - Right - View) : 왼쪽 요소, 오른쪽 요소, 조회 순으로 진행한다.
• 위 데이터로는 9 -> 5 -> 4 -> 2 -> 7 -> 1 -> 3 순서로 조회된다.

 

 

실행 코드

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

typedef struct _tree{
    struct _tree *left;
    int data;
    struct _tree *right;
} Tree;

void AddData(Tree **position, int value) {
    *position = (Tree *)malloc(sizeof(Tree)); 
    (*position)->data = value;
    (*position)->left = NULL;
    (*position)->right = NULL;
}

void initData(Tree **head) {
    AddData(head, 3); 

    AddData(&((*head)->left), 4); 
    AddData(&((*head)->left->left), 9);  

    AddData(&((*head)->left->right), 5); 

    AddData(&((*head)->right), 1); 
    AddData(&((*head)->right->left), 7); 

    AddData(&((*head)->right->left->right), 2); 
}

void preorder_traverser(Tree *head) {
    if (head != NULL) {
        printf("%d->", head->data);
        preorder_traverser(head->left);
        preorder_traverser(head->right);
    }
}

void inorder_traverser(Tree *head) {
    if (head != NULL) {
        inorder_traverser(head->left);
        printf("%d->", head->data);
        inorder_traverser(head->right);
    }
}

void postorder_traverser(Tree *head) {
    if (head != NULL) {
        postorder_traverser(head->left);
        postorder_traverser(head->right);
        printf("%d->", head->data);
    }
}

int main(void) {
    Tree *head = NULL; 

    initData(&head);

    printf("Preorder: ");
    preorder_traverser(head);
    printf("\n");

    printf("Inorder: ");
    inorder_traverser(head);
    printf("\n");

    printf("Postorder: ");
    postorder_traverser(head);
    printf("\n");

    return 0;
}

 

 

실행 결과