이진트리(Binary_Tree) 구현-C

1. BTree.h : 이진트리 자료구조의 헤더파일, ADT

#ifndef BTREE_H
#define BTREE_H
 
#include <stdio.h>
#include <stdlib.h>
 
typedef int BTData;
 
typedef struct  _BTreeNode
{
    BTData data;
    struct _BTreeNode* left;
    struct _BTreeNode* right;
}BTreeNode;
 
typedef void visitFunPtr(BTData data);
 
BTreeNode* makeBTreeNode(void);//노드를 만들고 연결하지는 않음.
BTData getData(BTreeNode* bt);//bt의 데이터를 return.
void setData(BTreeNode* bt, BTData data);//bt->data에 data를 넣어줌.
BTreeNode* getLeftSubTree(BTreeNode* bt);//Left트리의 주소를 return.
BTreeNode* getRightSubTree(BTreeNode* bt);
void makeLeftSubTree(BTreeNode* main, BTreeNode* sub);//sub를 main의 left에 연결.
void makeRightSubTree(BTreeNode* main, BTreeNode* sub);
void postorderTraverse(BTreeNode* bt, visitFunPtr action);//후위
void preorderTraverse(BTreeNode* bt, visitFunPtr action);//전위
void inorderTraverse(BTreeNode* bt, visitFunPtr action);//중위
void deleteTree(BTreeNode* bt);//트리제거
 
 
#endif // !BTREE_H
 

2. BTree.c

#include "BTree.h"
 
/*
makeBTreeNode
노드만 만들고 연결은 하지 않는다.
*/
BTreeNode* makeBTreeNode(void) {
    BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->left = NULL;
    newNode->right = NULL;
 
    return newNode;
 
}
/*
getData
해당 주소의 data를 return
*/
BTData getData(BTreeNode* bt) {
    return bt->data;
}
/*
setData
해당 주소에 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);
    /*만약 연결하려고 하는 노드의 왼쪽이 연결되어있다면,*/
    deleteTree(main->left);
    /*왼쪽 서브트리를 제거한다(후위순회방식)*/
 
    /*그리고 연결한다.*/
    main->left = sub;
 
}
void makeRightSubTree(BTreeNode* main, BTreeNode* sub) {
 
    if (main->right != NULL)
        deleteTree(main->right);
 
    main->right = sub;
 
}
 
void postorderTraverse(BTreeNode* bt, visitFunPtr action) {
    if (bt == NULL)
        return;
    //bt자체를 재귀적으로 각각 루트노드라고 생각한다.
    postorderTraverse(bt->left, action);//노드의 왼쪽 자식노드 방문
    postorderTraverse(bt->right, action);//노드의 오른쪽 자식노드 방문
    action(bt->data);//루트노드 방문
 
}
 
void inorderTraverse(BTreeNode* bt,visitFunPtr action) {//중위순회
    if (bt->left == NULL)
        return;
    
    inorderTraverse(bt->left,action);
    action(bt->data);
    inorderTraverse(bt->right, action);
 
}
 
void preorderTraverse(BTreeNode* bt, visitFunPtr action) {//전위순회
    if (bt == NULL)
        return;
    
    action(bt->data);
    preorderTraverse(bt->left,action);
    preorderTraverse(bt->right,action);
 
}
 
/*
deleteTree
후위순회방식으로 Tree를 삭제한다
메모리 누수 방지를 위해서..
*/
void deleteTree(BTreeNode* bt) {
 
    if (bt == NULL)
        return;
 
    deleteTree(bt->left);
    deleteTree(bt->right);
 
    printf("delete the Node : %d", bt->data);
    free(bt);
 
}
 

(참고 : 자료구조, 윤성우)