안녕하세요 C++을 공부하고있는 대학생입니다.
이번에는 연결리스트를 이용한 완전 이진트리를 구현 해 볼 생각입니다.
#include <stdio.h>
#include <stdlib.h>사용 한 헤더입니다.
typedef struct node {
struct node* next;
int data;
int size;
}node;
typedef struct Tree {
node nodes;
struct nodes* input;
struct Tree* left;
struct Tree* right;
int data;
}Tree;단일 연결리스트에 대한 구조체 정의 와 이진트리에 대한 구조체 정의 입니다.
node* root = NULL;
int size = 0;연결리스트에 대해 root (head) 점을 잡아서 NULL로 초기화시켜주고, size 개수를 측정하기위해 int 타입의 변수를 선언 해 주었습니다.
node* insert(node* root, int data) {
if (root == NULL) {
root = (node*)malloc(sizeof(node));
root->next = NULL;
root->data = data;
size++;
return root;
}
else {
root->next = insert(root->next, data);
return root;
}
}insert 부분입니다. root 가 NULL값 일 경우, data를 넣어주고 아니라면, root->next로 이동하면서 NULL체크를 하면서 데이터를 넣어주는 재귀부분입니다.
트리에는 순회방법이 3가지가 있습니다.
- 전위순회
=>1. 자기자신을 출력한다.
=>2. 자기자신의 왼쪽부분으로 재귀를 통해 출력한다.
=>3. 자기자신의 오른쪽부분으로 재귀를 통해 출력한다.- 중위순회
=>1. 자기자신의 왼쪽부분으로 재귀를 통해 출력한다.
=>2. 자기자신을 출력한다.
=>3. 자기자신의 오른쪽부분으로 재귀를 통해 출력한다.- 후위순회
=>1. 자기자신의 왼쪽부분을 재귀를 통해 출력한다.
=>2. 자기자신의 오른쪽부분을 재귀를 통해 출력한다.
=>3. 자기자신을 출력한다.
이렇게 3가지로 나뉘어집니다.
전위순회의 경우,
void print(Tree* tree) {
if (tree) {
printf("[ %d ] ", tree->data);
print(tree->left);
print(tree->right);
}
}중위순회의 경우,
void print(Tree* tree) {
if (tree) {
print(tree->left);
printf("[ %d ] ", tree->data);
print(tree->right);
}
}후위순회의 경우,
void print(Tree* tree) {
if (tree) {
print(tree->left);
print(tree->right);
printf("[ %d ] ", tree->data);
}
}이렇게 간단하게 표현 할 수 있습니다.
다음으로는 메인으로 들어가서,
int main() {
int inputNum = 0;
scanf_s("%d", &inputNum);
Tree binaryTree[MAX_SIZE];
for (int i = 1; i <= inputNum; i++) {
root = insert(root, i);
binaryTree[i].data = root->data;
binaryTree[i].left = NULL;
binaryTree[i].right = NULL;
root = root->next;
if (i % 2 == 0) {
binaryTree[i / 2].left = &binaryTree[i];
}
else {
binaryTree[i / 2].right = &binaryTree[i];
}
}
print(&binaryTree[1]);
return 0;
}inputNum을 통해 데이터를 넣고자하는 개수를 scanf를 통해 입력 해 주고,
Tree 구조체에 대한 binaryTree[MAX_SIZE] (#define MAX_SIZE 256)
이진트리를 만들것을 선언 해 주고,
for 반복문을 통해 단일연결리스트 root 에 대해서 데이터를 넣어줍니다.
만약에 임의의 입력한 데이터값을 받고싶다면,
for(int i =1; i<=inputNum; i++) {
int key = 0;
scanf("%d",&key);
root = insert(root,key);
}이렇게 조금만 수정해서 받을 수 있습니다.
그 다음에, 이진트리를 하나하나 초기화시켜주기위해서, data값을 root 연결리스트를 통해 받아오고, left 와 right를 다 NULL값으로 만듭니다.
그리고 binaryTree에 대해 다 연결을 해 줍니다.
연결방법은, for문의 i값을 통해서 하였습니다.
이진트리 가 모두 채워지는것을 가정하고 그리면,
이렇게 구성이 됩니다. 그림을 보시면, 왼쪽에 해당되는 노드는 전부 짝수번이라는것을 알 수 있습니다.
그래서 for 반복문 안에 if 조건문 i%2 == 0 이라면 왼쪽에, 아니라면 오른쪽에 연결하는 모습을 볼 수 있습니다.
또한 그림을 보면, 부모노드는 몫연산자를 통해 i/2 번에 있는 노드임을 알 수 있습니다.
예시 1. 10번째 노드를 넣는다고 가정하면, 10번째의 노드의 부모노드는 5임을 알 수 있습니다.
예시 2. 12번째 노드를 넣는다고 가정하면, 12번째의 노드의 부모노드는 6임을 알 수 있습니다.
예시 3. 9번째 노드를 넣는다고 가정하면, 9번째의 노드의 부모노드는 4임을 알 수 있습니다.
그러므로, binaryTree[i / 2] = 해당 노드의 부모노드에 i번째 노드의 값을 왼쪽 또는 오른쪽으로 연결 하는 것 입니다.
마지막으로 풀 코드를 보여드리겠습니다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 256
typedef struct node {
struct node* next;
int data;
int size;
}node;
typedef struct Tree {
node nodes;
struct nodes* input;
struct Tree* left;
struct Tree* right;
int data;
}Tree;
node* root = NULL;
int size = 0;
node* insert(node* root, int data) {
if (root == NULL) {
root = (node*)malloc(sizeof(node));
root->next = NULL;
root->data = data;
size++;
return root;
}
else {
root->next = insert(root->next, data);
return root;
}
}
void print(Tree* tree) {
if (tree) {
printf("[ %d ] ", tree->data);
print(tree->left);
print(tree->right);
}
}
int main() {
int inputNum = 0;
printf("input data num : ");
scanf_s("%d", &inputNum);
Tree binaryTree[MAX_SIZE];
printf("\n");
for (int i = 1; i <= inputNum; i++) {
int key = 0;
printf("%d key : ",i);
scanf_s("%d", &key);
root = insert(root, key);
binaryTree[i].data = root->data;
binaryTree[i].left = NULL;
binaryTree[i].right = NULL;
root = root->next;
if (i % 2 == 0) {
binaryTree[i / 2].left = &binaryTree[i];
}
else {
binaryTree[i / 2].right = &binaryTree[i];
}
}
print(&binaryTree[1]);
}
