트리 개념 및 구현

트리는 다른 자료구조와 다르게 비선형 자료구조이다. 트리는 가지를 뻗어 나아간다.

트리의 추상 자료형

BTreeNode *MakeBtreeNode(void);

• 이진 트리 노드를 생성하여 그 주소값을 반환한다.

BTData GetData(BTreeNode *bt);

• 노드에 저장된 데이터를 반환한다.

void SetData(BTreeNode *bt, BTData data);

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

BTreeNode *GetLeftSubTree(BTreeNode *bt);

• 왼쪽 서브트리의 주소 값을 반환한다.

BTreeNode *GetRIghtSubTree(BTreeNode *bt);

• 오른쪽 서브트리의 주소 값을 반환한다.

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

• 왼쪽 서브트리를 연결한다.

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

• 오른쪽 서브트리를 연결한다.

트리의 경우 개념과 구현을 같이 보면 좋을 것 같아서 한곳에 정리해본다.

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

#define TRUE    1
#define FALSE   0

typedef int BTData;

typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode *left; // 왼쪽 서브트리를 연결하기위한 변수
    struct _bTreeNode *right; // 오른쪽 서브트리를 연결하기위한 변수
} 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) // intializer
{
    BTreeNode *newNode = (BTreeNode *)malloc(sizeof(BTreeNode));
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

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;
}

BinaryTree.h

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

#include <iostream>

typedef int BTData;

class BTreeNode
{
private:
    BTData data;
    BTreeNode *left;
    BTreeNode *right;
public:
    BTreeNode();
    BTreeNode *MakeBtreeNode();
    BTData GetData();
    void SetData(BTData data);
    BTreeNode *GetLeftSubTree();
    BTreeNode *GetRIghtSubTree();
    void MakeLeftSubTree(BTreeNode *sub);
    void MakeRightSubTree(BTreeNode *sub);
    void RemoveNode();
};

#endif

BinaryTree.cpp

#include "BinaryTree.h"
#include <iostream>

BTreeNode::BTreeNode() // 생성자를 통해 초기화 해준다.
{
    left = NULL;
    right = NULL;
}

// BTreeNode *BTreeNode::MakeBtreeNode() // main에서 직접 메모리를 할당해 줄 것이기 떄문에 
																					// 굳이 만들지 않는다.
// {
//     BTreeNode *bt = new BTreeNode;
//     bt->left = NULL;
//     bt->right = NULL;

//     return bt;
// }

BTData BTreeNode::GetData()
{
    return data;
}
void BTreeNode::SetData(BTData _data)
{
    data = _data;
}
BTreeNode *BTreeNode::GetLeftSubTree()
{
    return left;
}
BTreeNode *BTreeNode::GetRIghtSubTree()
{
    return right;
}
void BTreeNode::MakeLeftSubTree(BTreeNode *sub)
{
    left = sub;
}
void BTreeNode::MakeRightSubTree(BTreeNode *sub)
{
    right = sub;
}

void BTreeNode::RemoveNode()
{
    BTreeNode *dTree = this;
    if (dTree == NULL) 
        return ;
    dTree->GetLeftSubTree()->RemoveNode();
    dTree->GetRIghtSubTree()->RemoveNode();
    std::cout << data << std::endl;
    delete dTree;
}

트리의 출력은 재귀를 통해 이뤄지는데

void printData(BTreeNode *main)
{
    if (main == NULL)
        return ;
    printData(main->left);
    printf("%d ", main->data);
    printData(main->right);
}

전위 중위 후위 순회를 통해구현 할 수 있다. 위의 코드 처럼 말이다. 위 코드는 중위순회를 통해 구현 하였다. 맨 왼쪽 노드로 이동→오른쪽 노드 이동 → 출력 → 메모리 해제 의 방식을 통해 구현했다. 탈출은 노드가 null을 가르키게 되면 탈출 하도록 구현하였다.

void RemoveNode(BTreeNode *main)
{
    if (main == NULL)
        return ;
    RemoveNode(main->left);
    RemoveNode(main->right);
    printf("%d ",main->data);
    free(main);
}

삭제 역시 출력과 마찬가지로 재귀를 사용해서 구현한다.

 

힙 코드: https://boiling-fowl-6d6.notion.site/Heap-e0df3107d7d344c7b02f36b9736a499f