이진탐색트리

BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H_ #define BINARY_SEARCH_TREE_H_ #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct tagBSTNode { struct tagBSTNode* Left; struct tagBSTNode* Right; ElementType Data; }BSTNode; BSTNode* CreateNode(ElementType NewData); void DestroyNode(BSTNode* Node); void DestroyTree(BSTNode* Tree); BSTNode* SearchNode(BSTNode* Tree, ElementType Target); BSTNode* SearcMinNode(BSTNode* Tree); void InsertNode(BSTNode* Tree, BSTNode* Child); BSTNode* RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target); void InorderPrintTree(BSTNode* Node); #endif

BinarySearchTree.c

#include "BinarySearchTree.h" BSTNode* CreateNode(ElementType NewData) { BSTNode* NewBSTNode = (BSTNode*)malloc(sizeof(BSTNode)); NewBSTNode->Left = NULL; NewBSTNode->Right = NULL; NewBSTNode->Data = NewData; return NewBSTNode; } void DestroyNode(BSTNode* Node) { free(Node); } void DestroyTree(BSTNode* Tree) { if(Tree->Right != NULL) DestroyTree(Tree->Right); if(Tree->Left != NULL) DestroyTree(Tree->Left); Tree->Left = NULL; Tree->Right = NULL; DestroyNode(Tree); } BSTNode* SearchNode(BSTNode* Tree, ElementType Target) { if(Tree == NULL) return NULL; if(Tree->Data < Target) return SearchNode(Tree->Right, Target); else if(Tree->Data > Target) return SearchNode(Tree->Left, Target); else return Tree; } BSTNode* SearcMinNode(BSTNode* Tree) { if(Tree == NULL) return NULL; if(Tree->Left == NULL) return Tree; else return SearcMinNode(Tree->Left); } void InsertNode(BSTNode* Tree, BSTNode* Child) { if(Tree->Data < Child->Data) { if(Tree->Right == NULL) Tree->Right = Child; else InsertNode(Tree->Right, Child); } else if(Tree->Data > Child->Data) { if(Tree->Left == NULL) Tree->Left = Child; else InsertNode(Tree->Left, Child); } } BSTNode* RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target) { BSTNode* Removed = NULL; BSTNode* MinBSTNode; BSTNode* Temp; if(Tree == NULL) return NULL; if(Tree->Data > Target) RemoveNode(Tree->Left, Tree, Target); else if(Tree->Data < Target) Removed = RemoveNode(Tree->Right, Tree, Target); // 목표 값을 찾은 경우 else { Removed = Tree; // 잎 노드인 경우 바로 삭제 if(Tree->Left == NULL && Tree->Right == NULL) { if(Parent->Left == Tree) Parent->Left = NULL; else Parent->Right = NULL; } // 자식이 있는 노드인 경우 else { // 자식이 양쪽 다 있는 경우 if(Tree->Left != NULL && Tree->Right != NULL) { // 오른쪽 자식의 최소값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킨다. MinBSTNode = SearcMinNode(Tree->Right); RemoveNode(Tree, NULL, MinBSTNode->Data); Tree->Data = MinBSTNode->Data; } // 자식이 한쪽만 있는 경우 else { Temp = NULL; if(Tree->Left != NULL) Temp = Tree->Left; else Temp = Tree->Right; if(Parent->Left == Tree) Parent->Left = Temp; else Parent->Right = Temp; } } } return Removed; } void InorderPrintTree(BSTNode* Node) { if(Node == NULL) return; // 왼쪽 하위 트리 출력 InorderPrintTree(Node->Left); // 루트 노드 출력 printf("%d ", Node->Data); // 오른쪽 하위 트리 출력 InorderPrintTree(Node->Right); }

Test_BinarySearchTree.c

#include "BinarySearchTree.h" int main() { // 노드 생성 BSTNode* Tree = CreateNode(123); BSTNode* Node = NULL; // 트리에 노드 추가 InsertNode(Tree, CreateNode(22)); InsertNode(Tree, CreateNode(9918)); InsertNode(Tree, CreateNode(424)); InsertNode(Tree, CreateNode(17)); InsertNode(Tree, CreateNode(3)); InsertNode(Tree, CreateNode(98)); InsertNode(Tree, CreateNode(34)); InsertNode(Tree, CreateNode(760)); InsertNode(Tree, CreateNode(317)); InsertNode(Tree, CreateNode(1)); // 트리 출력 InorderPrintTree(Tree); printf("\n"); // 특정 노드 삭제 printf("Removing 98...\n"); Node = RemoveNode(Tree, NULL, 98); DestroyNode(Node); InorderPrintTree(Tree); printf("\n"); // 새 노드 삽입 printf("Inserting 111...\n"); InsertNode(Tree, CreateNode(111)); InorderPrintTree(Tree); printf("\n"); // 트리 소멸시키기 DestroyTree(Tree); return 0; }