C언어로 이진 트리 논하기

이진 트리는 흔하게 다루는 자료구조이다. 그리고 학부 단위에서 흔하게 직접 구현하는 과제가 주어지곤 한다. 물론 우리도 예외는 아니다. 경험이 있어서 망정이지 이게 처음 받아들일때는 많은 당황스러움과 함께 했던 기억이 난다. 친절하게 안내 할 수 있도록 노력하고 있다.

기본 구현

typedef struct _btnode{
	int item;
	struct _btnode *left;
	struct _btnode *right;
} BTNode;

여기서의 기초 루틴의 작동을 위해 스택을 사용 하게 된다. 다만 여기에서의 Stack은 기존에 봤던 본체는 ll인 형태는 아니다.

뒷 배경

생성에 있어 주로 이용되는 스택의 본체에 대해 논한다.

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

    temp = malloc(sizeof(StackNode));
    if(temp == NULL)
        return;
    // 제대로 배정되지 못한 꼬롬한 애들은 중단한다.
    temp->btnode = node;
    if(stk->top == NULL){
        stk->top = temp;
        temp->next = NULL;
    }
    // 처음 삽입하는 경우는 얘가 즉시 top이 된다.
    else{
        temp->next = stk->top;
        stk->top = temp;
    // 처음 삽입이 아니어도 사실 얘는 top이 된다.
    }
}

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

   top = stk->top;
   if(top != NULL){
        temp = top->next;
        ptr = top->btnode;
		// ptr로 실제 중요한 정보를 갖고 있도록 한다.
        stk->top = temp;
        free(top);
        top = NULL;
        // 그리고 top의 공간을 반환시킨다.
   }
   // top에 아이템이 없다는 것은 이미 비었다는 것이니, 그 경우엔 ptr은 null을 반환한다.
   return ptr;
}

기본적인 삽입, 삭제

BTNode *createBTNode(int item){
    BTNode *newNode = malloc(sizeof(BTNode));
    newNode->item = item;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
    // 그냥 노드를 하나 만든다. 아래에 있는 내용 코드에서 필요하다.
}

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

    stk.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(&stk,root);
    }
    else
    {
        scanf("%c",&s);
    }

    while((temp =pop(&stk)) != 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)
             (&stk,temp->right);
        if(temp->left != NULL)
            push(&stk,temp->left);
    }
    return root;
    // 부모 노드 입력하고, 해당 부모에 대해 좌 우를 입력 시키게끔 하고 있다. 여기서 스택을 쓴다.
}

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;
        // 자기 자신에 대한 free가 후에 이루어져야 자식들에 대한 주소 손실이 없다.
    }
}

---

Quest #1. 두 트리가 주어지면, 완전 같은지 확인하기

int identical(BTNode *tree1, BTNode *tree2)
{
	// 두 트리가 완전 비어있어도 같은거라고 할 수 있다.
    // 이는 재귀를 통해 비어있는것도 같은 처리를 해야하기 때문에 초반부 정의가 필요하다.
    if(tree1 == NULL && tree2 == NULL)
        return 1;
        
    else if(tree1 == NULL || tree2 == NULL)
        return 0;
        // 다만 위의 and를 벗어나놓고 NULL이 있다는건 같진 않다는 것.
    else if(tree1->item != tree2->item)
        return 0;
        // 아이템이 다르면 같지 않은건 당연하다.

    int Lresult = 1;
    int Rresult = 1;
    // 기본 값을 1, 즉 동일하다고 상정한다. 대신에 다른 상황에서 즉시 값 변경이 이루어지면 된다.

    Lresult = identical(tree1->left, tree2->left);
    if(Lresult == 0)
        return 0;
    // 다르면 즉시 끝낸다.

    Rresult = identical(tree1->right, tree2->right);
    if(Rresult == 0)
        return 0;
    // 다르면 즉시 끝낸다.
}

 

Quest #2 : 트리 하나의 최대 깊이 구하기

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int findDeep(BTNode *node, int childCnt)
{
    if(node->left == NULL && node->right == NULL)
        return childCnt;

    int Lresult = -1;
    int Rresult = -1;

    if(node->left != NULL)
        Lresult = findDeep(node->left, childCnt + 1);
    
    if(node->right != NULL)
        Rresult = findDeep(node->right, childCnt + 1);

    return max(Lresult, Rresult);
}


int maxHeight(BTNode *node)

