[자료구조] BSTree

development activity/C Language

[자료구조] BSTree

Choi Hyun Seok 2015. 12. 6. 15:27

이진탐색트리

(BSTree : binary search tree)

left node는 부모노드보다 작아야 하며 right node는 부모노드 보다 커야함

이진탐색트리의 속성

각 노드에 값이 있다.
각 노드의 키값은 모두 달라야 한다.
값들은 전순서가 있다.
노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
중복된 노드가 없어야 한다.

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

typedef char element;

typedef struct TreeNode {
	element key;
	struct TreeNode *left;
	struct TreeNode *right;
} TreeNode;

TreeNode *searchBST(TreeNode *BST, element x) {
	TreeNode *p = BST;

if(p == NULL) return NULL;
	else if(x == p->key) {
		return p;
	} else if(x < p->key) {
		return searchBST(p->left, x);
	} else {
		return searchBST(p->right, x);
	}
}

TreeNode *insertBST(TreeNode *BST, element x) {
	TreeNode *p, *q, *new;
	p = BST;
	
	while(p != NULL) {
		if(x == p->key) return 0;
		else q=p;
		if(x < p->key) p = p->left;
		else p = p->right;
	}

new = (TreeNode*)malloc(sizeof(TreeNode));
	new->key = x;
	new->left = NULL;
	new->right = NULL;

if(BST == NULL) BST = new;
	else if(x < q->key) q->left = new;
	else q->right = new;
}

TreeNode *maxNode(TreeNode *BST) {
	TreeNode *p, *q;
	p = BST;

while(p != NULL) {
		q=p;
		p = p->right;
	}

if((q->left == NULL) && (q->right == NULL)) return q;
	else if((q->left == NULL) || (q->right == NULL)) {
		if(q->left != NULL) maxNode(q->right);
		else return q;
	}
	else if((q->left != NULL) && (q->right != NULL)) {
		maxNode(q->right);
	}
}

TreeNode *minNode(TreeNode *BST) {
	TreeNode *p, *q;
	p = BST;

while(p != NULL) {
		q=p;
		p = p->left;
	}

if((q->left == NULL) && (q->right == NULL)) return q;
	else if((q->left == NULL) || (q->right == NULL)) {
		if(q->left != NULL) minNode(q->left);
		else return q;
	}
	else if((q->left != NULL) && (q->right != NULL)) {
		minNode(q->left);
	}
}

int deleteBST(TreeNode *BST, element x) {
	TreeNode *p, *parent, *q;
	p = BST;
	
	while((p->key != x) && (p != NULL)) {
		parent = p;
		if(x < p->key) p = p->left;
		else p = p->right;
	}

if(p == NULL) printf("삭제할 노드가 없습니다!\n"); return 0;

if((p->left == NULL) && (p->right == NULL)) {
		if(parent->left == p) {
			parent->left = NULL;
		} else {
			parent->right = NULL;
		}
	} else if((p->left == NULL) || (p->right == NULL)) {
		if(p->left != NULL)	{
			if(parent->left == p) {
				parent->left = p->left;
			} else {
				parent->right = p->left;
			}
		} else {
			if(parent->left == p) {
				parent->left = p->right;
			} else {
				parent->right = p->right;
			}
		}
	} else if((p->left != NULL) && (p->right != NULL)) {
		if(parent->key > p->key) {
			q = maxNode(p);
			p->key = q->key;
			deleteBST(p->left, p->key);
		}else {
			q = minNode(p);
			p->key = q->key;
			deleteBST(p->left, p->key);
		}
	}

free(p);
	return 1;
}

void display_Inorder(TreeNode *BST) {
	if(BST) {
		display_Inorder(BST->left);
		printf("%c ", BST->key);
		display_Inorder(BST->right);
	}
}

void menu() {
	printf("\n<<<<<< 이진 탐색 트리 >>>>>>");
	printf("\n\t1. 트리 출력");
	printf("\n\t2. 문자 삽입");
	printf("\n\t3. 문자 삭제");
	printf("\n\t4. 문자 탐색");
	printf("\n\t5. 종     료");
	printf("\n<<<<<<<<<<<<<>>>>>>>>>>>>>");
	printf("\n\t메뉴입력 : ");
}

element main() {
	TreeNode *BST = (TreeNode*)malloc(sizeof(TreeNode));
	element key;

int choice;

insertBST(BST, 'A');
	insertBST(BST, 'B');
	insertBST(BST, 'D');
	insertBST(BST, 'C');
	insertBST(BST, 'G');
	insertBST(BST, 'F');
	insertBST(BST, 'E');
	insertBST(BST, 'H');

while(1) {
		menu();
		scanf("%d", &choice);

switch(choice) {
			case 1 : printf("트리 출력 >> ");
				display_Inorder(BST);
				printf("\n"); break;

case 2 : printf("삽입할 문자 입력 >> ");
				scanf(" %c", &key);
				insertBST(BST, key); break;

case 3 : printf("삭제할 문자 입력 >> ");
				scanf(" %c", &key);
				deleteBST(BST, key); break;

case 4 : printf("탐색할 문자 입력 >> ");
				scanf(" %c", &key);
				if(searchBST(BST, key) != NULL) printf("\n문자가 트리에 있습니다!\n");
				else printf("\n문자가 트리에 없습니다!\n");
				break;

case 5 : return 0;

default : printf("잘못 입력했습니다. 다시 입력해주세요!\n"); break;
		}
	}
}

------------------ C 파일 ------------------

BSTree.c