[BOJ/백준] 1991 트리 순회

● [문제번호 1991] 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

● 알아야 할 것

: 트리

: 재귀

: 전위 순회 (preOrder)

: 중위 순회 (inOrder)

: 후위 순회 (postOrder)

 

● 풀이 과정

: 왼쪽 자식 배열, 오른쪽 자식 배열 과

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

 

● 주의 할 것

: NULL

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// lc : 부모노드(index) 의 왼쪽 자식(값)
// rc : 부모노드(index) 의 오른쪽 자식(값)
char lc[27], rc[27];
int N;

// 문자를 index로 변경
int index(char node)
{
   return node - 'A'; 
}

// 전위 순회
void preOrder(char p)
{
    if(p != '.')
        cout << p;
    
    if(lc[index(p)] != '.')
        preOrder(lc[index(p)]);
    
    if(rc[index(p)] != '.')
        preOrder(rc[index(p)]);
}

// 중위 순회
void inOrder(char p)
{
    if(lc[index(p)] != '.')
        inOrder(lc[index(p)]);
    
    if(p != '.')
        cout << p;
    
    if(rc[index(p)] != '.')
        inOrder(rc[index(p)]);
}

// 후위 순회
void postOrder(char p)
{
    if(lc[index(p)] != '.')
        postOrder(lc[index(p)]);
    
    if(rc[index(p)] != '.')
        postOrder(rc[index(p)]);
    
    if(p != '.')
        cout << p;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 트리 생성
    for(int n = 0; n < N; n++)
    {
        char p, l, r;
        cin >> p >> l >> r;
        
        lc[index(p)] = l;
        rc[index(p)] = r;
    }
    
    preOrder('A');
    cout << "\n";
    
    inOrder('A');
    cout << "\n";
    
    postOrder('A');
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [620 - 트리 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1991	트리 순회	https://pirateturtle.tistory.com/288
2	2250	트리의 높이와 너비	https://pirateturtle.tistory.com/289
3	11725	트리의 부모 찾기	https://pirateturtle.tistory.com/290
4	1167	트리의 지름	https://pirateturtle.tistory.com/291
5	1967	트리의 지름	https://pirateturtle.tistory.com/292