[자료구조] 이진 트리와 4가지 순회 방법

이진 트리의 자식 표현 방법

이진 트리는 트리와 달리 자식의 Left, Right에 대한 정보가 반드시 필요하다. 따라서 일반적인 그래프로 구현하기 힘들다.

 

배열, 구조체, 연결리스트 등으로 표현가능하지만 트리의 구조를 이용하여 배열로 간단하게 나타낼 수 있다.

 

이진 트리의 4가지 순회 방법

1. 레벨 순회(Lever Travel)

Level Travel은 트리이 깊이를 순차적으로 탐색한다. 방문 순서는 cur → Left Child → Right Child이다.

레벨 순회는 BFS와 유사한 구조를 가진다. 구현은 일반적인 BFS처럼 해주면 된다. 이를 코드로 구현하면 다음과 같다.

void levelTravel(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << " ";
        if(lc[cur]) q.push(lc[cur]);
        if(rc[cur]) q.push(rc[cur]);
    }
}

 

 

 

2. 전위순회(Preorder Travel)

Preorder Travel은 트리의 왼쪽 자식을 모두 방문한 후 오른쪽 자식을 방문한다.

방문 순서는 cur → Left Child → Right Child이다.

전위 순회는 DFS와 같은 구조를 가진다. 

일반적으로 재귀로 구현하는게 편하지만 레벨 순회에서 queue대신 stack을 사용하면 stack의 구조를 이용하여 iterator을 이용한 반복문으로 구현이 가능하다.

 

[재귀로 구현한 Preorder Travel]

void preorder(int cur){
    cout << cur << " ";
    if(lc[cur]) preorder(lc[cur]);
    if(rc[cur]) preorder(rc[cur]);

}

[iterator로 구현한 Preorder Travel]

void preorder_iterator() {
    stack<int> s;
    s.push(1);
    while(!s.empty()) {
        int cur = s.top();
        s.pop();
        cout << cur << " ";
        if(rc[cur]) s.push(rc[cur]);
        if(lc[cur]) s.push(lc[cur]);
    }
}

 

재귀를 이용한 구현이 깔끔하고 가독성이 좋지만 iterator을 이용한 구현이 더 빠르다. 하지만 스택 메모리가 1MB로 제한되어 있을 때에는 이터레이터를 이용해야 한다. 이상을 정리하면 다음과 같다.

	장점	단점
재귀	코드의 가독성이 좋다.	매번 함수를 호출하여 속도가 느리다.
이터레이터	함수를 호출하지 않아 속도가 빠르다.	코드의 길이가 길어진다.

 

 

3. 중위순회(Inorder Travel)

Inorder Travel은 트리의 왼쪽 자식을 방문한 후 현재 node를 방문하고 마지막으로 오른쪽 자식을 방문한다.

방문 순서는 Left Child → cur → Right Child이다.

다음과 같이 재귀를 이용하여 간단하게 구현할 수 있다.

 

void inorder(int cur){
    if(lc[cur]) inorder(lc[cur]);
    cout << cur << " ";
    if(rc[cur]) inorder(rc[cur]);
}

 

 

이진 탐색 트리의 경우 중위 순회로 탐색할 경우 자동으로 크기순으로 탐색한다.

 

 

 

 

4. 후위순회(Postorder Travel)

Postorder Travel은 트리의 왼쪽 자식을 먼저 방문한 후 오른쪽 자식을 방문하고 마지막으로 현재 node를 방문한다.

방문 순서는 Left Child → Right Child → cur  이다.

다음과 같이 재귀를 이용하여 간단하게 구현할 수 있다.

 

void postorder(int cur){
    if(lc[cur]) postorder(lc[cur]);
    if(rc[cur]) postorder(rc[cur]);
    cout << cur << " ";
}