백준 1991 트리 순회

2020. 9. 10. 16:19·알고리즘/BOJ

www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

기초적인 트리 순회 문제.

처음에는 노드로 트리를 구현하여 순회시키려 했지만 생각보다 난이도가 있어서 배열로 구현했다.

이런 식으로 서브 노드가 더 이상 존재하지 않으면 '.'을 넣어 끝임을 표시한다.

	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		tree[a - 'A'][0] = b;
		tree[a - 'A'][1] = c;
	}

[0]은 왼쪽, [1]은 오른쪽으로 표현하여 각각의 아스키코드값으로 받아준다.

이렇게 하면 순회할 때

void preorder(char root) { //루트노드를 받아서
	if (root == '.') return;

	cout << root; //출력하고
	preorder(tree[root - 'A'][0]); //그 루트 노드의 왼쪽에 있는 서브노드를 재귀호출한다
	preorder(tree[root - 'A'][1]);
}

이런식으로 그 노드의 왼쪽, 오른쪽에 있는 노드를 재귀 호출해주면 된다.

 

#include <iostream>
using namespace std;

char tree[27][2];

void preorder(char root) {
	if (root == '.') return;

	cout << root;
	preorder(tree[root - 'A'][0]);
	preorder(tree[root - 'A'][1]);
}
void inorder(char root) {
	if (root == '.') return;

	inorder(tree[root - 'A'][0]);
	cout << root;
	inorder(tree[root - 'A'][1]);
}
void postorder(char root) {
	if (root == '.') return;

	postorder(tree[root - 'A'][0]);
	postorder(tree[root - 'A'][1]);
	cout << root;
}

int main() {
	int n;
	char a, b, c;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		tree[a - 'A'][0] = b;
		tree[a - 'A'][1] = c;
	}
	preorder('A');
	cout << endl;
	inorder('A');
	cout << endl;
	postorder('A');
	cout << endl;

	return 0;
}

 

잘 기억해둬야겠다.

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1967 트리의 지름  (0) 2020.09.10
백준 11725 트리의 부모 찾기  (0) 2020.09.10
백준 19699 소-난다!  (0) 2020.09.10
백준 2146 다리 만들기  (0) 2020.09.10
백준 9466 텀 프로젝트  (0) 2020.09.09
'알고리즘/BOJ' 카테고리의 다른 글
  • 백준 1967 트리의 지름
  • 백준 11725 트리의 부모 찾기
  • 백준 19699 소-난다!
  • 백준 2146 다리 만들기
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    행렬 제곱
    유니온 파인드
    dp
    다익스트라
    시뮬레이션
    피사노 주기
    BOJ
    MST
    dfs
    완전 탐색
    코딩테스트 연습
    트리
    구현
    SWEA
    우선순위 큐
    완전탐색
    냅색
    크루스칼
    팰린드롬
    분할 정복
    피보나치 수
    이분 탐색
    알고리즘
    GREEDY
    소수
    BFS
    조합
    큐
    이분탐색
    프로그래머스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
백준 1991 트리 순회
상단으로

티스토리툴바