[C++] Map을 이용한 tree 구현 (BOJ 1991: 트리순회)

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

1991번: 트리 순회

 

이 문제를 직접 tree를 구현하여 풀지 않고 map을 이용하여 구현하였다.

 

Map이란?

 map은 각 노드가 key와 value가 쌍을 이루고 있는 트리로 pair 객체로 저장되기 때문에 first-key로 second-value를 저장한다. 중복을 허락하지 않으며 기본 형태는 map<key,value> m; 으로 key를 통해 value를 찾기 용이하게 되어있다. 그래서 map은 pair로 이루어진 set 자료구조라고도 불린다

 

 또 가장 큰 특징으로는 자료를 저장할 때 내부에서 자동으로 오름차순으로 정렬된다는 것이다. 만약 내림차순으로 정렬하고 싶은 경우에는 map<key,value,greater> m와 같이 사용하면 된다.

 

자세한 내용은 아래 포스팅을 참고하면 된다!

https://donggul-godsang.tistory.com/74

[C++] Map 기본 사용법! (BOJ 17219: 비밀번호 찾기)

 

 

MAP을 사용한 이유?

 다른 STL을 사용하지 않고 MAP을 사용한 이유가 있다. 여기서는 부모노드에 접근했을 때 바로 왼쪽과 오른쪽의 자식 노드를 알 수 있어야한다. 이런 특성만을 고려하면 vector <char,pair<char,char>> v;로 선언하고 풀어도 될 것 같지만 vector을 사용하게 된다면 부모노드를 찾는데에 시간이 걸릴 수 밖에 없다. 부모노드를 찾기 위해서는 따른 vector을 하나 더 만들어 부모노드의 위치를 저장하게 하거나 find를 이용하여야 하는데 모두 코드를 복잡하게 만든다.

 

  그렇기 때문에 부모노드를 한번에 찾을 수 있고 부모노드를 알고 있을 떄 자식 노드 2개 모두 바로 알 수 있기 위해 pair을 통해 map을 선언해주면 아래와 같이 쓸 수 있다.

 

map<char,pair<char,char>> tree;

 

 

구현!!

 main 함수에서 위에서 언급했다싶이 부모노드를 알고 있으면 자식노드들을 알 수 있게 만들기 위해 노드들을 각각 parent,left,right로 받고

tree[parent]=make_pair(left,right)를 통해 map에 저장하였다.

 

그 후 preorder, inorder, postorder 함수를 만들어 각각 호출하여  전위 순회, 중위순회, 후위 순회를 하였는데 이 3개의 함수는 부모노드를 언제 출력할지에 따라 순서만 다를 뿐 내용은 같다고 볼 수 있다. (부모노드를 처음에 출력하면 전위, 두번째에 출력하면 중위, 마지막에 출력하면 후위)

 그리고 이 문제에서는 자식이 없을 경우 '.'으로 표현하고 있기 때문에 자식 노드가 '.'가 아닐 때만 재귀적으로 호출하도록 코드를 구현하였다.

 

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
map<char,pair<char,char>> tree; //순서대로 부모노드, 왼쪽 자식 노드, 오른쪽 자식 노드

void preorder(char c){
  cout<<c;
  if(tree[c].first!='.') //왼쪽 자식 노드가 존재할 때
    preorder(tree[c].first);
  if(tree[c].second!='.') //오른쪽 자식 노드가 존재할 때
    preorder(tree[c].second);
}

void inorder(char c){
  
   
  if(tree[c].first!='.') //왼쪽 자식 노드가 존재할 때
    inorder(tree[c].first);
  cout<<c;
  if(tree[c].second!='.') //오른쪽 자식 노드가 존재할 때
    inorder(tree[c].second);
}

void postorder(char c){
  
  if(tree[c].first!='.') //왼쪽 자식 노드가 존재할 때
    postorder(tree[c].first);
  if(tree[c].second!='.') //오른쪽 자식 노드가 존재할 때
    postorder(tree[c].second);
  cout<<c;
}


int main() {    
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
    {
      char parent,left,right;
      cin>>parent>>left>>right;
      tree[parent]=make_pair(left,right);
    }
  preorder('A');
  cout<<"\n";
  inorder('A');
  cout<<"\n";
  postorder('A');
  
}