연결 리스트, 이진 트리에 관한 개념 설명이 없는 글입니다.
오직 코드를 통한 구현에 초점을 맞춘 글입니다.

연결 리스트로의 기본 구현

기본 설정

이러한 형태로 연결 리스트로 구현을 해보고자 합니다.

typedef int BData;

typedef struct _bTreeNode {
    BData item;
    struct _bTreeNode* left_child;
    struct _bTreeNode* right_child;
} BTreeNode;

간단하죠? 왼쪽과 오른쪽 자식 노드는 자기 참조 구조체를 이용해 만듭니다.

트리로 만들어보기

구조체를 완성했으니 이번에는 트리로 만들어 보겠습니다.

이러한 모양의 이진 트리를 만들어 보고자 합니다.

int main() {
    BTreeNode* n1 = (BTreeNode *)malloc(sizeof(BTreeNode));
    BTreeNode* n2 = (BTreeNode *)malloc(sizeof(BTreeNode));
    BTreeNode* n3 = (BTreeNode *)malloc(sizeof(BTreeNode));

    n1->item = 10;
    n1->left_child = n2;
    n1->right_child = NULL;

    n2->item = 10;
    n2->left_child = n2;
    n2->right_child = NULL;

    n3->item = 10;
    n3->left_child = n2;
    n3->right_child = NULL;

    free(n1), free(n2), free(n3);
    return 0;
}

이 또한 매우 직관적인 형태로 코드 작성이 가능합니다. 노드 세 개를 선언해주고 각 노드의 요소, 자식 노드들이 뭔지만 연결 해주면 끝입니다.

메소드 만들어보기

노드의 생성, 삭제 등등.. 이 가능한 메소드를 한 번 만들어 보겠습니다.

// 새로운 노드를 만듭니다.
BTreeNode* createNode(BData item);
// 노드를 삭제합니다.
void DeleteNode(BTreeNode* node);

// 루트 노드를 왼쪽 노드에 연결합니다.
void CreateLeftSubtree(BTreeNode* root, BTreeNode* left);
// 루트 노드를 오른쪽 노드에 연결합니다.
void CreateRightSubtree(BTreeNode* root, BTreeNode* right);

CreateNode - 노드 생성

BTreeNode* CreateNode(BData item) {
    BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
    node->item = item;
    node->left_child = NULL;
    node->right_child = NULL;
    
    return node;
}

DeleteNode - 노드 삭제

void DeleteNode(BTreeNode *node) {
    free(node);
}

CreateLeftSubtree - 루트와 왼쪽 자식 노드 연결

void CreateLeftSubtree(BTreeNode* root, BTreeNode* left) {
    if (root->left_child != NULL)
        exit(1);
    
    root->left_child = left;
}

여기서 root는 곧 parent로 이해해도 좋습니다. left는 left child node를 말 하는 것입니다.

CreateRightSubtree - 루트와 오른쪽 자식 노드 연결

void CreateRightSubtree(BTreeNode* root, BTreeNode* right) {
    if (root->right_child != NULL)
        exit(1);

    root->right_child = right;
}

실습해보기

int main() {
    BTreeNode* n1 = CreateNode(1);
    BTreeNode* n2 = CreateNode(2);
    BTreeNode* n3 = CreateNode(3);
    BTreeNode* n4 = CreateNode(4);
    BTreeNode* n5 = CreateNode(5);
    BTreeNode* n6 = CreateNode(6);

    // level 1
    CreateLeftSubtree(n1, n2);
    CreateRightSubtree(n1, n3);
    
    // level 2
    CreateLeftSubtree(n2, n4);
    CreateLeftSubtree(n2, n5);
    CreateLeftSubtree(n3, n6);
    
    DeleteNode(n1);
    DeleteNode(n2);
    DeleteNode(n3);
    DeleteNode(n4);
    DeleteNode(n5);
    DeleteNode(n6);
    
    return 0;
}