[알고리즘] 이진 트리 탐색

이진 트리 탐색 C++

이진 트리에서의 전위 순회, 중위 순회, 후위 순회를 알아봅시다.

이진 트리

• 트리 구조이므로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다.
• 또한 사이클 역시 존재할 수 없다.
• 각각의 노드가 최대 두 개의 자식 노드를 가지고 있음
• 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 칭한다.
• 전위 순회, 중위 순회, 후위 순회의 탐색을 가지고 있다.
• 최상위 루트 노드를 가지고 있다.

전위 순회

전위 순회의 진행은 깊이 우선 순회라고도 하며, 다음의 세 가지 순서로 진행된다.

• 부모 노드를 방문한다.
• 왼쪽 자식 노드를 방문한다.
• 오른쪽 자식 노드를 방문한다.

즉, 부모 노드가 1, 왼쪽 자식 노드가 2, 오른쪽 자식 노드가 3이라면 1 -> 2 -> 3의 순으로 방문한다.

중위 순회

중위 순회는 다음의 세 가지 순서로 진행된다.

• 왼쪽 자식 노드를 방문한다.
• 부모 노드를 방문한다.
• 오른쪽 자식 노드를 방문한다.

즉, 부모 노드가 1, 왼쪽 자식 노드가 2, 오른쪽 자식 노드가 3이라면 2 -> 1 -> 3의 순으로 방문한다.

후위순회

후위 순회는 다음의 세 가지 순서로 진행된다.

• 왼쪽 자식 노드를 방문한다.
• 오른쪽 자식 노드를 방문한다.
• 부모 노드를 방문한다.

즉, 부모 노드가 1, 왼쪽 자식 노드가 2, 오른쪽 자식 노드가 3이라면 2 -> 3 -> 1의 순으로 방문한다.

구현(C++)

재귀를 통해 구현할 수 있다.


전위 순회는 preOrderFunc, 중위 순회는 inOrderFunc, 후위 순회는 postOrderFunc이라는 함수를 만들어 구현해봅시다.

이진 트리는 부모 노드 번호가 n이라면 왼쪽 자식 노드는 n2, 오른쪽 노드는 n2+1로 구현할 수 있습니다.

레벨 N을 입력해 주면 level이 N인 완전 이진 트리를 만들고, 각 순회를 해주는 소스를 만들어봅시다.

#include <iostream>
#include <vector>
using namespace std;
int N;
void preOrderFunc(int idx, int level) {
    if (level > N) return;
    cout << idx << ' ';
    preOrderFunc(idx * 2, level + 1);
    preOrderFunc(idx * 2+1, level + 1);
}
void inOrderFunc(int idx, int level) {
    if (level > N) return;
    inOrderFunc(idx * 2, level + 1);
    cout << idx << ' ';
    inOrderFunc(idx * 2 + 1, level + 1);
}
void postOrderFunc(int idx, int level) {
    if (level > N) return;
    postOrderFunc(idx * 2, level + 1);
    postOrderFunc(idx * 2 + 1, level + 1);
    cout << idx << ' ';
}
int main(void) {
    cin >> N;
    cout << "전위 순회 : ";
    preOrderFunc(1,1); 
    cout << '\n';
    cout << "중위 순회 : ";
    inOrderFunc(1,1);
    cout << '\n';
    cout << "후위 순회 : ";
    postOrderFunc(1,1);
    cout << '\n';
    return 0;
}

전위 순회는 자식 노드를 순회하기 전에 인덱스 값을 출력

중위 순회는 왼쪽 자식 노드를 순회한 뒤에 인덱스 값을 출력

후위 순회는 왼쪽 자식 노드, 오른쪽 자식 노드를 순회한 뒤에 인덱스 값을 출력하여 만들었습니다.

3을 입력해봅시다.

3
전위 순회 : 1 2 4 5 3 6 7
중위 순회 : 4 2 5 1 6 3 7
후위 순회 : 4 5 2 6 7 3 1

순회에 맞는 결과가 출력됩니다.