21 / 31
第六章总结
通过这次课程设计，我对二叉排序树的整个构造流程更加了解了，同时也对顺序表和栈这两种数据结构做了一次复习，但同时也存在了很多问题。我在删除函数中因为有些指针没有用好，所以最开始只是跟我报错说是read()出错，我反复的检查许久一直找不到出错的地方在哪，不得已，只能重新写了一遍删除函数，发现我分成两个删除函数去执行（一个函数去找那个需要删除的结点，另一个函数则是对这已经找到的结点进行删除），没有问题。而对于中序遍历函数，我先用递归做测试，先把其他功能做完善以后，再用栈来实现中序非递归遍历。
22 / 31
第七章附录源代码
#include
//#include
unsigned int n = 30; //////////
typedef int keytype;
typedef int valuetype; typedef int listtype;
///////////////////////////// struct linklist {
struct linklist *next; int element; };
struct int_linklist {
struct linklist *head; int counts; };
//////////////////////// typedef struct BSTNode { keytype data;
struct BSTNode *lchild, *rchild; }BTNode, *Btree;
///////////////////// typedef Btree Selem; typedef struct snode { Selem data;
struct snode *next; }snode, *linkst;
typedef struct linkstack { linkst top; int count; }linkstack;
/////////////////////
struct int_linklist*init();
void add(struct int_linklist*, int); void printf_list(struct int_linklist *);
23 / 31
/////////////////////
void emptyMessage(char *); void initstack(linkstack *);
void push_stacks(linkstack *, Selem ); void pop_stacks(linkstack *,Selem&); bool empty_stack(linkstack *); ///////////////////////// BTNode *init_BSTree(Btree); Btree BSTree_fund();
bool Search_BSTree(Btree, keytype, BTNode&, BTNode&); bool insert_BSTree(Btree&, valuetype); bool Delete_BSTree(Btree&, keytype); void delete_value(Btree &tree); void inoder_rec(Btree); void PrintTree(Btree, int);
////////////////////////////////////// void menu(Btree); //////////////////、 int main() {
Btree tree = NULL; //printf_list(lists); tree = BSTree_fund(); //printf(\
//printf(\ //printf(\ //inoder_rec(tree); menu(tree); return 0; }
//////////////////////
struct int_linklist* init() { struct int_linklist*lists;
lists = (struct int_linklist*)malloc(sizeof(struct int_linklist*)); lists->head = (struct linklist*)malloc(sizeof(struct linklist)); lists->head->element = -1; lists->counts = 0;
lists->head->next = NULL; return lists; }
void add(struct int_linklist *lists, int value) { struct linklist *p;
p = (struct linklist *)malloc(sizeof(struct linklist)); p->next = NULL; p->element = value;
24 / 31
p->next = lists->head->next; lists->head->next = p; lists->counts++; //return lists; }
void printf_list(struct int_linklist *lists) { struct linklist *p; p = lists->head->next; while (p != NULL) {
printf(\ p = p->next; } }
//////////////////////
void emptyMessage(char *s) { printf(\ exit(1); }
void initstack(linkstack *stacks) { //linkst *p;
stacks->top = (linkst)malloc(sizeof(snode));
if (stacks->top == NULL)emptyMessage(\ stacks->top = NULL; stacks->count = 0;
//stacks.top -> next = NULL; }
Selem Get_top(linkstack stacks, Selem &e) {
if (stacks.top == NULL)emptyMessage(\ e = stacks.top->data; return e; }
void push_stacks(linkstack *stacks, Selem e) { linkst p = (linkst)malloc(sizeof(snode)); if (p == NULL)emptyMessage(\ p->data = e;
p->next = stacks->top; stacks->top = p; stacks->count++; }
void pop_stacks(linkstack *stacks,Selem &e) { linkst p;
25 / 31