이진 트리 소스 코드 (삽입, 삭제, 탐색, 순회)

< main.cpp >

#include <stdio.h>
#include <iostream>
#include "BinaryTree.h"
 
using namespace std;
 
BTreeNode *tree[1000] = { NULL, };
extern int chkTree;
extern int findNode;
 
 
int main()
{
    int num, value;
 
    while (1)
    {
        cout << "1.삽입\n2.삭제\n3.탐색\n4.전위 순회\n5.중위 순회\n6.후위 순회\n7.종료\n";
        cout << "번호를 입력하세요 :: "; cin >> num;
 
        switch (num)
        {
            case 1: cout << "삽입 할 값을 입력하세요 :: "; cin >> value; chkTree = 1; MakeSubTree(value); break;
            case 2: DelTree(); break;
            case 3:
                cout << "탐색 할 값을 입력하세요 :: "; cin >> value; 
                PreTraverseSearch(tree[0], value);
                if (findNode == 1)
                {
                    cout << "탐색 값이 존재합니다." << endl;
                    findNode = 0;
                }
                else
                    cout << "탐색 값이 존재하지 않습니다." << endl;
                
                cout << endl; 
                break;
 
            case 4:    PreorderTraverse(tree[0], ShowData); cout << endl; break;
            case 5: InorderTraverse(tree[0], ShowData); cout << endl; break;
            case 6: PostorderTraverse(tree[0], ShowData); cout << endl; break;
            case 7: exit(0);
        }
    }
    
 
    return 0;
}

< BinaryTree.cpp >

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
 
/*
함수들의 실제 내용을 적어 놓은 곳
*/
 
extern BTreeNode *tree[1000];
 
int f = 0, b = 1;
int cnt = 1;
int chkTree;
int findNode = 0;
 
BTreeNode *MakeBTreeNode(void)
{
    BTreeNode *nd = (BTreeNode *)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}
 
void ShowData(int data)
{
    printf("%d ", data);
}
 
 
void PreTraverseSearch(BTreeNode *bt, int value)
{
    if (bt == NULL)
        return ;
 
    if (bt->data == value)
    {
        findNode = 1;
    }
 
    PreTraverseSearch(bt->left, value);
    PreTraverseSearch(bt->right, value);
}
 
void DelTree()
{
    if (chkTree == 0)
    {
        printf("Tree가 존재하지 않습니다.\n");
        return;
    }
    else if (b == 1)
    {
        printf("Root 노드 %d 를 지웁니다.\n",tree[0]->data);
        tree[0]->left = NULL;
        tree[0]->right = NULL;
        tree[0]->data = NULL;
        tree[0] = NULL;
        free(tree[0]);
        chkTree = 0;
    }
    else if (cnt % 2 == 0)
    {
        chkTree = 1;
        if (tree[f]->right == tree[b - 1])
        {
            printf("오른쪽 %d 를 지웁니다. 현재 이것의 부모 노드는 %d 입니다.\n", tree[b - 1]->data,tree[f]->data);
            tree[f]->right = NULL;
            free(tree[b - 1]);
            b--;
        }
 
        else if (tree[f]->left == tree[b - 1])
        {
            printf("왼쪽 %d 를 지웁니다. 현재 이것의 부모 노드는 %d 입니다.\n", tree[b - 1]->data,tree[f]->data);
            tree[f]->left = NULL;
            free(tree[b - 1]);
 
            b--;
            f--;
        }
 
    }
    else if (cnt % 2 == 1)
    {
        chkTree = 1;
        if (tree[f - 1]->right == tree[b - 1])
        {
            printf("오른쪽 %d 를 지웁니다. 현재 이것의 부모 노드는 %d 입니다.\n", tree[b - 1]->data, tree[f-1]->data);
            tree[f - 1]->right = NULL;
            free(tree[b - 1]);
            b--;
        }
 
        else if (tree[f - 1]->left == tree[b - 1])
        {
            printf("왼쪽 %d 를 지웁니다. 현재 이것의 부모 노드는 %d 입니다.\n", tree[b - 1]->data, tree[f-1]->data);
            tree[f - 1]->left = NULL;
            free(tree[b - 1]);
 
            b--;
            f--;
        }
    }
 
}
void MakeSubTree(int value)
{
    if (tree[0] == NULL) // tree[0] == root
    {
        tree[0] = MakeBTreeNode();
        SetData(tree[0], value);
    }
    else
    {
        tree[b] = MakeBTreeNode();
        SetData(tree[b], value);
                
        if (cnt % 2 == 1)
        {
            MakeLeftSubTree(tree[f], tree[b]);
            cnt++;
            b++;
        }
 
        else if (cnt % 2 == 0)
        {
            MakeRightSubTree(tree[f], tree[b]);
            cnt++;
            f++;
            b++;
        }
    }
}
 
void SetData(BTreeNode *bt, BTData data)
{
    bt->data = data;
}
 
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 PreorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;
 
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}
 
void InorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;
 
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}
 
void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;
 
    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

< BinaryTree.h >

#pragma once
 
/*
구조체 및 함수들에 대한 정의를 수록
*/
typedef int BTData;
 
typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode *left;
    struct _bTreeNode *right;
}BTreeNode;
 
BTreeNode *MakeBTreeNode(void);
void MakeSubTree(int value);
void DelTree();
 
void SetData(BTreeNode *bt, BTData data);
 
 
void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);
 
typedef void VisitFuncPtr(BTData data); // == void (*VisitFuncPtr)(BTData data);
void ShowData(int data);
 
void PreorderTraverse(BTreeNode *bt, VisitFuncPtr action); // 전위 순회
void InorderTraverse(BTreeNode *bt, VisitFuncPtr action); // 중위 순회
void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action); // 후위 순회
void PreTraverseSearch(BTreeNode *bt, int value);

일단 널리 알려진 이진 탐색 트리와는 다르다는 것을 명시하고자 한다.

이 코드는 어떤 값에도 관계없이 순서대로 노드에 값이 달린다.

그에 관한 코드는 http://www.crocus.co.kr/350 에서 사용한 코드를 응용하였다.

즉 배열 포인터로 만들어서 이용하였다. (배열 포인터 = 이중 포인터)

앞서 설명된 이진 트리의 개념을 기반으로 모든 것을 작성하였기에, 게시글들의 내용을 읽는다면 해석하기 쉬울 것이다.

(필자 또한 자료구조를 공부하고 있는 상태이다.)

그리고 각 순회에 action이라는 함수 포인터가 있는데, 이것을 이용하기 싫다면

printf("%d ", bt->data);를 이용하여도 무방하다.

삭제 및 삽입 구현과정에서 f, b, cnt라는 변수를 이용하였는데 f는 현재 노드 바로 위의 노드를 의미한다.(각각의 부모노드) 

b는 현재 노드를 의미하고, cnt는 그다음 트리에 달릴 노드가 왼쪽인지 오른쪽인지 구분하는 과정에서 이용하였다. 

탐색의 경우에는 전위 순회방식을 이용하여 탐색하도록 만들었다. 

전위, 중위, 후위 순회는 하나의 전위 순회 코드를 작성하여 순서를 바꾸며 전위, 중위, 후위 순회를 만들었다.