오늘의 문제는 이진트리 문제이다. C언어를 조금씩 하면서 파이썬으로 알고리즘을 할 때 이해가 잘 가지 않았던 부분이 몬가 이해가 좀 더 잘되는 느낌이다.

문제는 트리에 있는 최솟값을 출력하는 함수를 작성하는 것이다. 아래와 같이 문제가 있다.

Binary Tree - smallestValue() 함수 구현

문제 설명

주어진 이진 트리에서 가장 작은 값을 반환하는 C 함수를 작성하시오.

함수 프로토타입

int smallestValue(BTNode *node);

함수 작성 아이디어

• 현재 노드가 NULL이면 INT_MAX를 리턴하는 기저 조건을 작성한다.(<limit.h> 헤더에 include)
  • 리턴값이 INT_MAX인 이유는 리턴 값을 0을 해놓으면 항상 최솟값이 0이 되버리게 리턴하기 때문에 int 자료형의 제일 큰 수를 리턴값으로 보내 해당 문제를 방지한다.
• 왼쪽과 오른쪽의 서브 트리를 순회하게 재귀 함수를 호출하고
• 현재 값은 현재의 노드 값으로 선언한다.
• 만약 왼쪽 값이 현재 값보다 작으면 현재 값을 왼쪽 값으로 업데이트
• 오른쪽 값이 현재 값보다 작으면 현재 값을 오른쪽 값으로 업데이트
• 같으면 현재 값을 리턴한다.

smallestValue() 함수

int smallestValue(BTNode *node)
{
    // <limits.h> 헤더 추가해서 INT_MAX 사용
    // INT_MAX -> INT의 수 중 가장 큰 수
    // 리턴을 0이 아니라 큰 수로 하는 이유 리턴 시 0을 리턴하게되면 0이 가장 작은 값이 되버려서 최솟값은 항상 0이 나오기 때문
    // 기저 조건
    if (node == NULL) return INT_MAX;

    // 왼쪽 서브 트리 재귀
    int leftMin = smallestValue(node->left);
    // 오른쪽 서브 트리 재귀
    int rightMin = smallestValue(node->right);
    // 현재 작은 값은 현재 노드의 값 
    int currentMin = node->item;

    // 왼쪽에 있는 값이 현재 값보다 작을 때
    if (leftMin < currentMin) {
        currentMin = leftMin;
    }
    // 오른쪽에 있는 값이 현재 값보다 작을 때 
    if (rightMin < currentMin) {
        currentMin = rightMin;
    }
    
    // 현재 작은 값 리턴
	return currentMin;
}

전체 코드

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section E - Binary Trees Questions
Purpose: Implementing the required functions for Question 7 */

//////////////////////////////////////////////////////////////////////////////////

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

#include <limits.h>

//////////////////////////////////////////////////////////////////////////////////

typedef struct _btnode
{
    int item;
    struct _btnode *left;
    struct _btnode *right;
} BTNode;   // You should not change the definition of BTNode

/////////////////////////////////////////////////////////////////////////////////

typedef struct _stackNode
{
    BTNode *btnode;
    struct _stackNode *next;
} StackNode;

typedef struct _stack
{
    StackNode *top;
} Stack;


///////////////////////// Function prototypes ////////////////////////////////////

// You should not change the prototypes of these functions
int smallestValue(BTNode *node);

BTNode *createBTNode(int item);

BTNode *createTree();
void push( Stack *stack, BTNode *node);
BTNode* pop(Stack *stack);

void printTree(BTNode *node);
void removeAll(BTNode **node);

///////////////////////////// main() /////////////////////////////////////////////

