C)전위(preorder), 중위(inorder), 후위(postorder)순회 트리 구현

사용자로부터 5개의 숫자를 차례대로 입력받아 트리를 생성한다. (5개의 숫자는 postorder 순으로 입력)

가령, 9, 11, 5, 7, 3 이 입력된 경우, 아래와 같은 구조의 트리를 만든다.

              3

            /  \

          5      7

        /  \

     9      11

각 노드를 만들어 연결하기 위해 다음과 같은 makeNode() 함수를 이용한다.

makeNode() 함수의 인자와 반환 값은 다음과 같다.

TreeNode * makeNode(int data, TreeNode *left, TreeNode *right)

data: 노드에 저장될 데이터 (정수)

left: 왼쪽 자식 노드의 주소

right: 오른쪽 자식 노드의 주소

반환값: 생성된 노드의 주소

​

생성된 트리의 preorder, inorder, postorder 순회 결과를 차례대로 출력한다.

<입출력 예>

9 11 5 7 3

3 5 9 11 7

9 5 11 3 7

9 11 5 7 3

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
    int data;
    struct TreeNode *left,*right;
}TreeNode;

// 노드 생성 함수 (인자: 데이터, 왼쪽 자식 주소, 오른쪽 자식 주소)
// 반환값: 생성된 노드의 주소
TreeNode * makeNode(int data, TreeNode *left, TreeNode *right)
{
    TreeNode *p;
    p = (TreeNode *) malloc(sizeof(TreeNode));
    p->data = data;
    p->left = left;
    p->right = right;
    return p;
}

void preorder(TreeNode *p)
{
    if(p!=NULL)
    {
        printf("%d ",p->data);
        preorder(p->left);
        preorder(p->right);
    }
}
void inorder(TreeNode *p)
{
    if(p!=NULL)
    {
        inorder(p->left);
        printf("%d ",p->data);
        inorder(p->right);
    }
}
void postorder(TreeNode *p)
{
    if(p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        printf("%d ",p->data);
    }
}

int main()
{
    TreeNode    *n1, *n2, *n3, *n4, *n5; //직접 노드 하나씩 입력받아 넣어주었습니다.
    int         data;

    // 정수를 하나씩 입력 받을 때마다 노드를 생성하여 트리 구성
    // makeNode() 함수 이용
 
    scanf("%d",&data);
    n4 = makeNode(data,NULL,NULL);
    scanf("%d",&data);
    n5 = makeNode(data,NULL,NULL);
    scanf("%d",&data);
    n2 = makeNode(data,n4,n5);
    scanf("%d",&data);
    n3 = makeNode(data,NULL,NULL);
    scanf("%d",&data);
    n1 = makeNode(data,n2,n3);

    // preorder
    preorder(n1);
    printf("\n");

    // inorder
    inorder(n1);
    printf("\n");
    // postorder
    postorder(n1);
    printf("\n");
}