이진 트리의 구현과 순회(traversal)방식

이진 트리의 구현과 순회 방식

이진 트리는 데이터의 탐색 속도 향상을 위해 사용하는 구조로, 배열로도 표현할 수 있지만 이 경우에는 메모리 낭비가 있을 수 있어 주로 포인터를 사용해 트리를 구현한다.

이진 트리에는 완전 이진 트리가 있는데, 완전 이진 트리란 왼쪽 자식 오른쪽 자식 두개 다 꽉꽉 채우며 트리를 구성하는 것으로 생각하면 될 것 같다.

 

그럼 이제 트리 순회에 대해 알아보도록 하자. 트리 순회 방식에는 크게 3가지가 있다.

 

1. 전위 순회(Preorder Traversal)

① 자기 자신을 처리

② 왼쪽 자식 방문

③ 오른쪽 자식 방문

 

전위 순회를 이해하기 쉽게 그림으로 나타내면 다음과 같다.

 

2. 중위 순회(Inorder Traversal)

① 왼쪽 자식 방문

② 자기 자신을 처리

③ 오른쪽 자식 방문

 

중위 순회를 이해하기 쉽게 그림으로 나타내면 다음과 같다.

 

3. 후위 순회(Postorder Traversal)

① 왼쪽 자식 방문

② 오른쪽 자식 방문

③ 자기 자신을 처리

 

후위 순회를 이해하기 쉽게 그림으로 나타내면 다음과 같다.

 

아래는 포인터를 이용해 구현한 이진 트리와 세가지 트리 순회 방식의 코드이다.

 

#include <iostream>
 
using namespace std;
 
const int number = 15;
 
// 하나의 노드 정보를 선언
typedef struct node* treePointer;
typedef struct node {
    int data;
    treePointer left, right;
} node;
 
//전위순회
void preorder(treePointer ptr) {
    if (ptr) {
        cout << ptr->data << ' ';
        preorder(ptr->left);
        preorder(ptr->right);
    }
}
 
// 중위 순회
void inorder(treePointer ptr) {
    if (ptr) {
        inorder(ptr->left);
        cout << ptr->data << ' ';
        inorder(ptr->right);
    }
}
 
// 후위 순회
void postorder(treePointer ptr) {
    if (ptr) {
        postorder(ptr->left);
        postorder(ptr->right);
        cout << ptr->data << ' ';
    }
}
 
int main() {
    node nodes[number + 1];
    for (int i = 1; i <= number; i++) {
        nodes[i].data = i;
        nodes[i].left = NULL;
        nodes[i].right = NULL;
    }
 
    for (int i = 1; i <= number;i++) {
        if (i % 2 == 0)
            nodes[i / 2].left = &nodes[i];
        else
            nodes[i / 2].right = &nodes[i];
    }
 
    preorder(&nodes[1]);
    printf("\n");
    inorder(&nodes[1]);
    printf("\n");
    postorder(&nodes[1]);
    return 0;
}

 

추가로, 코드 상에서 트리를 만드는 방식은 먼저 1부터 15까지의 노드를 생성하고 숫자가 짝수이면 왼쪽, 홀수이면 오른쪽에 붙이는 방식이다.