[자료구조] 트리 c

배열을 complete binary tree로 변환

#include <stdio.h>
#include <stdlib.h>

#pragma warning (disable : 4996)

#define ARR_SIZE 9
typedef struct treeNode
{
    int value;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;

treeNode* createBinaryTree(int* arr, int parentIdx, int maxSize);
void displayInorder(treeNode* t);
void displayPreorder(treeNode* t);
void displayPostorder(treeNode* t);
void memoryFree(treeNode* t);
int getSumTreeNode(treeNode* t);
int getCountTreeNode(treeNode* t);
int searchKValue(treeNode* t, int k);

void fun()
{
    //프로그램 실행 시 단 한반만 메모리가 할당되어 초기화 된다.
    //정적 변수의 값은 계속 프로그램 종료시까지 유지된다.
    static int a = 0; //정적 변수
    a++;
    printf("%d\n", a);
}

int main()
{
   fun();
   fun();
   fun();

    int arr[ARR_SIZE]= {6, 4, 8, 2, 5, 7, 9, 1, 3};

    treeNode* root = NULL; //최상위 부모 노드

    //배열을 complete binary tree로 생성
    //createBinaryTree함수: 트리를 생성 후, 루트의 주소를 리턴
    root = createBinaryTree(arr, 0, ARR_SIZE); //배열이름, 루트로 쓸 첨자, 배열의 최대 크기

    printf("중위 순회 출력: ");
    displayInorder(root);
    puts("");

    printf("전위 순회 출력: ");
    displayPreorder(root);
    puts("");

    printf("후위 순회 출력: ");
    displayPostorder(root);
    puts("");

    printf("노드의 합은 %d입니다.\n", getSumTreeNode(root));
    printf("노드의 개수는 %d입니다.\n", getCountTreeNode(root));

    int k;
    printf("중위 순회 시 몇 번째 노드의 값을 출력 하시겠습니까? ");
    scanf("%d", &k);

    printf("중위 순회시 %d번째 노드의 값은 %d입니다.\n", k, searchKValue(root, k));

    memoryFree(root);
    return 0;

}

treeNode* createBinaryTree(int* arr, int parentIdx, int maxSize)
{
    int leftIdx = 2 * parentIdx + 1; //왼쪽 자식의 인덱스
    int rightIdx = leftIdx + 1;
    treeNode* newNode;

    newNode = (treeNode*)malloc(sizeof(treeNode));
    newNode->value = arr[parentIdx];
    newNode->left = NULL;
    newNode->right = NULL;

    if(leftIdx < maxSize) //재귀호출의 종료 조건
        newNode->left = createBinaryTree(arr, leftIdx, maxSize); //왼쪽 자식을 만들기 위한 재귀호출

    if(rightIdx < maxSize)
        newNode->right = createBinaryTree(arr, rightIdx, maxSize); //오른쪽 자식을 만들기 위한 재귀호출

    return newNode; //리턴시 부모와 자식이 연결
}

void displayInorder(treeNode* t)
{
    //중위 순회
    if (t != NULL)
    {
        displayInorder(t->left); //왼쪽 재귀호출
        printf("%d ", t->value);
        displayInorder(t->right); //오론쪽 재귀호출
    }
}

void displayPreorder(treeNode* t)
{
    //전위 순회
    if (t != NULL)
    {
        printf("%d ", t->value);
        displayPreorder(t->left);//왼쪽 재귀호출
        displayPreorder(t->right);//오른쪽 재귀호출
    }
}

void displayPostorder(treeNode* t)
{
    //후위 순회
    if (t != NULL)
    {
        displayPostorder(t->left);// 왼쪽 재귀호출
        displayPostorder(t->right);//오론쪽 재귀호출
        printf("%d ", t->value);
    }
}

void memoryFree(treeNode* t)
{
    //후위 순회 방식으로 돌면서 메모리 제거
    //후위 순회
    if (t != NULL)
    {
        memoryFree(t->left);// 왼쪽 재귀호출
        memoryFree(t->right);//오론쪽 재귀호출
        printf("%d노드 제거\n", t->value);
        free(t);
    }
}

int getSumTreeNode(treeNode* t)
{
    //프로그램 실행 시 단 한번만 메모리가 할당되어 초기화 된다.
    //재귀 호출 시 메모리 할당 x => 변하는 값을 유지
    static int sum = 0; //정적변수
    int sum1 = 0, sum2 = 0;
    //후위 순회
    if (t != NULL)
    {
        /*
        sum1 = sum1 + getSumTreeNode(t->left);// 왼쪽 재귀호출
        sum2 = sum2 + getSumTreeNode(t->right);//오론쪽 재귀호출
        sum = sum1 + sum2 + t->value;
        return sum;
         */

        return getSumTreeNode(t->left) + getSumTreeNode(t->right)+ t->value;
    }

    return 0; //NULL인 경우 0리턴
}

int getCountTreeNode(treeNode* t)
{

    /*
     if (t != NULL)
    {
        return getCountTreeNode(t->left) + getCountTreeNode(t->right)+ 1;
    }

    return 0; //NULL인 경우 0 리턴
     */
    static int count = 0;

    if (t != NULL)
    {
        getCountTreeNode(t->left); //왼쪽 재귀호출
        getCountTreeNode(t->right); //오른쪽 재귀호출
        ++count;; //순회하는 횟수 == 개수
    }

    return count;
}

int searchKValue(treeNode* t, int k)
{
    //중위 순회시 k번째 값을 리턴
    //if(k <= 0 || k > getCountTreeNode(t)) //k > 노드의 개수보다 크다면?
    //    return -1;

    static int count = 0;
    int result;
    //중위 순회
    if (t != NULL)
    {
        result = searchKValue(t->left, k); //왼쪽 재귀호출

        if(result != -1)
            return result;

        ++count;

        if(count == k)
            return t->value;
        return searchKValue(t->right, k); //오론쪽 재귀호출
    }

    return -1;
}