[C] C언어로 이진트리를 구현하기 1
학원에서 배운 C로 이진트리를 구현하는 과정을 이 포스트에다가 저장한다.
파이썬과 원리는 같은 것 같다. 다만 클래스 대신 구조체를 선언하는 것이 C언어에서의 포인트.
구현 코드
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996) // 권장되지않는 함수에 대한 에러를 무시함.
// 이진트리의 구현
typedef struct treeNode{
int value;
struct treeNode* left;
struct treeNode* right;
}treeNode;
treeNode* setBinTreeNode(int* arr, int size, int idx);
void displayInorder(treeNode* t);
void displayPreorder(treeNode* t);
void displayPostorder(treeNode* t);
void freeNode(treeNode* t);
void counter(treeNode*t);
void displayInorder_index(treeNode* t, int k);
int sum_tree(treeNode* t);
int count;
int main() {
int arr[9] = {6, 4, 8, 2, 5, 7, 9, 1, 3};
treeNode* root = NULL;
// 배열에서 크기를 구하는 방법.
root = setBinTreeNode(arr, sizeof(arr) / sizeof(int), 0); // 배열이름, 배열의 크기, 첫 번째 인덱스
// 왼쪽 자식 구하기 : 2*idx + 1
// 오른쪽 자식 구하기 : 2*idx + 2
displayInorder(root);
puts("");
displayPreorder(root);
puts("");
displayPostorder(root);
puts("");
counter(root);
printf("노드의 갯수 : %d", count);
puts("");
displayInorder_index(root, 0);
printf("합계: %d\n", sum_tree(root));
freeNode(root);
return 0;
}
// 노드 생성
treeNode* setBinTreeNode(int* arr, int size, int idx) {
// tree 형성
treeNode* curNode = (treeNode*)malloc(sizeof(treeNode)); // 현재 방문 중인 노드를 저장.
int left = 2*idx + 1;
int right = left + 1; // 2*idx + 2 의 값과 같다.
curNode->value = arr[idx];
curNode->left = NULL;
curNode->right = NULL;
if (left < size) {
curNode->left = setBinTreeNode(arr, size, left); // 왼쪽 자식 재귀호출 및 연결
}
if (right < size) {
curNode->right = setBinTreeNode(arr, size, right); // 오른쪽 자식 재귀호출 및 연결
}
// setBinTreeNode가 curNode의 주소를 반환함으로써 연결이 되는 원리.
return curNode;
}
// 중위 순회
void displayInorder(treeNode* t) {
// 중위 순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식
if (t != NULL) {
displayInorder(t->left);
printf("%d ", t->value);
displayInorder(t->right);
}
return;
}
// 중위 순회 중 인덱스 출력
void displayInorder_index(treeNode* t, int k) {
static int counting = 1;
if (t != NULL) {
displayInorder_index(t->left, k);
if(counting == t->value) {
printf("%d번째 인덱스의 값 : %d\n", counting, t->value);
counting++;
}
displayInorder_index(t->right, k);
}
return;
}
// 전위 순회
void displayPreorder(treeNode* t) {
// 전위 순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식
if (t != NULL) {
printf("%d ", t->value); // 부모
displayPreorder(t->left); // 왼쪽 자식
displayPreorder(t->right); // 오른쪽 자식
}
return;
}
// 후위 순회
void displayPostorder(treeNode* t) {
// 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모
if (t != NULL) {
displayPostorder(t->left); // 왼쪽 자식
displayPostorder(t->right); // 오른쪽 자식
printf("%d ", t->value); // 부모
}
return;
}
// 동적 메모리 해제
void freeNode(treeNode* t) {
// 동적 메모리 해제는 후위순회방식으로.
if (t != NULL) {
freeNode(t->left); // 왼쪽 자식
freeNode(t->right); // 오른쪽 자식
printf("%d삭제\n", t->value); // 부모
free(t);
}
}
// 노드의 개수 세기
void counter(treeNode* t) {
if (t != NULL) {
counter(t->left);
counter(t->right);
count++; // count는 전역변수 혹은 static 변수
}
return;
}
// 각 노드에 들어있는 값의 합 구하기
int sum_tree(treeNode* t) {
static int _sum = 0; // static : 사용자 지정 함수 내 전역변수 같은..? 지역 변수?
if (t != NULL) {
sum_tree(t->left);
_sum += t->value;
sum_tree(t->right);
return _sum;
}
}
코드를 작성하다보니 일정한 코드 배열에서 전위, 중위, 후위 순회 여부에 따라서 재귀함수와 취할 액션을 어떤 순서로 배치하냐를 다르게 하면 되는 것을 공부했다.
그림으로 나타내면 아래와 같은 느낌이다.
