[Algorithm] 이진트리의 구현과 순회 알고리즘

이진트리란?

가장 많이 사용되는 비선형 자료구조는 이진트리이다. (<-> 선형 자료구조는 배열, 스택, 큐 등이다.)

이진트리는 데이터의 탐색 속도를 빠르게 하기 위해 사용한다.

한 번 탐색 할 때마다, 반씩 탐색할 데이터가 줄어들기 때문에 트리의 높이는 logN이 된다.

완전 이진 트리는 그냥 구현할 수 있지만, 보통 이진트리를 구현할 때는 포인터를 사용하여 구현한다.

탐색방법

이진 트리에서 데이터를 탐색하는 방법은 크게 3가지가 존재한다.

전위 순회(Preorder Traversal)

1. 자기 자신을 처리
2. 왼쪽 자식 방문
3. 오른쪽 자식 방문

중위 순회(Inorder Traversal)

1. 왼쪽 자식 방문
2. 자기 자신 처리
3. 오른쪽 자식 방문

후위 순회(Postorder Traversal)

1. 왼쪽 자식 방문
2. 오른쪽 자식 방문
3. 자기 자신 처리

구현

#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) { // 해당 포인터가 null값이 아니라면
        cout << ptr->data << ' ';
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}

// 중위 순회(왼쪽 -> 자기자신 -> 오른쪽)
void inorder(treePointer ptr) {
    if(ptr) { // 해당 포인터가 null값이 아니라면
        inorder(ptr->leftChild);
        cout << ptr->data << ' ';
        inorder(ptr->rightChild);
    }
}

// 후위 순회(왼쪽 -> 오른쪽 -> 자기자신)
void postorder(treePointer ptr) {
    if(ptr) { // 해당 포인터가 null값이 아니라면
        postorder(ptr->leftChild);
        postorder(ptr->rightChild);
        cout << ptr->data << ' ';
    }
}

int main(void) {
    node nodes[number+1]; // 15개의 데이터가 담길 수 있는 배열 

    for(int i=1;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) { // i가 2의 배수이면, 
            nodes[i/2].leftChild = &nodes[i];
        } else {
            nodes[i/2].rightChild = &nodes[i];
        }
    }

    preorder(&nodes[1]);
    cout << endl;
    inorder(&nodes[1]);
    cout << endl;
    postorder(&nodes[1]);

    return 0;
}

reference: https://www.youtube.com/watch?v=z_tzHoPfllA&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=20