[백준 1991번/c++] 트리 순회

알고리즘

 

• 트리
• 재귀

---

전위/중위/후위 순회

이진트리를 순회하는 방법에는 전위, 중위, 후위 3가지 방법이 있다.

 

이진트리에서 보면 전체 트리나 서브 트리나 그 구조는 완전히 동일하다.

-> 따라서 전체 트리 순회에 사용된 알고리즘은 똑같이 서브 트리에 적용할 수 있는 것이다.

 

다만 문제의 크기가 작아진다.

문제의 구조는 같고 크기만 작아지는 경우라면 순환을 적용할 수 있으므로 전체 순회에 사용된 알고리즘을 다시 서브트리에 적용하는 것이 가능해진다.

 

전위 순회

1. 루트노드 방문
2. 왼쪽 서브트리의 모든 노드 방문
3. 오른쪽 서브트리의 모든 노드 방문

중위 순회

1. 왼쪽 서브트리의 모든 노드 방문
2. 루트노드 방문
3. 오른쪽 서브트리의 모든 노드 방문

후위 순회

1. 왼쪽 서브트리의 모든 노드 방문
2. 오른쪽 서브트리의 모든 노드 방문
3. 루트노드 방문

---

성공 코드

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

pair<int, int> edge[26];

// 중위 순회 
void inorder(char rt){
    if(rt == '.') return;
    inorder(edge[rt-'A'].first);
    printf("%c", rt);
    inorder(edge[rt-'A'].second);
}

// 전위 순회 
void preorder(char rt){
    if(rt == '.') return;
    printf("%c", rt);
    preorder(edge[rt-'A'].first);
    preorder(edge[rt-'A'].second);
}

// 후위 순회 
void postorder(char rt){
    if(rt == '.') return;
    postorder(edge[rt-'A'].first);
    postorder(edge[rt-'A'].second);
    printf("%c", rt);
}

int main(){
    // freopen("input.txt", "rt", stdin);
    int n, i;
    char rt, ln, rn;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf(" %c %c %c", &rt, &ln, &rn);
        edge[rt-'A']={ln, rn};
    }
    preorder('A');
    printf("\n");
    inorder('A');
    printf("\n");
    postorder('A');
    printf("\n");

    return 0;
}

 

---

참고
C언어로 쉽게 풀어 쓴 자료구조