[알고리즘] 이진트리와 순회(Inorder, Preorder, Postorder)

트리는 계층적인 구조를 표현하는 자료 구조로, 가장 상위 노드인 루트 노드와 나머지 내부 노드, 그리고 가장 끝의 자식이 없는 리프 노드로 구성된다.

이진 트리란 각 노드가 최대 2개의 자식을 갖는 트리이다. 이진 트리는 배열로 구현할 수도 있으나 연결 리스트로 구현하면 편리하게 관리할 수 있다.

(부모노드의 주소는 필요시에만 저장하고 보통은 생략된다.)

struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}

이진 트리의 순회

---

트리는 각각의 부분 트리들이 부모-자식 관계를 가지는 특별한 자료 구조를 가지고 있기 때문에 단순히 배열 인덱스를 따라 순회하는 것으로는 트리에 저장하여 자료들을 사용하는 데에 있어 이점을 제대로 활용할 수 없다.

이진 트리의 순회는 어떤 순회 방식을 사용하느냐에 따라 Inorder, Preorder, Postorder로 나뉜다.

1. Inorder (중위순회)

트리를 세 부분으로 나누었을 때 왼쪽 자식노드 -> 부모노드 -> 오른쪽 자식노드 순으로 방문한다.

void Inorder(struct node* node)
{
    if (node == NULL)
        return;
    Inorder(node->left); // 왼쪽 트리 순회
    printf("%d ", node->data); // 루트 방문
    Inorder(node->right); // 오른쪽 트리 순회
}

정렬되지 않은 원소들을 BST(왼쪽 노드의 값이 오른쪽 노드보다 작은 이진 탐색 트리)로 구현한 후 중위순회하면 오름차순으로 정렬할 수 있다. 이때 시간복잡도는 $O(nlog n)$을 갖는다.

2. Preorder (전위순회)

부모노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드 순으로 방문한다.

void Preorder(struct node* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data); 
    Preorder(node->left); 
    Preorder(node->right); 
}

3. Postorder (후위순회)

왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모노드 순으로 방문한다.

void Postorder(struct node* node)
{
    if (node == NULL)
        return;
    Postorder(node->left); 
    Postorder(node->right); 
    printf("%d ", node->data); 
}

참고자료
Tree Traversal Techniques – Data Structure and Algorithm Tutorials
트리와 이진트리 / https://youtu.be/TdakkF5Xh6o