int main()
{
    char e;
    int c, value;
    BTNode *root;

    c = 1;
    root = NULL;

    printf("1: Create a binary tree.\n");
    printf("2: Smallest value;\n");
    printf("0: Quit;\n");


    while(c != 0)
    {
        printf("Please input your choice(1/2/0): ");
        if( scanf("%d",&c) > 0)
        {
            switch(c)
            {
            case 1:
                removeAll(&root);
                root = createTree();
                printf("The resulting binary tree is: ");
                printTree(root);
                printf("\n");
                break;
            case 2:
                value = smallestValue(root);
                printf("Smallest value of the binary tree is: %d\n",value);
                removeAll(&root);
                break;
            case 0:
                removeAll(&root);
                break;
            default:
                printf("Choice unknown;\n");
                break;
            }
        }
        else
        {
            scanf("%c",&e);
        }

    }
    return 0;
}

//////////////////////////////////////////////////////////////////////////////////

int smallestValue(BTNode *node)
{
    // <limits.h> 헤더 추가해서 INT_MAX 사용
    // INT_MAX -> INT의 수 중 가장 큰 수
    // 리턴을 0이 아니라 큰 수로 하는 이유 리턴 시 0을 리턴하게되면 0이 가장 작은 값이 되버려서 최솟값은 항상 0이 나오기 때문
    // 기저 조건
    if (node == NULL) return INT_MAX;

    // 왼쪽 서브 트리 재귀
    int leftMin = smallestValue(node->left);
    // 오른쪽 서브 트리 재귀
    int rightMin = smallestValue(node->right);
    // 현재 작은 값은 현재 노드의 값 
    int currentMin = node->item;

    // 왼쪽에 있는 값이 현재 값보다 작을 때
    if (leftMin < currentMin) {
        currentMin = leftMin;
    }
    // 오른쪽에 있는 값이 현재 값보다 작을 때 
    if (rightMin < currentMin) {
        currentMin = rightMin;
    }
    
    // 현재 작은 값 리턴
	return currentMin;
}

//////////////////////////////////////////////////////////////////////////////////

BTNode *createBTNode(int item)
{
    BTNode *newNode = malloc(sizeof(BTNode));
    newNode->item = item;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//////////////////////////////////////////////////////////////////////////////////


BTNode *createTree()
{
    Stack stack;
    BTNode *root, *temp;
    char s;
    int item;

    stack.top = NULL;
    root = NULL;
    printf("Input an integer that you want to add to the binary tree. Any Alpha value will be treated as NULL.\n");
    printf("Enter an integer value for the root: ");
    if(scanf("%d",&item) > 0)
    {
        root = createBTNode(item);
        push(&stack,root);
    }
    else
    {
        scanf("%c",&s);
    }

    while((temp =pop(&stack)) != NULL)
    {

        printf("Enter an integer value for the Left child of %d: ", temp->item);

        if(scanf("%d",&item)> 0)
        {
            temp->left = createBTNode(item);
        }
        else
        {
            scanf("%c",&s);
        }

        printf("Enter an integer value for the Right child of %d: ", temp->item);
        if(scanf("%d",&item)>0)
        {
            temp->right = createBTNode(item);
        }
        else
        {
            scanf("%c",&s);
        }

        if(temp->right != NULL)
            push(&stack,temp->right);
        if(temp->left != NULL)
            push(&stack,temp->left);
    }
    return root;
}

void push( Stack *stack, BTNode *node)
{
    StackNode *temp;

    temp = malloc(sizeof(StackNode));
    if(temp == NULL)
        return;
    temp->btnode = node;
    if(stack->top == NULL)
    {
        stack->top = temp;
        temp->next = NULL;
    }
    else
    {
        temp->next = stack->top;
        stack->top = temp;
    }
}

BTNode* pop(Stack *stack)
{
    StackNode *temp, *top;
    BTNode *ptr;
    ptr = NULL;

    top = stack->top;
    if(top != NULL)
    {
        temp = top->next;
        ptr = top->btnode;

        stack->top = temp;
        free(top);
        top = NULL;
    }
    return ptr;
}

void printTree(BTNode *node)
{
    if(node == NULL) return;

    printTree(node->left);
    printf("%d ",node->item);
    printTree(node->right);
}

void removeAll(BTNode **node)
{
    if(*node != NULL)
    {
        removeAll(&((*node)->left));
        removeAll(&((*node)->right));
        free(*node);
        *node = NULL;
    }
}