2016-09-12_조재찬_스터디일지_C언어-이진 트리의 구현과 순회(Traversal)

이진 트리 구현의 예

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
 
typedef int BTData;
 
typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;
 
/*** BTreeNode 관련 연산들 ****/
BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);
 
BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);
 
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);
 
#endif

BinaryTree.c

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
 
BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
 
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}
 
BTData GetData(BTreeNode * bt)
{
    return bt->data;
}
 
void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}
 
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}
 
BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}
 
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
 
    main->left = sub;
}
 
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
 
    main->right = sub;
}
 

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)

{

if(main->left != NULL)

free(main->left);

main->left = sub;

}

위의 함수에서 왼쪽 서브트리가 하나의 노드라면 문제없지만,

그렇지 않다면 나머지 노드는 잃어버리게 되고 메모리 누수로 이어진다.

둘 이상의 노드로 이루어진 서브트리를 완전히 삭제하려면

서브 트리를 구성하는 모든 노드를 대상으로 free함수를 호출해야 한다.

BinaryTreeMain.c

#include <stdio.h>
#include "BinaryTree.h"
 
int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();    
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();    // 노드 bt 1~4 생성
 
    SetData(bt1, 1);    // bt1에 1저장
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);
 
    MakeLeftSubTree(bt1, bt2);    // bt2를 bt1의 왼쪽 자식 노드로
    MakeRightSubTree(bt1, bt3);    // bt3을 bt1의 오른쪽 자식 노드로
    MakeLeftSubTree(bt2, bt4);    // bt4를 bt2의 왼쪽 자식 ㅗ드로
 
    // bt1의 왼쪽 자식 노드의 데이터 출력 
    printf("%d \n",
        GetData(GetLeftSubTree(bt1)));
 
    // bt1의 왼쪽 자식 노드의 왼쪽 자식 노드의 데이터 출력
    printf("%d \n",
        GetData(GetLeftSubTree(GetLeftSubTree(bt1))));
 
    return 0;
}

Output :

2

4

이진 트리의 순회(Traversal)

이진 트리의 순회 방법은 재귀적(recursive)이다.

루트 노드를 방문하는 시점에 따라 세 가지 순회 방법으로 나뉜다.

서브 트리가 존재하는 이진 트리의 중위 순회

// 이진 트리 전체를 중위 순회하는 함수

void InorderTraverse(BTreeNode * bt)

{

if(bt == NULL)    // bt가 NULL이면 재귀 탈출! 

return;

InorderTraverse(bt->left); 

printf("%d \n", bt->data); 

InorderTraverse(bt->right); 

}

재귀함수와 관련된 코드를 이해할 떄는 단순히 거슬러가는것이 아니라,

복사본을 만들고 호출하고 호출된 순서의 역순으로 반환이 이뤄진다고 이해하면 쉽다.

BinaryTreeTraverseMain.c

#include <stdio.h>
#include "BinaryTree.h"
 
void InorderTraverse(BTreeNode * bt)
{
    if(bt == NULL)    // bt가 NULL이면 재귀 탈출! 
        return;
 
    InorderTraverse(bt->left); 
    printf("%d \n", bt->data); 
    InorderTraverse(bt->right); 
}
 
int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();
 
    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);
 
    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);
 
    InorderTraverse(bt1);
    return 0;
}

Output :

4

2

1

3

함수 포인터의 활용

typedef void VisitFuncPtr(BTData data);    // (*VisitFuncPtr)로 대신 가능

void형 포인터는 형 정보가 존재하지 않기에 어떠한 주소값도 저장이 가능하다. (하지만 형정보가 없기에 메모리 접근을 위한 * 연산은 불가능)

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt == NULL)
        return;
 
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

action이 가리키는 함수를 통해 방문 진행

action(bt->data);    // 노드의 방문

VisitFuncPtr 형을 기준으로 정의된 함수

void ShowIntData(int data)

{

printf("%d ", data);

}

action에 전달되는 함수의 내요에 따라 노드의 방문결과가 결정.

위와 같이 data가 전달되면 노드의 방문 결과는 출력(printf)이 된다.

BinaryTreeTraversalAdded.7z

output :

1 2 4 5 3 6

4 2 5 1 3 6

4 5 2 6 3 1

트리의 삭제 함수 정의하기

void DeleteTree(BTreeNode * bt)
{
    if (bt == NULL)
        return;
 
    DeleteTree(bt->left);
    DeleteTree(bt->right);
 
    printf("트리 data 삭제: %d \n", bt->data);
    free(bt);
}

main함수에서는 DeleteTree(bt1); 와 같이 호출한다. 호출되면 bt1이 가리키는 노드를 루트 노드로 하는 트리 전부가 지워된다.

루트 노드가 마지막에 삭제되어야 하기 때문에 반드시 후위순회(Postorder Traversal)의 과정을 거쳐야 한다.

output :

1 2 4 5 3 6

4 2 5 1 3 6

4 5 2 6 3 1

트리 data 삭제: 4

트리 data 삭제: 5

트리 data 삭제: 2

트리 data 삭제: 6

트리 data 삭제: 3

트리 data 삭제: 1