[백준/boj] 1991번: 트리 순회 | C++

요약 : c++로 이진 트리, 트리 순회 구현하기(재귀 구조 활용)
 
알고리즘 설계 수업에서 이진트리 순회(전위 순회, 중위 순회, 후위 순회)를 구현하는 실습문제가 주어졌다!
근데 못풀었다! (ㅜ.ㅜ)
제출은 못했지만 공부는 할 수 있으니까!
백준에 같은 문제가 있어서 풀어보려한다~
 

목차 ( 클릭하면 이동! 👈🏻)

0. 문제
1. 문제풀이 핵심
2. 문제풀이에 사용된 개념
3. 문제풀이 코드
  3-1. 코드 로직 설명
4. 마무리

---

0. 문제

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

1991번: 트리 순회

 
입력값 : 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 (자식노드 중 없는 부분은 '. '으로 주어짐.
            (ex. 입력값이 B . . 이면 부모 노드는 'B' 라는 key값을 가지며 자식노드는 없다. = 'B' 노드는 이진트리에서 leaf 노드 이다.)
출력값 : 입력값으로 구성한 이진트리를 전위, 중위, 후위 순회할 때의 결과
 

---

1. 문제풀이 핵심

1. 직접 이진트리를 구현할 수 있는가
2. 전위 순회, 중위 순회, 후위 순회를 이해하고 있고, 구현할 수 있는가
 

---

2. 문제풀이에 사용된 개념

2.1 이진 트리
2.2 순회의 개념
 

2.1  이진 트리란?

트리란?
- 그래프 라는 자료구조(data structure)의 일종
   * 자료구조 : 데이터를 어떻게 효율적으로 저장하고 꺼내쓰지? 를 정리해놓은 규칙의 구조
       **자료구조의 종류 (array, linked list, queue, stack, 그래프 등등)
   * 그래프 : 노드와 간선으로 이루어진 자료구조. 노드는 간선으로 연결되어있음. 이를 통해 데이터의 관계를 나타낸다.
 
- node 와 edge로 이루어져있음
- node는 데이터를 저장하고 있음. 이 데이터를 key 라고 함
- edge는 node와 node를 연결하는 선. 데이터 간의 관계를 나타냄.
- root노드로부터 자식 노드들이 가지처럼 뻗어나감. 뒤집어진 나무 형태이다~
- root노드의 왼쪽 노드 를 root로 하는 트리 속의 트리를 왼쪽 서브트리,
오른쪽 노드를 root로 하는 트리 속의 트리를 오른쪽 서브트리 라고 해요

이진트리란?
자식 노드의 개수가 0개~2개인 트리
 
관계에 따라 node 를 부르는 다양한 명칭이 있어요
그 중에 중요한 것들! 
- 부모노드, 자식노드, 형제노드(왼쪽 자식 노드 ,오른쪽 자식 노드) 
- root노드, internal 노드,leaf 노드
 

2.2   트리 순회란?

위에서 봤듯이 문제에서 도출해내야하는 결과값!인 출력값은

입력값으로 구성한 이진트리를 전위, 중위, 후위 순회할 때의 결과..

 
**순회의 결과라..이것이 정확히 무엇인고~
 
우선
순회란?
트리의 각 노드들을 한번씩만 방문하면서~ 모든 노드를 돌아봐야하고~ 돌아보면서 각 노드의 key값을 확인해본다!!
 
이때
어디부터 시작해서 어디로! 어떤 규칙을 가지고! 체계적으로! 돌아다녀볼것인가?
이것이 관건입니다
이걸 규정해놓은게 각각 전위 순회, 중위 순회, 후위 순회 인 것이구요
 
전위 순회(preorder traversal)란?
루트노드 -> 왼쪽 서브트리 노드 -> 오른쪽 서브트리 노드
순서로 순회합니다

이때 주의할 점은 실제 트리 구조가 위의 그림처럼 트리의 트리..의 트리... 형식이기 때문에, 실제 전위 순회 결과가 A->B->C ... 가 아닌!! A->B->D->C ... 이라는 것 입니다
 
자세한 과정은 다음과 같습니다
 
초록색 트리 기준으로 (루트 -> 왼쪽 -> 오른쪽)
루트 노드 : A (방문. 초록색 트리의 루트 노드니까) 
-> A의 왼쪽 서브트리로 : 파란색 트리
 
     파란색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
     루트 노드 : B (방문. 파란색 트리의 루트 노드니까)
     -> B의 왼쪽 서브트리로 : 검정색 트리
 
           검정색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
          루트 노드 : D (방문. 검정색 트리의 루트 노드니까)
          -> D의 왼쪽 서브트리로 : 없음
          -> D의 오른쪽 서브트리로 : 없음
          => 검정색 트리 순회 완료 = B의 왼쪽 서브트리 순회 완료
 
     -> B의 오른쪽 서브트리로 : 없음 
    => 파란색 트리 순회 완료 = A의 왼쪽 서브트리 순회 완료
 
-> A의 오른쪽 서브트리로 : 빨간색 트리 
 
     빨간색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
     루트 노드 : C (방문. 빨간색 트리의 루트 노드니까 )
      -> C의 왼쪽 서브트리로 : 노란색 트리
       
          노란색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
          루트 노드 : E (방문. 노란색 트리의 루트 노드니까)
          -> E의 왼쪽 서브트리로 : 없음
          -> E의 오른쪽 서브트리로 : 없음
          => 노란색 트리 순회 완료 = C의 왼쪽 서브트리 순회 완료
 
     -> C의 오른쪽 서브트리로 : 보라색 트리
 
          보라색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
          루트 노드 : F (방문. 보라색 트리의 루트 노드니까)
          -> F의 왼쪽 서브트리로 : 없음
          -> F의 오른쪽 서브트리로 : 갈색 트리
 
               갈색 트리 를 기준으로 (루트 -> 왼쪽 -> 오른쪽)
               루트 노드 : G (방문. 갈색 트리의 루트 노드니까)
               -> G의 왼쪽 서브트리로 : 없음
               -> G의 오른쪽 서브트리로 : 없음
               => 갈색 트리 순회 완료 = F의 오른쪽 서브트리순회 완료
          => 보라색 트리 순회 완료 = C의 오른쪽 서브트리 순회 완료
     => 빨간색 트리 순회 완료 = A의 오른쪽 서브트리 순회 완료
=> 초록색 트리 순회 완료
 
트리 전위 순회 완료

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)

 
중위 순회(inorder traversal)란?
왼쪽 서브트리 노드 -> 루트노드 -> 오른쪽 서브트리 노드
 
