이진 트리 구현과 순회(Traversal)

※이 글은 나동빈님 강의를 보고 복습용으로 작성하는 글입니다.

https://blog.naver.com/ndb796/221233560789

19. 이진 트리의 구현과 순회(Traversal) 방식

 

---

이진 트리(Binary Tree)는 굉장히 많이 사용되는 비선형 자료구조입니다. 비선형이란 선, 즉 일렬로 구현되지 않았다는 뜻입니다. 또 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용되는 구조입니다. 이전 Heap Sort 에서도 다뤄 본 적이 있었습니다.

 

 

https://com24everyday.tistory.com/101

힙정렬

 

이번에는 좀 더 본격적으로 이진 트리에 대해 알아볼까요? 이진 트리는 자식 노드가 두개이하인 노드를 이야기 합니다. 트리의 구현을 제대로 하기 위해서는 포인터(Pointer)를 사용해야하는데요. 그 이유는 유연함을 위해서 입니다. 다음과 같은 트리가 있다고 생각해봅시다.

오른쪽 자식이 4개 입니다. 그러면 필요한 배열은 어떻게 될까요. 1,3,7,14 니깐 4개의 노드를 저장할 뿐인데 크기가 14인 배열이 필요한 겁니다. 

 

이진 트리는 다음과 같은 구조입니다. 하나의 노드는 모두 왼쪽 자식과 오른쪽 자식을 가질 수 있습니다.(물론 없어도 됩니다.) 근데 반드시 '포인터'를 사용해야할까요? 자식이 없어도 되기 때문입니다. 힙정렬때는 완전이진트리(자식이 두개인 트리) 였기 때문에 배열로 표현하기 쉬웠지만 이진트리는 배열로 표현하기 어려워졌습니다. 

 

 

그럼 이제 포인터를 사용해서 이진 트리를 구현해볼것인데 그전에 세가지의 이진 트리 데이터 탐색법에 관해 알아보겠습니다. 이 셋은 하나의 노드에 방문했을때의 동작을 뜻하는데 이 동작은 다 똑같고 순서만 다릅니다. 자기자신을 처리하는 순서에 따라 이름이 결정된다고 보시면 됩니다. 

 

① 전위 순회(Preorder Traversal)

 

(1) 먼저 자기 자신을 처리

(2) 왼쪽 자식 방문

(3) 오른쪽 자식 방문 

 

② 중위 순회(Inorder Traversal)

 

(1) 왼쪽 자식 방문

(2) 자기 자신을 처리

(3) 오른쪽 자식 방문 

 

③ 후위 순회(Postorder Traversal)

 

(1) 왼쪽 자식 방문

(2) 오른쪽 자식 방문 

(3) 자기 자신을 처리

 

 

 

 

그림을 보며 방문 순서를 보겠습니다.

재귀적으로 생각하면 생각하시기 쉽습니다. 한번 그려보며 진행순서를 판단해보시는게 좋습니다!

 

전위 순회 방문 순서를 보시면 다음과 같습니다. 

 

1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

 

 

중위 순회의 방문 순서는 다음과 같습니다.

 

8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 

 

후위 순회의 방문 순서는 다음과 같습니다. 

 

8 9 4 10 11 5 2 12 13 6 14  15 7 3 1

 

이해가 다 되셨을거 같습니다. 이제 C/C++ 구현을 해보겠습니다. 포인터로 구현했다는 점에서 완전 이진 트리가 아니어도 정상적으로 작동을 합니다. 

 

#include <iostream>

using namespace std;

int number = 15;

//하나의 노드 정보를 선언
typedef struct node* treePointer;
typedef struct node {
    int data;
    treePointer leftChild, rightChild;
}node;

//전위 순회 구현
void preorder(treePointer ptr) {
    if (ptr) {
        cout << ptr->data << ' '; // (1) 먼저 자기 자신을 처리
        preorder(ptr->leftChild); // (2) 왼쪽 자식 방문
        preorder(ptr->rightChild); //(3) 오른쪽 자식 방문
    }
}

//중위 순회 구현
void inorder(treePointer ptr) {
    if (ptr) {
        preorder(ptr->leftChild); //(1) 왼쪽 자식 방문
        cout << ptr->data << ' '; //(2) 자기 자신을 처리
        preorder(ptr->rightChild);//(3) 오른쪽 자식 방문
    }
}

//후위 순회 구현
void postorder(treePointer ptr) {
    if (ptr) {      
        preorder(ptr->leftChild); //(1) 왼쪽 자식 방문
        preorder(ptr->rightChild);//(2) 오른쪽 자식 방문
        cout << ptr->data << ' '; //(3) 자기 자신을 처리
    }
}
int main()
{
    node nodes[16];

    //노드 생성
    for (int i = 0; i <= number; i++) {
        nodes[i].data = i;
        nodes[i].leftChild = NULL;
        nodes[i].rightChild = NULL;
    }

    //노드 연결
    for (int i = 1; i <= number; i++) {
        if (i % 2 == 0) {
            nodes[i / 2].leftChild = &nodes[i]; //짝수면 왼쪽 자식이 됨
        }
        else {
            nodes[i / 2].rightChild = &nodes[i]; //홀수면 오른쪽 자식이 됨
        }
    }

    //전위 진행
    printf("전위순회 방문 순서: ");
    preorder(&nodes[1]);
    printf("\n");
    printf("중위순회 방문 순서: ");
    inorder(&nodes[1]);
    printf("\n");
    printf("후위순회 방문 순서: ");
    postorder(&nodes[1]);
}

 

이렇게 이진트리 구현과 순회를 배워보았습니다. 수고하셨습니다.