Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 자료구조
- asp.net core
- 탐색
- sql
- BFS
- 도커
- Merge Sort
- 재귀
- Get
- quick sort
- REDIS
- maui
- 스택
- asp.net
- 시간복잡도
- 파이썬
- .net maui
- 정렬
- API
- dfs
- C++
- C#
- .NET
- 큐
- .net core
- Docker
- 알고리즘
- 백준
- docker-compose
- mysql
Archives
- Today
- Total
코젤브
3주차 - 트리 (백준 1991번) 본문
백준 1991번 문제: 트리 순회
https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파
www.acmicpc.net
3주차 트리 자료구조 교육에서 배운 것처럼,
구조체를 통해 이진 트리를 구현하고 각 정의에 맞게 코드를 구성하면 된다.
- 전위 순위
: 루트 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 - 중위 순위
: 왼쪽 서브트리 방문 -> 루트 노드 방문 -> 오른쪽 서브트리 방문 - 후위 순위
: 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 루트 노드 방문
재귀를 사용한 방법, 반복을 사용한 방법으로 구현할 수 있다.
재귀를 사용한 방법은 반복문보다 성능은 떨어지지만 가독성이 높다는 장점이 있다.
따라서 나는 재귀를 사용하여 코드를 구현했다.
처음에 아래와 같이 구조체와 포인트를 활용한 방법(일반적으로 배운 방법)을 통해 구현하려고 했는데,
//하나의 노드 정보를 선언
typedef struct node* TreeNode;
typedef struct node {
char data;
TreeNode left, right;
} node;
//전위 순회 구현
void preorder(TreeNode ptr) {
if (ptr != NULL) {
cout << ptr->data; // (1) 자기 자신을 처리
preorder(ptr->left); // (2) 왼쪽 방문
preorder(ptr->right); // (3) 오른쪽 방문
}
}
//중위 순회 구현
void inorder(TreeNode ptr) {
if (ptr != NULL) {
inorder(ptr->left); // (1) 왼쪽 방문
cout << ptr->data; // (2) 자기 자신을 처리
inorder(ptr->right);// (3) 오른쪽 방문
}
}
//후위 순회 구현
void postorder(TreeNode ptr) {
if (ptr != NULL) {
postorder(ptr->left); // (1) 왼쪽 방문
postorder(ptr->right);// (2) 오른쪽 방문
cout << ptr->data; // (3) 자기 자신을 처리
}
}
main 부분에서 노드를 입력 받는 부분에서 오류를 해결하지 못해서,
구글링을 통해 참고하여 조금 다른 방법으로 구현했다.
최종 제출 코드
#include <iostream>
using namespace std;
struct node {
char left;
char right;
};
struct node arr[100];
void preorder(char root) {
if (root == '.') // root가 .이면 상관 없으므로
return;
else {
cout << root;
preorder(arr[root].left);
preorder(arr[root].right);
}
}
void inorder(char root) {
if (root == '.') // root가 .이면 상관 없으므로
return;
else {
inorder(arr[root].left);
cout << root;
inorder(arr[root].right);
}
}
void postorder(char root) {
if (root == '.') // root가 .이면 상관 없으므로
return;
else {
postorder(arr[root].left);
postorder(arr[root].right);
cout << root;
}
}
int main() {
int n;
cin >> n; // 노드의 개수
char node, lNode, rNode; // 차례로 입력 받음
for (int i = 1; i <= n; i++) {
cin >> node >> lNode >> rNode;
arr[node].left = lNode;
arr[node].right = rNode;
}
preorder('A');
cout << endl;
inorder('A');
cout << endl;
postorder('A');
cout << endl;
return 0;
}
node 구조체 구현
=> 포인터로 노드를 받지 않고, 구조체에 char타입인 left와 right만 존재한다.
탐색 부분 함수 구현
=> . (즉 단일 노드 일 때)는 구분하여 return만 하고, 그 외의 경우는 위와 같이 각 탐색별 정의에 맞게 탐색한다.
main 함수 구현
노드의 개수는 n으로 입력받고 n만큼 반복해서 순차적으로 3개씩 입력 받는다.
이때 노드, 왼쪽 노드, 오른쪽 노드 순으로 입력 받는 것 이므로 이에 맞게 코드를 구성한다.
제출 결과
'컴공의 일상 > 백준 문제' 카테고리의 다른 글
6주차 - Backtracking (백준 2580번) (0) | 2022.05.18 |
---|---|
5주차 - 그리디 알고리즘 (백준 11047) (0) | 2022.05.13 |
4주차 - 정렬과 탐색(백준 2750번) 합병 정렬 & 퀵 정렬 (0) | 2022.05.05 |
2주차 - 그래프(백준 5567) (0) | 2022.03.21 |
1주차 - 스택과 큐(10828, 10845) (2) | 2022.03.11 |