백준 1991번 트리순회

< 백준 1991번 트리순회 - 마포 코딩박 >

사용한 알고리즘: 구현


 문제에서 preorder, inorder, postorder 의 개념을 설명해주고 이를 구현하는 것을 요구합니다.

문제풀이는 다음과 같습니다.
(1) (코드 6~7)
 사실 각 노드값 A,B,C... 가 유일하다고 ( A인 노드가 하나뿐이라고 ) 생각했습니다.....
 ( 문제에서는 이점을 명시하지는 않았지만, 노드가 최대 26개라고 하긴 했습니다... )
 각 i 노드의 왼쪽 자식과 오른쪽자식을 저장할 2차배열을 만들었습니다.

(2) (코드 9~22)
 preorder 구현입니다. 자기 -> 왼쪽 -> 오른쪽 순으로 순회합니다.

(3) (코드 23~36)
 inorder 구현입니다. 왼쪽 -> 자기 -> 오른쪽 순으로 순회합니다.

(4) (코드 37~50)
 postorder 구현입니다. 왼쪽 -> 오른쪽 -> 자기 순으로 순회합니다.

	#include <iostream>
	#include <cstring>
	using namespace std;
	bool visited[27];
	// tree[i][0] : i 의 왼쪽자식 , tree[i][1] : i의 오른쪽자식
	char tree[27][2];
	int N, tototo;
	// 전위순회
	void preorder(int x){
	if(visited[x]) return;
	visited[x] = true;
	// 루트
	char Root = x+'A';
	cout << Root;
	// 왼쪽 자식
	int Left = tree[x][0]-'A';
	if(Left >= 0) preorder(Left);
	// 오른쪽 자식
	int Right = tree[x][1]-'A';
	if(Right >= 0) preorder(Right);
	}
	// 중위순회
	void inorder(int x){
	if(visited[x]) return;
	visited[x] = true;
	// 왼쪽 자식
	int Left = tree[x][0]-'A';
	if(Left >= 0) inorder(Left);
	// 루트
	char Root = x+'A';
	cout << Root;
	// 오른쪽 자식
	int Right = tree[x][1]-'A';
	if(Right >= 0) inorder(Right);
	}
	// 후위순회
	void postorder(int x){
	if(visited[x]) return;
	visited[x] = true;
	// 왼쪽 자식
	int Left = tree[x][0]-'A';
	if(Left >= 0) postorder(Left);
	// 오른쪽 자식
	int Right = tree[x][1]-'A';
	if(Right >= 0) postorder(Right);
	// 루트
	char Root = x+'A';
	cout << Root;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	char a, b, c;
	cin >> a >> b >> c;
	tree[a-'A'][0] = b;
	tree[a-'A'][1] = c;
	}
	// 전위순회
	preorder(0);
	cout << '\n';
	// 중위순회
	memset(visited,0,sizeof(visited));
	inorder(0);
	cout << '\n';
	// 후위순회
	memset(visited,0,sizeof(visited));
	postorder(0);
	cout << '\n';
	return 0;
	}

view raw BOJ 1991.cpp hosted with ❤ by GitHub