이진 탐색

Score.h

#pragma once

typedef struct {
	int number;
	double score;
} Score;

Score DataSet[] =
{
	/* 번호, 점수*/
	1, 877.88,
	2, 176.23,
	3, 365.92,
	4, 162.44,
	5, 148.86,
	6, 89.74,
	7, 342.52,
	8, 811.02
};

 

BinarySearch.c

#include <stdlib.h>
#include <stdio.h>
#include "Score.h"

Score* BinarySearch(Score ScoreList[], int Size, double Target) {
	int Left, Right, Mid;

	Left = 0;
	Right = Size - 1;

	while (Left <= Right) {
		Mid = (Left + Right) / 2;

		if (Target == ScoreList[Mid].score) {
			return &(ScoreList[Mid]);
		}
		else if (Target > ScoreList[Mid].score) {
			Left = Mid + 1;
		}
		else {
			Right = Mid - 1;
		}
	}

	return NULL;
}

int CompareScore(const void* _elem1, const void* _elem2) {
	Score* elem1 = (Score*)_elem1;
	Score* elem2 = (Score*)_elem2;

	if (elem1->score > elem2->score)
		return 1;
	else if (elem1->score < elem2->score)
		return -1;
	else
		return 0;
}

int main() {
	int Length = sizeof(DataSet) / sizeof(DataSet[0]);

	int i = 0;
	Score* found = NULL;

	/* 점수의 오름차순으로 정렬 */
	qsort((void*)DataSet, Length, sizeof(Score), CompareScore);

	/* 671.78 점을 받은 학생 찾기 */
	found = BinarySearch(DataSet, Length, 162.44);

	printf("found : %d %f \n", found->number, found->score);

	return 0;
}

BinarySearchTree.h

#pragma once

#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*	BST_CreateNode(ElementType NewData);
void		BST_DestroyNode(BSTNode* Node);
void		BST_DestroyTree(BSTNode* Tree);

BSTNode*	BST_SearchNode(BSTNode* Tree, ElementType Target);
BSTNode*	BST_SearchMinNode(BSTNode* Tree);
void		BST_InsertNode(BSTNode* Tree, BSTNode *Child);
BSTNode*	BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target);
void		BST_InorderPrintTree(BSTNode* Node);

#endif

BinarySearchTree.c

#include "BinarySearchTree.h"

BSTNode* BST_CreateNode(ElementType NewData) {
	BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

void BST_DestroyNode(BSTNode* Node) {
	free(Node);
}

void BST_DestroyTree(BSTNode* Tree) {
	if (Tree->Right != NULL)
		BST_DestroyTree(Tree->Right);
	if (Tree->Left != NULL)
		BST_DestroyTree(Tree->Left);

	Tree->Left = NULL;
	Tree->Right = NULL;

	BST_DestroyNode(Tree);
}

BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target) {
	if (Tree == NULL)
		return NULL;

	if (Tree->Data == Target)
		return Tree;
	else if (Tree->Data > Target)
		return BST_SearchNode(Tree->Left, Target);
	else
		return BST_SearchNode(Tree->Right, Target);
}

BSTNode* BST_SearchMinNode(BSTNode* Tree) {
	if (Tree == NULL)
		return NULL;

	if (Tree->Left == NULL)
		return Tree;
	else
		return BST_SearchMinNode(Tree->Left);
}

void BST_InsertNode(BSTNode* Tree, BSTNode* Child) {
	if (Tree->Data < Child->Data) {
		if (Tree->Right == NULL)
			Tree->Right = Child;
		else
			BST_InsertNode(Tree->Right, Child);
	}
	else if (Tree->Data > Child->Data) {
		if (Tree->Left == NULL)
			Tree->Left = Child;
		else
			BST_InsertNode(Tree->Left, Child);
	}
}

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target) {
	BSTNode* Removed = NULL;

	if (Tree == NULL)
		return NULL;

	if (Tree->Data < Target)
		BST_RemoveNode(Tree->Right, Tree, Target);
	else if (Tree->Data > Target)
		BST_RemoveNode(Tree->Left, 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) {
				BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
				Removed = BST_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 BST_InorderPrintTree(BSTNode* Node) {
	if (Node == NULL)
		return;

	/* 왼쪽 하위 트리 출력 */
	BST_InorderPrintTree(Node->Left);

	/* 루트 노트 출력 */
	printf("%d ", Node->Data);

	/* 오른쪽 하위 트리 출력 */
	BST_InorderPrintTree(Node->Right);
}

int main() {
	/* 노드 생성 */
	BSTNode* Tree = BST_CreateNode(123);
	BSTNode* Node = NULL;

	/* 트리에 노드 추가 */
	BST_InsertNode(Tree, BST_CreateNode(22));
	BST_InsertNode(Tree, BST_CreateNode(9918));
	BST_InsertNode(Tree, BST_CreateNode(424));
	BST_InsertNode(Tree, BST_CreateNode(17));
	BST_InsertNode(Tree, BST_CreateNode(3));

	BST_InsertNode(Tree, BST_CreateNode(98));
	BST_InsertNode(Tree, BST_CreateNode(34));
	
	BST_InsertNode(Tree, BST_CreateNode(760));
	BST_InsertNode(Tree, BST_CreateNode(317));
	BST_InsertNode(Tree, BST_CreateNode(1));
	
	/* 트리 출력 */
	BST_InorderPrintTree(Tree);
	printf("\n");

	/* 특정 노드 삭제 */
	printf("Removing 98...\n");

	Node = BST_RemoveNode(Tree, NULL, 98);
	BST_DestroyNode(Node);

	BST_InorderPrintTree(Tree);
	printf("\n");

	/* 새 노드 삽입 */
	printf("Inserting 111...\n");

	BST_InsertNode(Tree, BST_CreateNode(111));
	BST_InorderPrintTree(Tree);
	printf("\n");

	/* 트리 소멸시키기 */
	BST_DestroyTree(Tree);

	return 0;
}