BinaryTree

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

기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리이다. 이진 트리는 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도를 빠르게 하기 위해 사용하는 구조이다.

힙정렬에서는 완전 이진 트리를 사용했기 때문에 트리를 배열로 구현할 수 있었지만, 실제로 불규칙한 트리를 제대로 구현하기 위해서는 포인터를 사용해야한다. 포인터를 이용해 특정한 루트에서 자식노드로 접근할 수 있기 때문이다.

포인터를 사용하는 이유는 자원 낭비를 막기 위함이다.

이진 트리에서 데이터를 순회하는 방법은 크게 세가지가 있다.

1. 전위 순회

   : 자기 자신 -> 왼쪽 자식 -> 오른쪽 자식

2. 중위 순회

   : 왼쪽 자식 -> 자기 자신 -> 오른쪽 자식

3. 후위 순회 (컴퓨터가 이해하기 좋은 방식)

   : 왼쪽 자식 -> 오른쪽 자식 -> 자기 자신

Source Code

#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 << ' ';
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}

//중위순회
void inorder(treePointer ptr) {
    if(ptr) {
        preorder(ptr->leftChild);
        cout << ptr->data << ' ';
        preorder(ptr->rightChild);
    }
}

//후위순회
void postorder(treePointer ptr) {
    if(ptr) {
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
        cout << ptr->data << ' ';
    }
}