/* file name: bin_search_tree.c */
/* 利用二叉查找樹處理數據－加載、儲存、新增、刪除、修改、輸出 */

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

/* 定義student結構 */
struct student {
	char name[20];  /* 學生姓名 */
	int score;  /* 學生成績 */
	struct student *llink;  /* 左子鏈接 */
	struct student *rlink;   /* 右子鏈接 */
};

void load_f(void);      /* 加載函數 */
void save_f(void);      /* 儲存函數 */
void insert_f(void);    /* 新增函數 */
void delete_f(void);    /* 刪除函數 */
void modify_f(void);    /* 修改函數 */
void show_f(void);      /* 輸出函數 */
void access(char [], int);  /* 將數據插入二叉查找樹 */
void removing(char []);  /* 將數據從二叉查找樹中移除 */
struct student *replace(struct student *);  /* 尋找替代節點 */

void connect(struct student *, char);  /* 調整鏈接 */
void inorder(struct student *);  /* 數據以中序法輸出 */
void preorder(struct student *, FILE *);  /* 數據以前序法寫入表 */
struct student *search(char []);  /* 查找節點 */
struct student *search_re_r(struct student *);  /* 查找右子樹替代節點 */
struct student *search_re_l(struct student *);  /* 查找左子樹替代節點 */
struct student *search_p(struct student *);  /* 查找父節點 */

struct student *root, *ptr;

void main(void)
{
	char option;
	load_f();  /* 載入文件 */
	while(1)
	{
		puts("");
		puts("********************");
		puts("     <1> insert");
		puts("     <2> delete");
		puts("     <3> modify");
		puts("     <4> show");
		puts("     <5> quit");
		puts("********************");
		printf("Enter your choice: ");
		option = getche();
		printf("\n\n");
		switch(option)
		{
			case '1':
				insert_f();
				break;
			case '2':
				delete_f();
				break;
			case '3':
				modify_f();
				break;
			case '4':
				show_f();
				break;
			case '5':
				save_f();  /* 儲存文件 */
				exit(0);
			default :
				puts("Wrong option!");
		}
	}
}

/* 加載函數，將數據文件dfile.dat加載到程序中 */
void load_f(void)
{
	FILE *fptr;
	char name[20];
	int score;
	printf("File loading...");
	if((fptr = fopen("bst.dat", "r")) == NULL)   /* 打開文件 */
	{
		puts("failed!");
		puts("Dfile.dat not found!");
		return;
	}
	while(fscanf(fptr, "%s %d", name, &score) != EOF)   /* 讀取文件數據 */
		if(strcmp(name, "") != 0)
			access(name, score);
	puts("OK!");
	fclose(fptr);   /* 關閉文件 */
}

/* 儲存文件，將二叉查找樹中的數據儲存至數據文件dfile.dat中 */
void save_f(void)
{
	FILE *fptr;
	printf("File saving...");
	if((fptr = fopen("bst.dat", "w")) == NULL)  /* 開啟文件 */
	{
		puts("failed!");
		return;
	}
	preorder(root, fptr);   /* 以前序法寫入 */
	puts("OK!");
	fclose(fptr);  /* 關閉文件 */
}

/* 新增函數，新增一筆新的數據 */
void insert_f(void)
{
	char name[20], temp[4];
	int score;
	puts("=====INSERT DATA=====");
	printf("Enter student name: ");
	gets(name);
	printf("Enter student score: ");
	gets(temp);
	score = atoi(temp);
	access(name, score);
}

/* 刪除函數，將數據從二叉查找樹中刪除 */
void delete_f(void)
{
	char name[20];
	if(root == NULL)
	{
		puts("No student record!");
		return;
	}
	puts("=====DELETE DATA=====");
	printf("Enter student name: ");
	gets(name);
	removing(name);
}

/* 修改數據，修改學生成績 */
void modify_f(void)
{
	struct student *node;
	char name[20], temp[4];
	if(root == NULL)   /* 判斷根節點是否為NULL */
	{
		puts("No student record!");
		return;
	}
	puts("=====MODIFY DATA===== ");
	printf("Enter student name: ");
	gets(name);
	if((node = search(name)) == NULL)
		printf("Student %s not found!\n", name);
	else
	{
		/* 列出原數據狀況 */
		printf("Original student name: %s\n", node->name);
		printf("Original student score: %d\n", node->score);
		printf("Enter new score: ");
		gets(temp);
		node->score = atoi(temp);
		printf("Data of student %s modified\n", name);
	}
}

/* 輸出函數，將數據輸出至屏幕 */
void show_f(void)
{
	if(root == NULL)  /* 判斷根節點是否為NULL */
	{
		puts("No student record!");
		return;
	}
	puts("=====SHOW DATA=====");
	inorder(root);  /* 以中序法輸出數據 */
}
/* 處理二叉查找樹，將新增數據插入至二叉查找樹中 */
void access(char name[], int score)
{
	struct student *node, *prev;
	if(search(name) != NULL)  /* 數據已存在則顯示錯誤 */
	{
		printf("Student %s has existed!\n", name);
		return;
	}
	ptr = (struct student *) malloc(sizeof(struct student));
	strcpy(ptr->name, name);
	ptr->score = score;
	ptr->llink = ptr->rlink = NULL;
	if(root == NULL)  /* 當根節點為NULL的狀況 */
		root = ptr;
	else   /* 當根節點不為NULL的狀況 */
	{
		node = root;
		while(node != NULL)  /* 查找數據插入點 */
		{
			prev = node;
			if(strcmp(ptr->name, node->name) < 0)
				node = node->llink;
			else
				node = node->rlink;
		}
		if(strcmp(ptr->name, prev->name) < 0)
			prev->llink = ptr;
		else
			prev->rlink = ptr;
	}
}

/* 將數據從二叉查找樹中移除 */
void removing(char name[])
{
	struct student *del_node;
	if((del_node = search(name)) == NULL)  /* 找不到數據則顯示錯誤 */
	{
		printf("Student %s not found!\n", name);
		return;
	}
	/* 節點不為樹葉節點的狀況 */
	if(del_node->llink != NULL || del_node->rlink != NULL)
		del_node = replace(del_node);
	else  /* 節點為樹葉節點的狀況 */
		if(del_node == root)
			root = NULL;
		else
			connect(del_node, 'n');
	free(del_node);  /* 釋放內存 */
	printf("Data of student %s deleted!\n", name);
}

/* 尋找刪除非樹葉節點的替代節點 */
struct student *replace(struct student *node)
{
	struct student *re_node;
	/* 當右子樹找不到替代節點，會查找左子樹是否存在替代節點 */
	if((re_node = search_re_r(node->rlink)) == NULL)
		re_node = search_re_l(node->llink);
	if(re_node->rlink != NULL)  /* 當替代節點有右子樹存在的狀況 */
		connect(re_node, 'r');
	else
		if(re_node->llink != NULL)  /* 當替代節點有左子樹存在的狀況 */
			connect(re_node, 'l');
		else  /* 當替代節點為樹葉節點的狀況 */
			connect(re_node, 'n');
	strcpy(node->name, re_node->name);
	node->score = re_node->score;
	return re_node;
}

/* 調整二叉查找樹的鏈接，link為r表示處理右鏈接，為l表處理左鏈接，
   為m則將鏈接指向NULL */
void connect(struct student *node, char link)
{
	struct student *parent;
	parent = search_p(node);   /* 查找父節點 */
	/* 節點為父節點左子樹的狀況 */
	if(strcmp(node->name, parent->name) < 0)
		if(link == 'r')   /* link為r */
			parent->llink = node->rlink;
		else  /* link