#pragma once
#ifndef BST_H
#define BST_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 Data);
void DestroyNode(BSTNode* Node);
void DestroyTree(BSTNode* Tree);
BSTNode* SearchNode(BSTNode* Tree, ElementType Target);
BSTNode* SearchMinNode(BSTNode* Tree);
void InsertNode(BSTNode* Tree, BSTNode* Child);
BSTNode* RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target);
void PrintInorderTree(BSTNode* Node);
#endif
===========================================================================
//.h 만들기
//왼쪽 자식 노드는 나보다 작고, 오른쪽 자식 노드는 나보다 크다.
#include "BST.h"
BSTNode* CreateNode(ElementType NewData) {
BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
NewNode->Data = NewData;
NewNode->Left = NULL;
NewNode->Right = NULL;
return NewNode;
}
void DestroyNode(BSTNode* Node) {
free(Node);
}
void DestroyTree(BSTNode* Tree) {
if (Tree->Right != NULL)
DestroyTree(Tree->Left);
if (Tree->Left != NULL)
DestroyTree(Tree->Right);
Tree->Left = NULL;
Tree->Right = NULL;
DestroyNode(Tree);
}
BSTNode* SearchNode(BSTNode* Tree, ElementType Target){
if (Tree == NULL)
return NULL;
if (Tree->Data == Target) {
return Tree;
}
else if (Tree->Data > Target) {
return SearchNode(Tree->Left, Target);
}
else return SearchNode(Tree->Right, Target);
}
BSTNode* SearchMinNode(BSTNode* Tree){
if (Tree == NULL)
return NULL;
if (Tree->Left == NULL)
return Tree;
else return SearchMinNode(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;
if (Tree->Data > Target)
Removed = RemoveNode(Tree->Left, Tree, Target);
else if (Tree->Data < Target)
Removed = RemoveNode(Tree->Right, Tree, Target);
else {
Removed = Tree;
//leaf 노드인 경우
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)
{
//오른쪽 트리의 최소값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킨다.
BSTNode* MinNode = SearchMinNode(Tree->Right);
MinNode = RemoveNode(Tree, NULL, MinNode->Data);
Tree->Data = MinNode->Data;
}
else {
//자식이 하나인 경우
BSTNode* 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);
}
void 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");
Node = RemoveNode(Tree, NULL, 98);
DestroyNode(Node);
InorderPrintTree(Tree);
printf("\n");
//특정 노드 삽입
printf("Inserting 111...\n");
InsertNode(Tree, CreateNode(111));
InorderPrintTree(Tree);
printf("\n");
system("pause");
}
===========================================================================
//출력
댓글 없음:
댓글 쓰기