티스토리 뷰

링크 : www.acmicpc.net/problem/1991

문제요약 

입력

이진 트리 노드의 갯수(N)

각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드

 

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력

 

전위, 중위 후위 순회 개념 : eugene-lab.tistory.com/70


코드작성개요

필요한변수

N - 이진트리 노드의 개수(1≤N≤26)

p, n1, n2 - 부모노드, 왼쪽 자식노드, 오른쪽 자식노드

adj - vector<pair<int, int>> 형태의 이진트리(size = N)

 

입력

이진트리 노드의 개수 N

p, n1, n2 를 문자로 받아서 'A' 로 빼줘서 int 형으로 바꿔준후 adj 에 담는다.

 

전위순회

  1.  ' . ' 이 들어왔다면 아무것도 리턴하지 않는다.
  2.  현재 노드를 출력한다.
  3.  now 노드의 왼쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)
  4. 3번 과정이 끝나면 오른쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)

중위순회

  1.  ' . ' 이 들어왔다면 아무것도 리턴하지 않는다.
  2.  now 노드의 왼쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)
  3. 현재 노드를 출력한다.
  4. 3번 과정이 끝나면 오른쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)

 

후위순회

  1.  ' . ' 이 들어왔다면 아무것도 리턴하지 않는다.
  2.  now 노드의 왼쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)
  3. 3번 과정이 끝나면 오른쪽 노드를 기준(now)으로 함수를 재귀호출한다. (1번부터 다시 반복)
  4. 현재 노드를 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int, int>>adj;

//전위순회
void preorder_traversal(int now)
{
    if(now == '.' - 'A')return;
    cout << char(now + 'A');
    preorder_traversal(adj[now].first);
    preorder_traversal(adj[now].second);
}

//중위순회
void inorder_traversal(int now)
{
    if(now == '.' - 'A')return;
    inorder_traversal(adj[now].first);
    cout << char(now + 'A');
    inorder_traversal(adj[now].second);
}

//후위순회
void postorder_traversal(int now)
{
    if(now == '.' - 'A')return;
    postorder_traversal(adj[now].first);
    postorder_traversal(adj[now].second);
    cout << char(now + 'A');
}

int main()
{
    int N;
    cin >> N;
    adj.resize(N);
    for(int i = 0; i < N; i++){
        char p, n1, n2;
        cin >> p >> n1 >> n2;
        adj[p - 'A'].first = n1 - 'A';
        adj[p - 'A'].second = n2 - 'A';
    }
    preorder_traversal(0);
    cout << '\n';
    inorder_traversal(0);
    cout << '\n';
    postorder_traversal(0);

    return 0;
}
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함