자세한 과정은 순서만 바뀔 뿐이지 전위 순회와 원리가 같습니다
직접 해보시면 이해가 확실해져용

• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)

 
후위 순회(postorder traversal)란?
왼쪽 서브트리 노드 -> 오른쪽 서브트리 노드 -> 루트노드

• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

---

3. 문제풀이 코드

#include<iostream>
using namespace std;

int BT[43][2]; //부모노드와 자식노드 저장할 배열. 아스키코드 활용.
int n;

void preorder(int node){
    if (node == -1) return;
    cout<< (char)(node+'0');
    preorder(BT[node][0]);
    preorder(BT[node][1]);
}
void inorder(int node){
    if (node == -1) return;
    inorder(BT[node][0]);
    cout<<(char)(node+'0');
    inorder(BT[node][1]);
}
void postorder(int node){
    if (node == -1) return;
    postorder(BT[node][0]);
    postorder(BT[node][1]);
    cout<<(char)(node+'0');
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    while(n--){
        char root,left,right;

        cin>>root>>left>>right;
        if(left!='.'){
            BT[root-'0'][0] = left-'0'; 
        }else if(left =='.'){
            BT[root-'0'][0] = -1; 
        }

        if(right!='.'){
            BT[root-'0'][1] = right-'0'; 
        }else if(right =='.'){
            BT[root-'0'][1] = -1; 
        }
    }
    preorder('A'-'0');
    cout<<'\n';
    inorder('A'-'0');
    cout<<'\n';
    postorder('A'-'0');

}

실수 포인트!
각 알파벳의 아스키코드를 인덱스로 활용해서 배열에는 해당 인덱스를 아스키코드로 가지는 노드의 자식 노드를 저장했다.
이때, 아스키코드를 사용할 때 
처음에
노드값(char) - 'A' 가 아니라
노드값(char) -'0' 으로 했는데..
'A'의 아스키코드값이 65이고
'Z'는 90
'0'은 48
이기 때문에 알파벳 26개 제외하고 'A'와 '0'의 차이인 17개 만큼의 배열 공간이 추가적으로 할당되어있어야 한다. 안그러면 존재하지않는 배열 인덱스에 접근하는게 되어 런타임에러가 난다.. 당연하다
그리고 배열에서 0 부터 16까지의 인덱스는 비어있게 된다
 
그니까 알파벳을 아스키코드로 쓸 때 -'A'로 해주자! 나 자신
인덱스 0부터 활용하는게 낫지
굳이 앞에 17칸을 비워둘 필요가 없는 것이다...
 

3-1. 코드 로직 설명

 
1. 이진 트리 구현
이차원 배열 이용
[부모노드 아스키코드 값-'A'][0] = 부모노드의 왼쪽 자식노드 아스키코드 값 -'A'
[부모노드 아스키코드 값-'A'][1] = 부모노드의 오른쪽 자식노드 아스키코드 값 -'A'
 
2. 순회
재귀를 이용

---

4. 마무리

잔잔바리 실수 주의 !
그리고 재귀적 사고방식이 필요하다