득이공간
[백준 C++] 1991 트리 순회 - 이진트리 본문
#include <iostream>
#include <string>
using namespace std;
string PreorderTree;
string InorderTree;
string PostorderTree;
char Tree[27][2];
void DFS(char Parent)
{
if (Parent == '.')
{
return;
}
char LeftChild = Tree[Parent - 65][0];
char RightChild = Tree[Parent - 65][1];
PreorderTree.push_back(Parent);
DFS(LeftChild);
InorderTree.push_back(Parent);
DFS(RightChild);
PostorderTree.push_back(Parent);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
char Parent, Left, Right;
cin >> Parent >> Left >> Right;
Tree[Parent - 65][0] = Left;
Tree[Parent - 65][1] = Right;
}
DFS('A');
cout << PreorderTree << '\n';
cout << InorderTree << '\n';
cout << PostorderTree;
}
하나의 이진 트리를 전위 순회, 중위 순회, 후위 순회로 각각 출력 연산하도록 하는 문제입니다.
순회별 출력 문자를 담을 string을 따로 만들고
깊이우선탐색을 사용해서
자식 노드 진입 전에는 전위 순회 문자열에 push,
왼쪽 자식 진입 후에는 중위 순회 문자열에 push,
모든 자식 진입 후에는 후위 순회 문자열에 push해서
최종적으로 탐색 순서를 출력하도록 풀었습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 2357 최솟값과 최댓값 - 세그먼트트리 (0) | 2024.02.12 |
---|---|
[백준 C++] 2042 구간 합 구하기 - 세그먼트트리 (0) | 2024.02.11 |
[백준 C++] 1946 신입 사원 - 정렬 (0) | 2024.02.09 |
[백준 C++] 18870 좌표 압축 - 정렬 (0) | 2024.02.09 |
[백준 C++] 12015 가장 긴 증가하는 부분 수열 2 - 이분탐색 (0) | 2024.02.08 |