Jeff/Data_Structure
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
Data_Structure/資料結構光碟檔/CH07/binarySearchTree.c.txt

308 lines
7.9 KiB
Plaintext
Raw Permalink Normal View History

上傳教材
2025-01-20 21:25:33 +08:00
/* file name: binarySearchTree.c */
/* <20>Q<EFBFBD>ΤG<CEA4><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD>B<EFBFBD>z<EFBFBD><7A><EFBFBD>ơи<C6A1><D0B8>J<EFBFBD>B<EFBFBD>x<EFBFBD>s<EFBFBD>B<EFBFBD>s<EFBFBD>W<EFBFBD>B<EFBFBD>R<EFBFBD><52><EFBFBD>B<EFBFBD>ק<EFBFBD><D7A7>B<EFBFBD><42><EFBFBD>X */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* <20>w<EFBFBD>qstudent<6E><74><EFBFBD>c */
struct student {
char name[20]; /* <20>ǥͩm<CDA9>W */
int score; /* <20>ǥͦ<C7A5><CDA6>Z */
struct student *llink; /* <20><><EFBFBD>l<EFBFBD>쵲 */
struct student *rlink; /* <20>k<EFBFBD>l<EFBFBD>쵲 */
};
void insert_f(void); /* <20>s<EFBFBD>W<EFBFBD><57><EFBFBD><EFBFBD> */
void delete_f(void); /* <20>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
void modify_f(void); /* <20>ק<EFBFBD><D7A7><EFBFBD><EFBFBD><EFBFBD> */
void show_f(void); /* <20><><EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD> */
void process(char [], int); /* <20>N<EFBFBD><4E><EFBFBD>ƥ[<5B>J<EFBFBD>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D> */
void removing(char []); /* <20>N<EFBFBD><4E><EFBFBD>Ʊq<C6B1>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD>𤤲<EFBFBD><F0A4A4B2><EFBFBD> */
struct student *replace(struct student *); /* <20>M<EFBFBD><4D><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
void connecting(struct student *, char); /* <20>վ<EFBFBD><D5BE>쵲 */
void inorder(struct student *); /* <20><><EFBFBD>ƥH<C6A5><48><EFBFBD>Ǫk<C7AA><6B><EFBFBD>X */
void flushBuffer(void);
struct student *search(char []); /* <20>j<EFBFBD>M<EFBFBD>`<60>I */
struct student *search_re_r(struct student *); /* <20>j<EFBFBD>M<EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
struct student *search_re_l(struct student *); /* <20>j<EFBFBD>M<EFBFBD><4D><EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
struct student *search_p(struct student *); /* <20>j<EFBFBD>M<EFBFBD><4D><EFBFBD>`<60>I */
struct student *root, *ptr;
int main(void)
{
char option;
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 = getchar();
flushBuffer();
printf("\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':
exit(0);
default :
puts("<22>ﶵ<EFBFBD><EFB6B5><EFBFBD>~!");
}
}
return 0;
}
/* <20>s<EFBFBD>W<EFBFBD><57><EFBFBD>ơA<C6A1>s<EFBFBD>W<EFBFBD>@<40><><EFBFBD>s<EFBFBD><73><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
void insert_f(void)
{
char name[20];
int score;
puts("=====INSERT DATA=====");
printf("<22>m<EFBFBD>W: ");
scanf("%s", name);
printf("<22><><EFBFBD><EFBFBD>: ");
scanf("%d", &score);
flushBuffer();
process(name, score);
}
/* <20>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>ơA<C6A1>N<EFBFBD><4E><EFBFBD>Ʊq<C6B1>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD>𤤧R<F0A4A4A7><52> */
void delete_f(void)
{
char name[20];
if (root == NULL) {
puts("<22>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD>O<EFBFBD>Ū<EFBFBD>!");
return;
}
puts("=====DELETE DATA=====");
printf("<22>п<EFBFBD><D0BF>J<EFBFBD><4A><EFBFBD>R<EFBFBD><52><EFBFBD><EFBFBD><EFBFBD>m<EFBFBD>W: ");
scanf("%s", name);
flushBuffer();
removing(name);
}
/* <20>ק<EFBFBD><D7A7><EFBFBD><EFBFBD>ơA<C6A1>ק<EFBFBD><D7A7>ǥͦ<C7A5><CDA6>Z */
void modify_f(void)
{
struct student *node;
char name[20];
/* <20>P<EFBFBD>_<EFBFBD>ڸ`<60>I<EFBFBD>O<EFBFBD>_<EFBFBD><5F>NULL */
if (root == NULL) {
puts("<22>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD>O<EFBFBD>Ū<EFBFBD>!");
return;
}
puts("=====MODIFY DATA===== ");
printf("<22>п<EFBFBD><D0BF>J<EFBFBD><4A><EFBFBD>ק諸<D7A7>m<EFBFBD>W: ");
scanf("%s", name);
flushBuffer();
if ((node = search(name)) == NULL)
printf("%s <20><><EFBFBD>b<EFBFBD>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D>!\n", name);
else {
/* <20>C<EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD><EFBFBD>ƪ<EFBFBD><C6AA>p */
printf("<22>m<EFBFBD>W: %s\n", node->name);
printf("<22><><EFBFBD><EFBFBD>: %d\n\n", node->score);
printf("<22>п<EFBFBD><D0BF>J<EFBFBD>s<EFBFBD><73><EFBFBD><EFBFBD><EFBFBD><EFBFBD>: ");
scanf("%d", &node->score);
flushBuffer();
printf("%s <20>w<EFBFBD>Q<EFBFBD>ק<EFBFBD>\n", name);
}
}
/* <20><><EFBFBD>X<EFBFBD><58><EFBFBD>ơA<C6A1>N<EFBFBD><4E><EFBFBD>ƿ<EFBFBD><C6BF>X<EFBFBD>ܿù<DCBF> */
void show_f(void)
{
/* <20>P<EFBFBD>_<EFBFBD>ڸ`<60>I<EFBFBD>O<EFBFBD>_<EFBFBD><5F>NULL */
if (root == NULL) {
puts("<22>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD>O<EFBFBD>Ū<EFBFBD>!");
return;
}
puts("=====SHOW DATA=====");
inorder(root); /* <20>H<EFBFBD><48><EFBFBD>Ǫk<C7AA><6B><EFBFBD>X<EFBFBD><58><EFBFBD><EFBFBD> */
}
/* <20>B<EFBFBD>z<EFBFBD>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD>A<EFBFBD>N<EFBFBD>s<EFBFBD>W<EFBFBD><57><EFBFBD>ƥ[<5B>J<EFBFBD>ܤG<DCA4><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD><EFBFBD> */
void process(char name[], int score)
{
struct student *node, *prev;
/* <20><><EFBFBD>Ƥw<C6A4>s<EFBFBD>b<EFBFBD>h<EFBFBD><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
if (search(name) != NULL) {
printf("%s <20>w<EFBFBD>s<EFBFBD>b!\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) /* <20><><EFBFBD>ڸ`<60>I<EFBFBD><49>NULL<4C><4C><EFBFBD><EFBFBD><EFBFBD>p */
root = ptr;
else { /* <20><><EFBFBD>ڸ`<60>I<EFBFBD><49><EFBFBD><EFBFBD>NULL<4C><4C><EFBFBD><EFBFBD><EFBFBD>p */
node = root;
while (node != NULL) { /* <20>j<EFBFBD>M<EFBFBD><4D><EFBFBD>ƴ<EFBFBD><C6B4>J<EFBFBD>I */
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;
}
}
/* <20>N<EFBFBD><4E><EFBFBD>Ʊq<C6B1>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD>𤤲<EFBFBD><F0A4A4B2><EFBFBD> */
void removing(char name[])
{
struct student *del_node;
if((del_node = search(name)) == NULL) /* <20>䤣<EFBFBD><E4A4A3><EFBFBD><EFBFBD><EFBFBD>ƫh<C6AB><68><EFBFBD>ܿ<EFBFBD><DCBF>~ */
{
printf("%s <20><><EFBFBD>b<EFBFBD><62><EFBFBD>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD><EFBFBD>!\n", name);
return;
}
/* <20>`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>𸭸`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>p */
if (del_node->llink != NULL || del_node->rlink != NULL)
del_node = replace(del_node);
else /* <20>`<60>I<EFBFBD><49><EFBFBD>𸭸`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>p */
if(del_node == root)
root = NULL;
else
connecting(del_node, 'n');
free(del_node); /* <20><><EFBFBD><EFBFBD><EFBFBD>O<EFBFBD><4F><EFBFBD><EFBFBD> */
printf("%s <20>w<EFBFBD>Q<EFBFBD>R<EFBFBD><52>!\n", name);
}
/* <20>M<EFBFBD><4D><EFBFBD>R<EFBFBD><52><EFBFBD>D<EFBFBD>𸭸`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
struct student *replace(struct student *node)
{
struct student *re_node;
/* <20><><EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD>䤣<EFBFBD><E4A4A3><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I<EFBFBD>A<EFBFBD>|<7C>j<EFBFBD>M<EFBFBD><4D><EFBFBD>l<EFBFBD><6C><EFBFBD>O<EFBFBD>_<EFBFBD>s<EFBFBD>b<EFBFBD><62><EFBFBD>N<EFBFBD>`<60>I */
if ((re_node = search_re_r(node->rlink)) == NULL)
re_node = search_re_l(node->llink);
if (re_node->rlink != NULL) /* <20><><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I<EFBFBD><49><EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD>s<EFBFBD>b<EFBFBD><62><EFBFBD><EFBFBD><EFBFBD>p */
connecting(re_node, 'r');
else
if (re_node->llink != NULL) /* <20><><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>l<EFBFBD><6C><EFBFBD>s<EFBFBD>b<EFBFBD><62><EFBFBD><EFBFBD><EFBFBD>p */
connecting(re_node, 'l');
else /* <20><><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I<EFBFBD><49><EFBFBD>𸭸`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>p */
connecting(re_node, 'n');
strcpy(node->name, re_node->name);
node->score = re_node->score;
return re_node;
}
/* <20>վ<EFBFBD><D5BE>G<EFBFBD><47><EFBFBD>j<EFBFBD>M<EFBFBD><4D><EFBFBD><EFBFBD><EFBFBD>쵲<EFBFBD>Alink <20><> r <20><><EFBFBD>ܳB<DCB3>z<EFBFBD>k<EFBFBD>쵲<EFBFBD>A<EFBFBD><41> l <20><><EFBFBD>B<EFBFBD>z<EFBFBD><7A><EFBFBD>쵲<EFBFBD>A
<20><> m <20>h<EFBFBD>N<EFBFBD>쵲<EFBFBD><ECB5B2><EFBFBD>V NULL */
void connecting(struct student *node, char link)
{
struct student *parent;
parent = search_p(node); /* <20>j<EFBFBD>M<EFBFBD><4D><EFBFBD>`<60>I */
/* <20>`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>`<60>I<EFBFBD><49><EFBFBD>l<EFBFBD>𪺪<EFBFBD><F0AABAAA>p */
if (strcmp(node->name, parent->name) < 0)
if(link == 'r') /* link<6E><6B>r */
parent->llink = node->rlink;
else /* link<6E><6B>m */
parent->llink = NULL;
else /* <20>`<60>I<EFBFBD><49><EFBFBD><EFBFBD><EFBFBD>`<60>I<EFBFBD>k<EFBFBD>l<EFBFBD>𪺪<EFBFBD><F0AABAAA>p */
if (link == 'l') /* link<6E><6B>l */
parent->rlink = node->llink;
else /* link<6E><6B>m */
parent->rlink = NULL;
}
/* <20>H<EFBFBD><48><EFBFBD>Ǫk<C7AA><6B><EFBFBD>X<EFBFBD><58><EFBFBD>ơA<C6A1>Ļ<EFBFBD><C4BB>j<EFBFBD>覡 */
void inorder(struct student *node)
{
if(node != NULL) {
inorder(node->llink);
printf("%-10s %d\n", node->name, node->score);
inorder(node->rlink);
}
}
/* <20>j<EFBFBD>Mtarget<65>Ҧb<D2A6>`<60>I */
struct student *search(char target[])
{
struct student *node;
node = root;
while(node != NULL)
{
if (strcmp(target, node->name) == 0)
return node;
else
/* target<65>p<EFBFBD><70><EFBFBD>ثe<D8AB>`<60>I<EFBFBD>A<EFBFBD><41><EFBFBD><EFBFBD><EFBFBD>j<EFBFBD>M */
if (strcmp(target, node->name) < 0)
node = node->llink;
else /* target<65>j<EFBFBD><6A><EFBFBD>ثe<D8AB>`<60>I<EFBFBD>A<EFBFBD><41><EFBFBD>k<EFBFBD>j<EFBFBD>M */
node = node->rlink;
}
return node;
}
/* <20>j<EFBFBD>M<EFBFBD>k<EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
struct student *search_re_r(struct student *node)
{
struct student *re_node;
re_node = node;
while (re_node != NULL && re_node->llink != NULL)
re_node = re_node->llink;
return re_node;
}
/* <20>j<EFBFBD>M<EFBFBD><4D><EFBFBD>l<EFBFBD><6C><EFBFBD><EFBFBD><EFBFBD>N<EFBFBD>`<60>I */
struct student *search_re_l(struct student *node)
{
struct student *re_node;
re_node = node;
while (re_node != NULL && re_node->rlink != NULL)
re_node = re_node->rlink;
return re_node;
}
/* <20>j<EFBFBD>Mnode<64><65><EFBFBD><EFBFBD><EFBFBD>`<60>I */
struct student *search_p(struct student *node)
{
struct student *parent;
parent = root;
while (parent != NULL) {
if (strcmp(node->name, parent->name) < 0) {
if (strcmp(node->name, parent->llink->name) == 0)
return parent;
else
parent = parent->llink;
}
else {
if (strcmp(node->name, parent->rlink->name) == 0)
return parent;
else
parent = parent->rlink;
}
}
return NULL;
}
void flushBuffer()
{
while (getchar() != '\n')
continue;
}
Reference in New Issue Copy Permalink