이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.
[입력] 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
[출력] 첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
✅ 문제 풀이
트리를 전위, 중위, 후위 순회하는 방법은 각각의 함수를 재귀호출하는 방법이다.
트리를 int타입의 2차원 배열에 넣을건데, 각 노드는 입력으로 받는 노드 즉 알파벳에서 'A'를 뺀 값을 인덱스로 받을 것이다. 따라서 A부터이므로, 0~25까지 인덱스를 사용하게 될 것이다. 그 인덱스의 첫번째 요소에는 left자식이, 두번째 요소에는 right자식이 들어가는 것이다.
따라서 left에는 두번째로 입력받은 문자가 .이 아닐 경우 문자-'A' 한 값을 넣어주고, right도 세번째로 입력받은 문자에 대해 동일하게 처리한다.
만약 문자가 .이라면 -1을 넣도록 한다.
preorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 node n을 알파벳으로 출력하기 위해 n+'A'를 하여 알파벳으로 출력한다. 그런후 preorder(arr[n][0])와 preorder(arr[n][1])을 차례로 호출하여 재귀 호출되도록 한다.
inorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 inorder(arr[n][0])를 호출한 후, n을 알파벳으로 출력하고, inorder(arr[n][1])을 호출한다.
postorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 postorder(arr[n][0])와 postorder(arr[n][1])을 호출한 후, n을 알파벳으로 출력한다.
각각의 함수들을 main함수에서 n=0으로 시작해 호출하고 결과를 확인한다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
void preorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
cout << (char)(n + 'A');
preorder(arr[n][0], arr);
preorder(arr[n][1], arr);
}
void inorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
inorder(arr[n][0], arr);
cout << (char)(n + 'A');
inorder(arr[n][1], arr);
}
void postorder(int n, vector<vector<int>> &arr) {
if (n == -1) return;
postorder(arr[n][0], arr);
postorder(arr[n][1], arr);
cout << (char)(n + 'A');
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<vector<int>> arr(n);
for (int i = 0; i < n; i++) {
char node, l, r;
cin >> node >> l >> r;
int x = node - 'A';
if (l == '.') {
arr[x].push_back(-1);
}
else arr[x].push_back(l-'A');
if (r == '.') {
arr[x].push_back(-1);
}
else arr[x].push_back(r - 'A');
}
preorder(0, arr);
cout << "\n";
inorder(0, arr);
cout << "\n";
postorder(0, arr);
cout << "\n";
return 0;
}
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.
[입력] 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
[출력] 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
✅ 문제 풀이
각 노드에 대한 자식 노드를 저장하기 위해서, vector 형태의 크기가 50인 배열 tree을 생성해주었다. vector<int> tree[50]
입력으로 N이 1부터 50까지 들어올 수 있기 때문에, 노드는 0~49임을 고려한 것이다.
차례대로 입력받을 때 0번 노드부터 부모를 입력받는다.
따라서 -1인 경우를 제외하고, 나머지 경우에 대해서는 입력받은 값을 p라고 했을 때, tree[p]에다가 해당 노드를 저장해준다. vector형태니까, push_back(해당 노드) 해주면 된다.
그럼 모든 노드에 대해서 바로 아래 자식 노드 리스트를 가지게 된다. 당연히, 자식이 없는 노드의 벡터는 비어있을 것이다.
그리고 삭제된 노드인지, 리프노드인지를 구별하기 위해 bool타입의 배열 leaf를 생성해서 false로 초기화 해주었다.
삭제할 노드를 입력받고, 해당 노드를 기준으로 dfs함수를 호출한다.
dfs 함수에서는 다음과 같이 동작한다. 입력 : tree, 삭제할 노드 node, leaf 로직 - 삭제할 노드의 자식 노드들을 순회한다. 즉 tree[node]를 순회한다. - 이 때 자식 노드를 num에 저장해두고, 자식의 자식들을 순회하기 위해 dfs를 호출하여 삭제할 노드로 num을 넘겨준다. -그리고 해당 노드에 대해 모두 순회했으면, tree[node]를 clear하여 모두 삭제해주고, 이는 삭제된 노드이므로 leaf[node]를 true로 변경해준다.
입력한 삭제 노드에 대해 위 로직을 따르고 나면, 이제 입력 값만을 부모에서 삭제해주면 된다.
부모를 찾기위해서 2중 for문을 통해 입력받은 값을 자식으로 갖는 노드가 있는지 순회하고, 일치하다면 해당 부모 노드의 배열에서 삭제하도록 한다. 그리고 순회를 즉시 멈춘다.
이제 삭제할 노드를 기점으로 모두 삭제되었으므로, tree배열을 순회하면서 leaf가 false이고(=삭제되지 않은노드), tree[i]의 size가 0인 노드를 카운트 하여 출력한다.
☑ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int> tree[], int node, bool leaf[]) {
for (int i = 0; i < tree[node].size(); i++) {
int num = tree[node][i];
dfs(tree, num, leaf);
}
tree[node].clear();
leaf[node] = true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<int> tree[50];
bool leaf[50] = {false};//false->true 개수만 세기
for (int i = 0; i < N; i++) {
int p;
cin >> p;
if (p == -1) continue;
else {
tree[p].push_back(i);
}
}
int node;
cin >> node;
dfs(tree, node, leaf);
bool br=false;
for (int i = 0; i < N; i++) {
for (auto it = tree[i].begin(); it != tree[i].end(); it++) {
if (*it==node) {
tree[i].erase(it);
br = true;
break;
}
}
if (br) break;
}
int answer = 0;
for (int i = 0; i < N; i++) {
if (!leaf[i]&&tree[i].size() == 0) answer++;
}
cout << answer;
return 0;
}
