12. 이진 트리의 구현 및 순회 - 이진트리 / 이진 트리의 순회 / 전위 순회 /중위 순회 / 후위 순회 / 이진 트리 구현하기

이진트리의 구현 및 순회

이진트리의 구현 방법과 순회의 개념에 대해서 이해한다. 이진 트리를 C언어로 구현하는 방법에 대해서 학습한다.

 

이진 트리

이진 트리는 부모가 왼쪽 자식, 오른쪽 자식을 가질 수 있다는 점에서, 포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능하다.

이진트리 구조체(노드) 만들기 / 초기화 함수

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

typedef struct Node{
    int data; //실제로는 이것보다 많은 양의 데이터가 들어가는 경우가 많다.
    struct Node *leftChild;
    struct Node *rightChild;
}Node;

//특정한 노드를 초기화하는 함수
Node* initNode(int data, Node* leftChild, Node* rightChild){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->leftChild = leftChild;
    node->rightChild = rightChild;
    return node; // 해당 노드의 포인터를 반환
} // 이진트리의 경우, 함수의 반환형에 특정 노드의 포인터가 들어가는 경우가 많다.

 

이진트리의 순회

이진 트리에 담긴 데이터를 하나씩 방문하는 방법은 대표적으로 3가지가 있다.

1. 전위 순회
2. 중위 순회
3. 후위 순회

 

이진트리의 전위 순회

1. 자기 자신을 출력한다.
2. 왼쪽 자식을 방문한다.
3. 오른쪽 자식을 방문한다.

이진트리의 전위 순회시 방문 순서 및 출력내용

전위 순회 함수 만들기

void preorder(Node* root){
    if(root){
        printf("%d ", root->data); //자기 자신부터 출력
        preorder(root->leftChild); //재귀적으로 왼쪽자식부터 방문
        preorder(root->rightChild);
    }
}

 

이진트리의 중위 순회

중위 순회의 결과는 가장 왼쪽에서 오른쪽으로 차례대로 출력하는 것과 동일하다.

1. 왼쪽 자식을 방문한다.
2. 자기 자신을 출력한다.
3. 오른쪽 자실을 방문한다.

중위 순회 함수 만들기

void inorder(Node* root){
    if(root){
        inorder(root->leftChild); //재귀적으로 왼쪽자식 방문
        printf("%d ", root->data); //자기자신 출력
        inorder(root->rightChild);
    }
}

 

이진 트리의 후위 순회

루트 노드가 가장 마지막에 출력되는게 특징이다.

1. 왼쪽 자식을 방문한다.
2. 오른쪽 자식을 방문한다.
3. 자기 자신을 출력한다.

 

후위순회 함수 만들기

void postorder(Node* root){
    if(root){
        postorder(root->leftChild); //재귀적으로 왼쪽 자식 방문
        postorder(root->rightChild); //재귀적으로 오른쪽 자식 방문
        printf("%d ", root->data); //자기 자신 출력
    }
}

 

이진트리 구현 및 사용하기

다음 그림과 같은 이진트리를 구현하고 사용해 본다.

구현할 이진 트리 도식

int main(void){
    Node* n7 = initNode(50, NULL, NULL); //리프노드들 부터 초기화
    Node* n6 = initNode(37, NULL, NULL);
    Node* n5 = initNode(23, NULL, NULL);
    Node* n4 = initNode(5, NULL, NULL);
    Node* n3 = initNode(48, n6, n7);
    Node* n2 = initNode(17, n4, n5);
    Node* n1 = initNode(30, n2, n3); //root노드
    preorder(n1); //전위 순회 결과 출력
    printf("\n");
    inorder(n1);
    printf("\n");
    postorder(n1);
    printf("\n");
    system("pause");
    return 0;
}

30 17 5 23 48 37 50
5 17 23 30 37 48 50
5 23 17 37 50 48 30

 

요약

1. 이진트리는 포인터를 이용해서 구현할 수 있다.
2. 이진 트리의 데이터를 방문하기 위해서 순회 알고리즘을 효과적으로 사용할 수 있다.