연결리스트 이진 탐색 트리

 

#include <stdio.h>
#include <stdlib.h>
#define ERROR 255
typedef char element;

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

typedef struct {
	TreeNode* root;
}BST;

BST* createBST() {
	BST* bst = (BST*)malloc(sizeof(BST));
	bst->root = NULL;
	return  bst;
}

int isEmpty(BST* bst) {
	if (bst->root = NULL) return 1;
	return 0;
}

element getData(TreeNode * current) {
	return current->key;
}

void preorder(TreeNode * root) {//전위순회
	if (root == NULL) return;
	printf("%d\t", root->key);
	preorder(root->left);
	preorder(root->right);
}

void inorder(TreeNode * root) {//중위순회
	if (root == NULL) return;
	inorder(root->left);
	printf("%d\t", root->key);
	inorder(root->right);
}

void postorder(TreeNode * root) { //후위순회
	if (root == NULL) return;
	postorder(root->left);
	postorder(root->right);
	printf("%d\t", root->key);
}

TreeNode* searchBST(TreeNode * root, element key) {
	if (root == NULL) {
		return NULL;
	}

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

TreeNode* searchBST2(TreeNode * root, element key) {
	TreeNode* p = root;
	while (p != NULL) {
		if (key == p->key) {
			return p;
		}
		else if (key < p->key) {
			p = p->left;
		}
		else {
			p = p->right;
		}
	}
}

void insertBST(BST * bst, element key) {
	TreeNode* newNode;
	TreeNode* p = bst->root;
	TreeNode* parent = NULL;

	//새로운 키값을 삽입 할 위치 선정
	while (p != NULL) {
		if (key == p->key) {
			return;
		}
		if (key < p->key) {
			parent = p;
			p = p->left;
		}
		else {
			parent = p;
			p = p->right;
		}
	}
	//새노드 생성
	newNode = (TreeNode*)malloc(sizeof(TreeNode));
	newNode->key = key;
	newNode->left = NULL;
	newNode->right = NULL;
	//새노드 추가
	if (parent == NULL) {
		bst->root = newNode;
	}
	else if (key < parent->key) {
		parent->left = newNode;
	}
	else {
		parent->right = newNode;
	}
}

int removeBST(BST * bst, element key) {
	TreeNode* p = bst->root;
	TreeNode* parent = NULL;
	TreeNode* child, * succ, * succ_parent;


	//1.삭제 할 노드 탐색
	while ((p != NULL)&&(p->key!=key)) {
		parent = p;
		if (key < p->key) {
			p = p->left;
		}
		else {
			p = p->right;
		}
		if (p == NULL) {
			printf("삭제 할 key가 존재하지 않습니다.");
			return 0;//못 찾은 경우
		}
	}

	//삭제
	//2-1.차수가 0인 경우 삭제
	if(p->left == NULL && p->right == NULL){
		if (parent != NULL) {
			if (parent->left == p)parent->left = NULL;
			else parent->right = NULL;
		}
		else bst->root = NULL;
	}
	//2-2.차수가 1인 경우 삭제
	else if ((p->left == NULL) || (p->right == NULL)) {
		if (p->left != NULL) child = p->left;
		else child = p->right;

		if (parent != NULL) {
			if (parent->left == p) parent->left = child;
			else parent->right = child;
		}
		else bst->root = child;
	}
	//2-3.차수가 2인 경우 삭제
	else {
		succ_parent = p;
		succ = p->left;
		while (succ->right != NULL) {
			succ_parent = succ;
			succ = succ->right;
		}
		if (succ_parent->left == succ) succ_parent->left = succ->left;
		else succ_parent->right = succ->left;
		p->key = succ->key;
		p = succ;
	}
	free(p);
	return 1;
}

int main() {
	TreeNode* p;
	BST* bst1, * bst2;
	bst1 = createBST();
	bst2 = createBST();

	insertBST(bst1, 30);
	insertBST(bst1, 20);
	insertBST(bst1, 70);
	insertBST(bst1, 15);
	insertBST(bst1, 10);
	insertBST(bst1, 50);
	insertBST(bst1, 40);

	insertBST(bst2, 50);
	insertBST(bst2, 10);
	insertBST(bst2, 100);
	insertBST(bst2, 5);
	insertBST(bst2, 20);
	insertBST(bst2, 15);
	insertBST(bst2, 40);
	insertBST(bst2, 30);
	insertBST(bst2, 31);

	p = searchBST(bst1->root, 15);
	printf("%d\n", getData(p));

	preorder(bst2->root);
	removeBST(bst2, 15);
	printf("\n");
	preorder(bst2->root);
	removeBST(bst2, 50);
	printf("\n");
	preorder(bst2->root);
	return 0;
}