⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️
https://www.acmicpc.net/problem/1991
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파
www.acmicpc.net
Code
#include <stdio.h>
#include <stdlib.h>
// 구조체 설정
typedef struct Node{
char data;
struct Node *left;
struct Node *right;
}node;
// 노드 생성
node *makeNode(char ch){
node *nd = (node*)malloc(sizeof(node));
nd->data = ch;
nd->left = NULL;
nd->right = NULL;
return nd;
}
// 이미 넣은 알파벳인지 확인 후 넣기
node *searchNode(node *nd, char ch){
if(nd != NULL){
if(nd->data == ch){
return nd;
}
else{ // 왼쪽 뒤지고, 없으면 오른쪽 뒤짐
node *ndd = searchNode(nd->left, ch);
if(ndd != NULL){
return ndd;
}
else
return searchNode(nd->right, ch);
}
}
else
return NULL;
}
// 노드에 값 집어넣기
void setNode(node *nd, char fir, char sec, char thr){
nd->data = fir;
if (sec != '.'){
nd->left = makeNode(sec);
}
if(thr != '.'){
nd->right = makeNode(thr);
}
}
// 전위 순회 출력
void preorderPrint(node *nd){
if(nd == NULL){
return;
}
else{
printf("%c", nd->data);
preorderPrint(nd->left);
preorderPrint(nd->right);
}
}
// 중위 순회 출력
void inorderPrint(node *nd){
if(nd == NULL){
return;
}
else{
inorderPrint(nd->left);
printf("%c", nd->data);
inorderPrint(nd->right);
}
}
// 후위 순회 출력
void postorderPrint(node *nd){
if(nd == NULL){
return;
}
else{
postorderPrint(nd->left);
postorderPrint(nd->right);
printf("%c", nd->data);
}
}
int main() {
int num; // 트리의 노드 갯수
char a, b, c; // 노드와 왼쪽자식, 오른쪽 자식 노드
node *tree = makeNode(NULL); // 정답 도출용 작성되는 노드
node *tree2; // tree에서 나온 주소에 바로 이어서 작성하기 위한 노드
scanf("%d", &num);
getchar();
// num만큼 for문을 통해 값 입력받고, node에 추가
for(int i = 0; i < num; i++){
scanf("%c %c %c", &a, &b, &c);
getchar();
tree2 = searchNode(tree, a);
if(tree2 != NULL){ // tree노드에 있는 값이라는 뜻 => tree노드에서 a가 들어갈 주소를 갖고있는 tree2에 넣기
setNode(tree2, a, b, c);
}
else{ // 처음에 A를 집어넣는 과정
setNode(tree, a, b, c);
}
}
// 전위, 중위, 후위에 맞게 출력
preorderPrint(tree); // 전위
printf("\n");
inorderPrint(tree); // 중위
printf("\n");
postorderPrint(tree); // 후위
return 0;
}
Code 필수 요소
1. 구조체의 활용방법
2. node를 활용해서 tree구조를 만드는 방법
이것만 생각해내면 절반은 끝났다.
// 구조체 설정
말 그대로 구조체를 만들어 주는 단계다. data는 해당 노드에 들어있는 값을 의미한다. 그 후 left와 right가 있는데, 포인터인 노드이다. C언어에 대해 초심자라면 이것에 대해서 많이 헷갈릴 것이다. 왜 굳이 포인터로 해야하지???
해답은 연결된 구조를 만들기 위해서다. 포인터를 사용할 경우 해당 값의 왼쪽 오른쪽 노드의 주소를 기록할 수 있기 때문에 연결된것 처럼 사용할 수 있다.
// 노드 생성
노드를 만들어주는 단계다. 동적할당을 통해서 적당한 크기를 생성하고, data값을 넣어준다. left와 right의 값에 NULL을 넣어주어서 해당 노드를 완성시킨다. 여기서 왜 NULL을 넣어주냐 라는 생각을 할 수가 있다. 아무 값도 넣지 않을 경우 이후에 내가 작성해둔 코드를 본다면 노드의 left, right값에 접근을 한다. 하지만 해당 값이 NULL로 초기화가 되어있지 않다면, 내가 원하지 않는 이상한 값이 도출 될 수 있기 때문에 NULL로 초기화 해줘야 한다.
// 이미 넣은 알파벳인지 확인 후 넣기
먼저 해당 노드가 비어있는지를 확인한다. 그 후 그 노드의 data값이 찾고자하는 알파벳과 같은지 확인 후 같다면 그대로 사용, 다를경우 노드의 왼쪽 자식과 오른쪽 자식을 뒤져본다. 여기서 ndd라는 새로운 노드를 만들어서 탐색에 이용한다.
그런데 왜 return을 ndd로 하는지 헷갈리는 경우가 있는데, ndd는 포인터로 된 node이다. 그렇기 때문에 nd->left의 data값의 주소를 가지고 있는 것이다. 즉, nd주소를 return하는 것이다.
// 노드에 값 집어넣기
말 그대로 노드에 값을 집어넣는 과정이다. 값을 넣고자 하나는 node의 data값에 알파벳을 넣고, 두번째와 세번째가 비어있는지 확인한다. 비어있지 않다면 값을 넣는다.
// 전위 순회 출력 // 중위 순회 출력 // 후위 순회 출력
이 세개는 출력 순서만 다른거지 같은 코드다. 왜 저런 방식으로 출력하는지 모르겠다면 하나씩 그려봐라. 위에서부터 내려오면서 왜 저 값이 출력됐는지 생각하며 그림을 그려보면 알 수 있다.
// main 함수
여기서부터는 위에 작성해둔 함수들을 적당히 잘 섞으면 된다. tree와 tree2 이렇게 두개를 만든 이유는 nd와 ndd를 만들어서 진행한것과 같은 이유다. 편할려고... 그리고 getchar();를 왜 넣었는지를 혹시나 해서 설명하면 버퍼를 없애려고 넣었다. 저거 안넣으면 엔터도 입력돼서 답이 개판으로 나온다. 궁금하다면 내 코드 복사해가서 getchar();만 제거해봐라. 답이 재밌게 나올거다.
이번건 꽤나 많이 어려웠다. 내가 구조체 자체에 어려움을 느끼는 것도 있었지만, node사용이 익숙치 않았던게 더 컸다. getchar를 사용하는것도 이번에서야 사용법을 알게됐고, 트리구조를 그려보라느니 쉬운듯 말했지만 저거 하는데 시간 엄청 쏟아부었다. 결론적으로 포인터, 구조체, 트리구조 이 세가지가 힘들었다.
-꿑-