bool empty_stack(linkstack *); //判断栈是否为空的函数 ///////////////////////// BTNode *init_BSTree(Btree); //初始化二叉排序树 Btree BSTree_fund();
//建立一个二叉排序树的函数
bool Search_BSTree(Btree, keytype, BTNode&, BTNode&); //判断该值是否在二叉树存在
bool insert_BSTree(Btree&, valuetype); //插入一个数值，返回0或1，判断是否插入成功 bool Delete_BSTree(Btree&, keytype);
//删除函数，找到要删除的数值，调用delete_value(Btree &tree)，返回0或1判断删除是否成功
void delete_value(Btree &tree); //删除这个结点
void inoder_rec(Btree); //中序非递归遍历二叉排序树 void PrintTree(Btree, int); //按树状图就行输出
////////////////////////////////////// void menu(Btree); //函数的菜单界面
第四章详细设计
4.1插入模块的设计
bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) { //寻找函数，判断二叉排序树中是否有该值，有返回1，无返回0
child = tree;//子节点等于根节点
while (child) {//如果子节点child不为空，则执行下面代码
if (value == child->data) {//如果值等于child->data，则表示找到，返回1 return 1; }
11 / 31
else if (value < child->data) {//如果该值小于child->data，则向左子树进行查找 parents = child;//parents纪录child结点的上一个结点，相当于记录父节点 child = child->lchild; }
else {
parents = child;
child = child->rchild; }
}
return 0;//如果不执行上面一段代码，或者没有找到，返回0 // } }
bool insert_BSTree(Btree &tree, keytype value) { Btree parents, child;//定义指针
if (!Search_BSTree(tree, value, parents, child)) {//如果二叉排序树找不到该值，则插入 Btree S = (BTNode*)malloc(sizeof(BTNode));//申请一个结构体空间 S->data = value;//赋值 S->lchild = NULL; S->rchild = NULL;
if (!tree) tree = S;//如果tree为空，则tree为s，设置根结点
else if (value < parents->data) {//如果value < parents->data，就插入到左子树 parents->lchild = S; }
else {
parents->rchild = S;//反之，插入到右子树 } }
return 1;
// return tree; }
4.2删除模块的设计
bool Delete_BSTree(Btree &tree, keytype value) {//删除函数 if (!tree)return 0; //tree为空，则表示删除功能不能执行 else {
if (value == tree->data) {//如果找到与value值相同的指针，调用delete_value函数进行删除
delete_value(tree); return 1; }
else if (value < tree->data) {//value小于结点的值，往左子树进行寻找 return Delete_BSTree(tree->lchild, value);
12 / 31
}
else {
return Delete_BSTree(tree->rchild, value); } }
//printf(\ }
void delete_value(Btree &p) { Btree q = NULL, s = NULL;
if (p->lchild && p->rchild) {//删除的结点，左右子树都不为空的情况 q = p; s = p->lchild; //q记录,s设为删除结点的左结点 while (s->rchild) {
q = s; s = s->rchild;
}//进行循环，找到最右边的那个结点
p->data = s->data; //把找到的最右边结点的关键字赋值给p的关键字 if (q != p) q->rchild = s->lchild;//挂接左右子树 else q->lchild = s->lchild;
//printf(\ free(s);//删除s这个结点 }
else {
if (!p->rchild) {//右子树为空，所以挂接到左子树上 q = p; p = p->lchild; free(q); }
else {
q = p; p = p->rchild; free(q);//左子树为空，所以挂接到右子树上 }
//printf(\
}
}
4.3遍历模块设计
void inoder_rec(Btree T) {
linkstack S ;
initstack( &S);//初始化一个栈 Selem e; Btree p = T;
while (p || !(S.count == 0)) {//当栈不为空或者p不为空时执行
13 / 31
while(p) {
push_stacks(&S, p); //p不为空，则进栈 p = p->lchild; //对左子树进行遍历 }
if(!empty_stack(&S)) {
e = Get_top(S, e); //当栈不为空时，取栈顶，输出栈顶指针所指向的data值 printf(\
pop_stacks(&S, p); //出栈，对右子树进行遍历 p = p->rchild; }
}
/*if (T) {
inoder_rec(T->lchild); printf(\ inoder_rec(T->rchild); }*/
//menu(tree);
}
4.4树型打印模块的设计
void PrintTree(Btree bt, int nlayer) // {//采用先序遍历的方法，进行树型打印 if(bt){
PrintTree(bt->rchild, nlayer + 10); for (int i = 0; i printf(\ } printf(\ PrintTree(bt->lchild, nlayer + 10); } } 14 / 31 4.5重建二叉树模块的设计 Btree BSTree_fund() { struct int_linklist *lists = NULL; Btree tree = NULL; int n; lists = init();//初始化顺序表 srand((unsigned)time(NULL));//伪随机函数的初始化 printf(\ scanf_s(\输入要插入多少的数 for (int i = 0; i < n; i++) { add(lists, rand());//构造顺序表 } struct linklist *p; // Btree tree = NULL; tree = init_BSTree(tree);//初始化二叉树 p = lists->head->next; while (p != NULL) { insert_BSTree(tree, p->element); p = p->next; }//调用insert_BSTree函数构造二叉树 return tree; } 15 / 31