透由二元搜尋樹及鏈結佇列，來實現成績管理程式的新增,刪除,讀檔,存檔功能。
二元搜尋樹(Binary Search Tree)
二元搜尋樹具有幾個特性:
- 在左子樹(left subtree)的所有鍵值均小於樹根的鍵值。
- 在右子樹(right subtree)的所有鍵值均大於樹根的鍵值。
- 左子樹跟右子樹也是二元搜尋樹。
- 每個鍵值必須為不同。
以本程式的資料當作範例，可供讀者參閱二元搜尋樹，其中沒有連結處為NULL，亦即空集點。
從此圖中我們可以得知，左子樹鍵值會小於樹根，而右子樹鍵值會大於樹根，同時不能存在相同鍵值的狀況。
在本文中不會過多著墨在介紹二元搜尋樹，僅討論關於如果刪除二元搜尋樹中的某一節點呢?
二元搜尋樹的節點刪除
筆者因為在準備出國，因此沒有太多時間去準備，所以直接以畫圖的方式更容易描述步驟，而更細節的部份可以參閱筆者的程式碼或資料結構書籍。
完整程式碼:
//the score record program used by linked list, binary search tree and structure.
//have functions: insert,load data,save data,show
#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include <string>
void insert(char*, int); /* 新增函數 */
void load(char); /* 載入函數 */
void save(void); /* 存檔函數 */
void show(void); /* 顯示函數 */
void delet(struct student*,char*,int); /*刪除函數*/
void replace(struct student*, struct student*);/*取代函數*/
void introdu(void);/* 介紹函數 */
void inorder(struct student*);
//資料以中序追蹤(inorder):依序拜訪left subtree, root and right subtree.
void preorder(struct student*,FILE *);
//以前序追蹤(preorder)儲存資料到檔案:依序拜訪 root, left subtree and right subtree.
struct student {
struct student *Llink; //left subtree
char name[20]; //node data
int score; //node data
bool right; //is the node right subtree of paeent node?
struct student *Rlink; //right subtree
};
struct student *head;
struct student *null = (struct student*)malloc(sizeof(struct student));
//當某節點的Llink與Rlink皆指向 *null時，代表此節點為終點節點。
int main()
{
null = NULL;
char key, loadQ, name[20] = {};
int score;
introdu();
printf("Do you want to load the data to program?(Y/N)");
scanf("%s", &loadQ);
load(loadQ);
while (1) {
printf("Please enter a command:");
scanf("%s",&key);
switch (key) {
case '1':
printf("\n*******Insert the student score*******\n");
printf("Please enter the student name:");
scanf("%s",&name);
printf("Please enter the student score:");
scanf("%d", &score);
insert(name,score);
printf("\n**************************************\n");
break;
case '2':
printf("\n*******Delete the student score*******\n");
printf("Please enter the student name:");
scanf("%s", &name);
printf("Please enter the student score:");
scanf("%d", &score);
delet(head,name,score);
printf("\n**************************************\n");
break;
case '3':
show();
break;
case '4':
save();
break;
default:
return 0;
break;
}
}
}
void insert(char* name,int score) {
struct student *node = (struct student*)malloc(sizeof(struct student));
struct student *point = (struct student*)malloc(sizeof(struct student));
point->score = score;
strcpy(point->name,name);
point->Rlink = NULL;
point->Llink = NULL;
if (head == NULL) {
head = point;
}
else {
node = head;
while (1) {
if (point->score > node->score) {
if (node->Rlink != NULL) {
node = node->Rlink;//移動到節點的右子樹
}
else {
node->Rlink = point;
point->right = true;//為父節點下的右子樹
//printf("Node:%s %d\n", node->name, node->score);
//printf("Right:%s %d\n", point->name, point->score);
break;
}
}
else if (point->score < node->score) {
if (node->Llink != NULL) {
node = node->Llink;//移動到節點的左子樹
}
else {
node->Llink = point;
point->right = false;//為父節點下的左子樹
//printf("Node:%s %d\n", node->name, node->score);
//printf("Light:%s %d\n", point->name, point->score);
break;
}
}
else {
printf("ERROR!!!/n");
break;
}
}
}
}
void load(char Q) {
if (Q == 'Y'||Q == 'y') {
char name[20] = {};
int score = 0;
FILE *fp;
if ((fp = fopen("final test.bin", "rb+")) != NULL) {
printf("\n*******Load the student score from Data.*******\n");
while (fscanf(fp,"%s %d", name, &score)!=EOF) {
insert(name,score);//insert
}
printf("\n***********************************************\n");
}
fclose(fp);
}
}
void save(void) {
FILE *fp;
if ((fp = fopen("final test.bin", "wb+")) != NULL) {
preorder(head,fp);
}
else {
printf("ERROR:CANNOT SAVE THE DATA.\n");
}
fclose(fp);
}
void show(void) {
printf("use inorder to traversal:\n");
printf("**********************************\n");
inorder(head);
printf("**********************************\n\n");
}
void introdu() {//介紹功能
printf("The program can save the student final exam scores. \n");
printf("(Use by linked list, binary search tree and structure.) \n");
printf("You can enter the number which choose the function:\n");
printf("---------------------------------------\n");
printf(" 1.Inset the new student score \n");
printf(" 2.Delete student scores \n");
printf(" 3.Display all student scores \n");
printf(" 4.Save the data\n");
printf(" 5.Exit\n");
printf("---------------------------------------\n");
}
void delet(struct student* node, char* target_name, int target_score) {
struct student *previous=node;
if (head == NULL) {
printf("No score record!\n");
}
else {
while (node != NULL) {
if (target_score > node->score) {
previous = node;
node = node->Rlink;
}
else if (target_score < node->score) {
previous = node;
node = node->Llink;
}
else {
if (strcmp(node->name,target_name)==0) {//成績與名字一致
printf("Find the student name is %s, and score is %d.\n", node->name, node->score);
if (node->Llink == NULL && node->Rlink == NULL) {//若此節點為樹葉節點
if (node->right) {
previous->Rlink = NULL;
free(node);
}
else {
previous->Llink = NULL;
free(node);
}
}
else replace(previous, node); //此節點非樹葉節點，需要找替代節點
break;
}
else {
printf("Cannot find student name from record!\n");
break;
}
}
}
}
}
void replace(struct student* previous_target_node, struct student* target_node) {
//previous_target_node is the parent node from target_node.
//And pre_replace_node is also the parent node from replace_node.
struct student *replace_node,*pre_replace_node;
if (target_node->Rlink != NULL) {//搜尋右子樹最小替代節點
pre_replace_node = target_node;
replace_node = target_node->Rlink;
//printf("Node %s:%d\n", replace_node->name, replace_node->score);
while (replace_node->Llink != NULL) { //找右子樹中最小的節點
pre_replace_node = replace_node;
replace_node = replace_node->Llink;
}
pre_replace_node->Llink = replace_node->Rlink;
//將替代節點's父節點的Llink連結至替代節點's左子樹，若無則為NULL
if (target_node->Rlink != replace_node)replace_node->Rlink = target_node->Rlink;
if (target_node->Llink != replace_node)replace_node->Llink = target_node->Llink;
//將替代節點與target同步相同的左右子樹，同時避免自己的子樹為自己的狀況發生
if (target_node != head) {
if (target_node->right) {
previous_target_node->Rlink = replace_node;
replace_node->right = true;
}
else {
previous_target_node->Llink = replace_node;
replace_node->right = false;
}
}
else head = replace_node;
//若target不為root，則將target's父節點的右子樹連結到替代節點
//若為，則替代節點直接取代root
}
else { //搜尋左子樹最大替代節點
pre_replace_node = target_node;
replace_node = target_node->Llink;
//printf("Node %s:%d else\n", replace_node->name, replace_node->score);
while (replace_node->Rlink != NULL) { //找左子樹中最大的節點
pre_replace_node = replace_node;
replace_node = replace_node->Rlink;
}
pre_replace_node->Rlink = replace_node->Llink;
//將替代節點's父節點的Rlink連結至替代節點's左子樹，若無則為NULL
if (target_node->Rlink != replace_node)replace_node->Rlink = target_node->Rlink;
if (target_node->Llink != replace_node)replace_node->Llink = target_node->Llink;
//將替代節點與target同步相同的左右子樹，同時避免自己的子樹為自己的狀況發生
if (target_node != head) {
if (target_node->right) {
previous_target_node->Rlink = replace_node;
replace_node->right = true;
}
else {
previous_target_node->Llink = replace_node;
replace_node->right = false;
}
}
else head = replace_node;
//若target不為root，則將target's父節點的左子樹連結到替代節點
//若為，則替代節點直接取代root
}
free(target_node);
}
void inorder(struct student* node) {
if (node != NULL) {
inorder(node->Llink);
printf("this node %s:%d", node->name, node->score);
if (node == head) {
printf(" is root.\n");
}
else {
if (node->right == true) {
printf(" is right subtree.\n");
}
else {
printf(" is left subtree.\n");
}
}
inorder(node->Rlink);
}
}//資料以中序追蹤(inorder):依序拜訪left subtree, root and right subtree.
void preorder(struct student* node,FILE *fp) {
if (node != NULL){
fprintf(fp,"%s %d\n", node->name, node->score);
preorder(node->Llink, fp);
preorder(node->Rlink, fp);
}
}//資料以前序追蹤(preorder)的方式儲存:依序拜訪 root, left subtree and right subtree.
執行結果:
_______________________________________________
我們透過閱讀，拼湊出真實世界的面貌，
並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。