{
    Stack *st = malloc(sizeof(Stack));
    st->top = NULL;
    int isContinue = 1;
    push(st, node);
    int Lresult = 0;
    int Rresult = 0;

    while (isContinue)
    {
        BTNode *poped = pop(st);
        if(poped != NULL)
        {
            Lresult = -1;
            Rresult = -1;
            if(poped->left != NULL)
            {
                push(st, poped->left);
                Lresult = findDeep(poped->left, 1);
            }


            if(poped->right != NULL)
            {
                push(st, poped->right);
                Rresult = findDeep(poped->right, 1);
            }

        }
        else
        {
            isContinue = 0;
        }
    }
    free(st);
    return max(Lresult, Rresult);
    // 저절로 개행 안해주길래 내 재량껏 삽입
}

스택을 쓰지 않는 코드

int maxHeight(BTNode *node)
{
    if(node == NULL)
        return -1;
    
    int isContinue = 1;
    int Lresult = 0;
    int Rresult = 0;
    BTNode *cur;
    cur = node;
        if(cur != NULL)
        {
            Lresult = findDeep(node->left, 1);
            Rresult = findDeep(node->right, 1);
        }
        else
        {
            isContinue = 0;
        }
    return max(Lresult, Rresult);
}

 

findDeep 함수는 그대로 이용이 필요했다. 함수를 한 개로 줄일 수 있을 법 하긴 한데..

Quest #3 : 자식이 단 한 개인 노드의 수 구하기

int countOneChildNodes(BTNode *node)

{
    Stack st;
    st.top = NULL;
    int isContinue = 1;
    int result = 0;
    push(&st, node);
    while (isContinue)
    {
        int ChildCnt = 0;
        BTNode *popItem = pop(&st); 
        if(popItem != NULL)
        {
            if(popItem->left != NULL)
            {
                push(&st, popItem->left);
                ChildCnt++;
            }

            if(popItem->right != NULL)
            {
                push(&st, popItem->right);
                ChildCnt++;
            }
        }
        else
        {
            isContinue = 0;
        }

        if(ChildCnt == 1)
        {
            result++;
        }
    }
    return result;

}

스택을 쓰지 않는 코드

int countOneChildNodes(BTNode *node)
{
    if(node == NULL)
        return 0;
    BTNode *cur;
    cur = node;
    int myCount = 0;
    int Lcount = 0;
    int Rcount = 0;
    Lcount = countOneChildNodes(cur->left);
    Rcount = countOneChildNodes(cur->right);

    if(node->left == NULL && node->right == NULL)
        myCount = 0;
    else if(node->left != NULL && node->right != NULL)
        myCount = 0;
    else
        myCount = 1;


    return myCount + Lcount + Rcount;
}

 

Quest #4. 아이템이 홀수인 노드들의 합

int sumOfOddNodes(BTNode *node)

{
    Stack stack;
    stack.top = NULL;

    int isContinue = 1;
    int result = 0;

    push(&stack, node);

    while (isContinue)
    {
        BTNode *popItem = pop(&stack);
        if(popItem != NULL)
        {
            if(popItem->left != NULL)
            {
                push(&stack, popItem->left);
            }

            if(popItem->right != NULL)
            {
                push(&stack, popItem->right);
            }

            if(popItem->item % 2 == 1)
            {
                result += popItem->item;
            }
        }
        else
        {
            isContinue = 0;
        }
    }
    return result;
}

스택을 쓰지 않는 코드

int sumOfOddNodes(BTNode *node)
{
    if(node == NULL)
        return 0;

    int Lresult = 0;
    int Rresult = 0;
    Lresult = sumOfOddNodes(node->left);
    Rresult = sumOfOddNodes(node->right);

    if(node->item % 2 == 1)
        return node->item + Lresult + Rresult;
    else
        return Lresult + Rresult;
}

 

Quest #5. 자식의 위치 좌우 반전하기

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

    mirrorTree(cur->left);
    mirrorTree(cur->right);

        cur = node->left;
        node->left = node->right;
        node->right = cur;
    
}

 

Quest #6. 주어진 수 보다 적은 수 출력하기

int Compare(int a, int b)
{
    if (a > b)
        return 1;
    else
        return 0;

}


void printSmallerValues(BTNode *node, int m)
{
    if(node == NULL)
        return;
	Stack stack;
    stack.top = NULL;
    int isContinue = 1;
    push(&stack, node);

    while (isContinue)
    {
        BTNode *popedItem = pop(&stack);
        if(popedItem != NULL)
        {
            if(Compare(m, popedItem->item) == 1)
                printf("%d ", popedItem->item);

            if(popedItem->right != NULL)
                push(&stack, popedItem->right);
            
            if(popedItem->left != NULL)
                push(&stack, popedItem->left);
            

        }
        else
        {
            isContinue = 0;
        }
    }
}

