[ch 08-2] 이진 트리의 구현

[배열 기반과 연결 리스트 기반]

■ 그림(배열 기반 트리)

- 트리가 완성 된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄지기 때문에 연결 리스트보다 탐색이 빠른 이점이 있음

- 노드에 번호가 부여됨

  ※ 인덱스 '0'은 사용해도 문제없으나 인덱스 번호와 노드 번호 매치를 위해 편의상 사용하지 않음

■ 그림(연결 리스트 기반 트리)

- 연결 리스트 구성 형태와 트리 형태와 일치한다는 점

※ 우선 연결 리스트 기반으로 구현. 배열 기반은 '완전 이진 트리의 구조를 갖는 '힙(heap)'이라는 자료구조 구현 시 활용할 예정

[이진 트리의 ADT]

BTreeNode * MakeBTreeNode(void);

- 이진 트리 노드를 생성하여 그 주소 값을 반환

int GetData(BTreeNode * bt);

- 노드에 저장된 데이터를 반환

void SetData(BTreeNode * bt, int data);

- 노드에 데이터를 저장. data로 전달된 값을 저장

BTreeNode * GetLeftSubTree(BTreeNode * bt);

- 왼쪽 서브 트리의 주소 값을 반환

BTreeNode * GetRightSubTree(BTreeNode * bt);

- 오른쪽 서브 트리의 주소 값을 반환

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);

- 'main'으로 전달된 노드에다가 'sub'로 전달된 트리를 왼쪽 서브 트리로 연결

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

- 'main'으로 전달된 노드에다가 'sub'로 전달된 트리를 오른쪽 서브 트리로 연결

[소스 코딩]

■ BinaryTree.h

 
#ifndef BINARYTREE_H_
#define BINARYTREE_H_
 
typedef struct _bTreeNode        // 구조체: 이진 트리를 표현 = 노드
{
    int data;                    // 노드에 저장할 데이터 값
    struct _bTreeNode * left;    // 노드의 왼쪽 서브 트리를 연결할 포인터 변수
    struct _bTreeNode * right;   // 노드의 오른쪽 서브 트리를 연결할 포인터 변수
} BTreeNode;
 
BTreeNode * MakeBTreeNode(void);               // 이진 트리 노드 생성
int GetData(BTreeNode * bt);                   // 노드의 데이터 값 반환
void SetData(BTreeNode * bt, int data);        // 노드에 데이터를 저장
 
BTreeNode * GetLeftSubTree(BTreeNode * bt);    // 노드의 왼쪽 서브 트리의 주소 값을 반환
BTreeNode * GetRightSubTree(BTreeNode * bt);   // 노드의 오른쪽 서브 트리의 주소 값을 반환
 
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);     // 전달 받은 'sub' 노드를 'main' 노드의 왼쪽 서브 트리로 연결
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);    // 전달 받은 'sub' 노드를 'main' 노드의 오른쪽 서브 트리로 연결
 
#endif

■ BinaryTree.c

#include <stdio.h>
#include <stdlib.h>        // malloc, free 함수를 사용하기 위함
#include "BinaryTree.h"
 
// 이진 트리 노드 생성 //
BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}
 
// 노드의 데이터 값 반환 //
int GetData(BTreeNode * bt)
{
    return bt->data;
}
 
// 노드에 데이터를 저장 //
void SetData(BTreeNode * bt, int data)
{
    bt->data = data;
}
 
// 노드의 왼쪽 서브 트리의 주소 값을 반환 //
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}
 
// 노드의 오른쪽 서브 트리의 주소 값을 반환 //
BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}
 
// 전달 받은 'sub' 노드를 'main' 노드의 왼쪽 서브 트리로 연결 //
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
 
    main->left = sub;
}
 
// 전달 받은 'sub' 노드를 'main' 노드의 오른쪽 서브 트리로 연결 //
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
 
    main->right = sub;
}

■ 설명

※ 한줄 코드는 생략

// 이진 트리 노드 생성 //
BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

- 'nd'라는 노드를 동적 메모리로 생성

- 양쪽 서브 트리를 연결할 'left, right'를 'NULL'로 초기화

- 'nd'를 반환

  ※ 노드(nd)는 'BinaryMain.c'에서 포인터 변수에 저장하게 됨

// 전달 받은 'sub' 노드를 'main' 노드의 왼쪽 서브 트리로 연결 //
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
 
    main->left = sub;
}

// 이미 왼쪽에 연결된 서브 트리가 있을 경우

- 해당 서브 트리의 루트 노드를 삭제

  ※ 삭제되는 루트 노드의 하위 노드들은 삭제되지 않음. 나중에 추가하여 구현할 예정

- 새로운 서브 트리를 왼쪽에 연결

// 전달 받은 'sub' 노드를 'main' 노드의 오른쪽 서브 트리로 연결 //
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
 
    main->right = sub;
}

// 이미 왼쪽에 연결된 서브 트리가 있을 경우

- 해당 서브 트리의 루트 노드를 삭제

  ※ 삭제되는 루트 노드의 하위 노드들은 삭제되지 않음. 나중에 추가하여 구현할 예정

- 새로운 서브 트리를 오른쪽에 연결

■ BinaryMain.c

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

■ 실행결과

■ 그림(실행결과 트리 표현)