알고리즘/백준
[백준 1991] 트리 순회
동 코
2020. 4. 17. 22:59
문제풀이
tree 연습용 문제였다. 이또한 malloc 말고 new 를 사용하였다. 계속 짜는 연습을 해서 익숙해질 필요가 있는것 같다.
소스코드
더보기
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include <iostream>
using namespace std;
class TreeNode{
friend class Tree;
private:
char data;
TreeNode* leftChild;
TreeNode* rightChild;
public:
TreeNode(char d){
data = d;
leftChild = NULL;
rightChild = NULL;
}
};
TreeNode* node[27]={NULL,};
class Tree{
private:
TreeNode* root;
public:
Tree():root(NULL){};
~Tree(){};
void setRoot(){
root = node[0];
}
void connectTree(char V, char L, char R){
int V_idx = V-'A';
if(L=='.'){
node[V_idx]->leftChild = NULL;
}else{
node[V_idx]->leftChild = node[L-'A'];
}
if(R=='.'){
node[V_idx]->rightChild = NULL;
}
else{
node[V_idx]->rightChild = node[R-'A'];
}
}
TreeNode* getRoot(){
return root;
}
void preorder(TreeNode* ptr){
if(ptr){
cout<<ptr->data;
preorder(ptr->leftChild);
preorder(ptr->rightChild);
}
}
void postorder(TreeNode* ptr){
if (ptr) {
postorder(ptr->leftChild);
postorder(ptr->rightChild);
cout<<ptr->data;
}
}
void inorder(TreeNode* ptr){
if (ptr) {
inorder(ptr->leftChild);
cout<<ptr->data;
inorder(ptr->rightChild);
}
}
};
int N;
Tree* tree;
int main() {
cin>>N;
for(int i=0;i<N;i++){
node[i] = new TreeNode('A'+i);
}
tree = new Tree();
if(node[0]!=NULL){
tree->setRoot();
}
for(int i=0;i<N;i++){
char V,L,R;
cin>>V>>L>>R;
tree->connectTree(V,L, R);
}
tree->preorder(tree->getRoot());
cout<<"\n";
tree->inorder(tree->getRoot());
cout<<"\n";
tree->postorder(tree->getRoot());
cout<<"\n";
}
|
문제 링크 : https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.
www.acmicpc.net