스택을 쓰지 않는 코드

void printSmallerValues(BTNode *node, int target)
{
    if(node == NULL)
        return;
    
    if(Compare(target, node->item) == 1)
        printf("%d ", node->item);

    printSmallerValues(node->left, target);
    printSmallerValues(node->right, target);
}

 

Quest #7. 순회 후 최소값 출력

int customCompare(int a, int b)
{
    if (a > b)
        return 1;
    else
        return 0;
}

int smallestValue(BTNode *node)
{
    Stack stack;
    stack.top = NULL;
    if(node == NULL)
        return -1;
	int mostLow = node->item;
    int isContinue = 1;
    
    push(&stack, node);
    // 어디로 가도 다 돌면 되니까 ___order traversal 성향을 타진 않는다.
    while (isContinue)
    {
        BTNode *poped = pop(&stack);
        if(poped != NULL)
        {
            if (customCompare(mostLow, poped->item) == 1)
                mostLow = poped->item;

            if (poped->left != NULL)
                push(&stack, poped->left);
            
            if (poped->right != NULL)
                push(&stack, poped->right);
            
        }
        else
        {
            isContinue = 0;
        }
    }
    return mostLow;

}

스택을 쓰지 않는 코드

int smallestValue(BTNode *node)
{
    if(node == NULL)
        return -1;
    int myValue = node->item;
    int Lresult = INT_MAX;
    int Rresult = INT_MAX;

    if(node->left != NULL)
            Lresult = smallestValue(node->left);
    
    if(node->right != NULL)
            Rresult = smallestValue(node->right);

    return min(myValue, min(Lresult, Rresult));

}

 

 

Quest #8. 자식의 자식의 자식을 가지고 있는 노드 수?

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int findGGChild(BTNode *node, int childCnt)
{
    if(childCnt == 3)
        return 1;

    if(node->left == NULL && node->right == NULL)
        return -1;

    int Lresult = -1;
    int Rresult = -1;

    if(node->left != NULL)
        Lresult = findGGChild(node->left, childCnt + 1);
    
    if(node->right != NULL)
        Rresult = findGGChild(node->right, childCnt + 1);

    return max(Lresult, Rresult);
}

int hasGreatGrandchild(BTNode *node)
{
	Stack *st = malloc(sizeof(Stack));
    st->top = NULL;
    int isContinue = 1;
    push(&st, node);

    while (isContinue)
    {
        BTNode *poped = pop(st);
        if(poped != NULL)
        {
            int Lresult = -1;
            int Rresult = -1;
            if(poped->left != NULL)
            {
                push(st, poped->left);
                Lresult = findGGChild(poped->left, 1);
            }


            if(poped->right != NULL)
            {
                push(st, poped->right);
                Rresult = findGGChild(poped->right, 1);
            }

            if(max(Lresult, Rresult) > 0)
                printf("%d ", poped->item);
        }
        else
        {
            isContinue = 0;
        }
    }
    printf("\n");
    free(st);
    // 저절로 개행 안해주길래 내 재량껏 삽입
}

 

스택을 쓰지 않는 코드

int hasGreatGrandchild(BTNode *node)
{
    if(node == NULL)
        return 0;
    
    BTNode *Lcur = node->left;
    BTNode *Rcur = node->right;
    int Lcount = 0;
    int Rcount = 0;

        Lcount = hasGreatGrandchild(Lcur);
        Lcount++;

        Rcount = hasGreatGrandchild(Rcur);
        Rcount++;

    int total = max(Lcount, Rcount);
    if(total > 3)
        printf("%d ", node->item);
    
    return total;

}

 

 

특정한 자료구조 만드는데 있어 다른 자료구조를 쓰는 것이 뭔가 맥락에 안맞다는 생각이 들어서 스택 없이 작동하는 코드까지 작성했다.  왜냐하면 연결 리스트 - 큐 스택 - 트리 형태로 배우는게 일반적이라고 알려져 있지만 누군가에겐 아닐 수도 있는 것이다. 이런 말하기엔 기본 삽입 삭제에 스택을 쓰네 흠

그래도 전체적으로 순회는 스택 없이도 할 수 있다는 점에서 코드 재구성은 의미 있는 시간이었다.