数据结构排序的综合实现
/编写二叉排序树的综合练习程序。加深对二叉排序树的建立、插入、查找、删除、显示等算法的理解。/
#include "datastru.h"
#include <string.h>
#include <malloc.h>
#include <stdio.h>
BSTNODE *searchnode(int w, BSTNODE *r)
/按给定值在二叉排序树中查询/
{ BSTNODE *p;
if(r == NULL) p = NULL; /*空二叉排序树*/
else { if(w == r->key) p = r; /*给定值和根结点相同*/
else if(w > r->key) p = searchnode(w, r->rchild); /*递归继续查询*/
else p = searchnode(w, r->lchild);}
return p;
}
BSTNODE *insert_bst(int w, BSTNODE *p)
/将一个元素插入二叉排序树中/
{ if(p == NULL )
/如果二叉排序树空,p作为新二叉排序树的根结点/
{p = malloc(sizeof(BSTNODE));
p->lchild = NULL; p->rchild = NULL; p->key = w;}
else if(w > p->key) p->rchild = insert_bst(w, p->rchild);
/*如果二叉排序树不空,p作为叶子结点递归插入二叉排序树中*/
else p->lchild = insert_bst(w, p->lchild);
return p; /*返回根结点*/
}
BSTNODE *getfather(BSTNODE *p, BSTNODE *r)
/在以r为根结点的二叉排序树中查询p结点的双亲结点并返回双亲结点的地址/
{ BSTNODE *pf;
if(r == NULL || p == r) pf = NULL;
else { if(p == r->lchild || p == r->rchild) pf = r;
else if(p->key > r->key) pf = getfather(p, r->rchild);
else pf = getfather(p, r->lchild);}
return pf;
}
BSTNODE *dele_bst(BSTNODE *p, BSTNODE *r){
/*p结点存在,删除p结点的算法*/
BSTNODE *temp, *tfather, *pf;
pf= getfather(p, r); /*查找p结点的双亲结点,返回双亲结点的地址pf*/
if(p->lchild == NULL && p->rchild == NULL && pf != NULL)
/*被删结点是叶子结点,不是根结点*/
if(pf->lchild == p) pf->lchild = NULL;
else pf->rchild = NULL;
if(p->lchild == NULL && p->rchild == NULL && pf == NULL) r = NULL;
/*被删结点是叶子结点,又是根结点*/
if(p->lchild == NULL && p->rchild != NULL && pf != NULL)
/*被删结点有右孩子,无左孩子,不是根结点*/
if(pf->lchild == p) pf->lchild = p->rchild;
else pf->rchild = p->rchild;
if(p->lchild == NULL && p->rchild != NULL && pf == NULL) r = p->rchild;
/*被删结点有右孩子,无左孩子,又是根结点*/
if(p->lchild != NULL && p->rchild == NULL && pf != NULL)
/*被删结点有左孩子,无右孩子,不是根结点*/
if(pf->lchild == p) pf->lchild = p->lchild;
else pf->rchild = p->lchild;
if(p->lchild != NULL && p->rchild == NULL && pf == NULL) r = p->lchild;
/*被删结点有左孩子,无右孩子,又是根结点*/
if(p->lchild != NULL && p->rchild != NULL)
/*被删结点又有左孩子,又有右孩子*/
{temp = p->lchild; tfather = p;
while(temp->rchild != NULL) {
tfather = temp;
temp = temp->rchild;}
p->key = temp->key;
if(tfather != p) tfather->rchild = temp->lchild;
else tfather->lchild = temp->lchild;
}
printf("\n");
if(r != NULL) printf("二叉排序树根结点是 %d\n\n", r->key);
else printf("二叉排序树空\n\n");
return r;
}
void print_bst(BSTNODE *p){
/*显示二叉排序树*/
if(p != NULL )
{ print_bst(p->lchild);
printf("%d ", p->key);
if(p->lchild != NULL) printf("%d的左结点是%d ", p->key, p->lchild->key);
else printf("%d无左结点 ", p->key);
if(p->rchild != NULL) printf("%d的右结点是%d", p->key, p->rchild->key);
else printf("%d无右结点", p->key);
printf("\n");
print_bst(p->rchild);
}
}
BSTNODE *creat_bst() {
/*建立二叉排序树*/
BSTNODE *root, *p;
int loop = 0;
int s;
root = NULL;
do{ printf("\n"); printf("输入数据(整数,结束输入0) : "); scanf("%d",&s);
if(s == 0) loop = 1;
else {p = searchnode(s, root);
if(p == NULL) {root = insert_bst(s, root);
/*输入的数据不在二叉排序树中,方可插入二叉排序树*/
print_bst(root);} /*边插入边显示二叉排序树中结点值*/
else printf("输入的数据已存在，不能插入\n");
}
if(root != NULL) printf("\n二叉排序树根结点为 %d\n\n", root->key);
}while(!loop);
return root;
}
BSTNODE * insert(BSTNODE *root) {
/*将用户输入的结点插入二叉排序树中*/
int s;
BSTNODE *p;
printf("\n");
printf("输入插入结点数据(整数) : ");
scanf("%d",&s);
if(s != 0){p = searchnode(s,root);
if(p == NULL){ root = insert_bst(s,root);
/*输入的数据不在二叉排序树中,方可插入二叉排序树*/
print_bst(root); /*边插入边显示二叉排序树中结点值*/
if(root != NULL) printf("\n二叉排序树根结点为 %d\n\n", root->key);}
else printf("结点已存在，不再插入!!\n");}
return root;
}
search_bst(BSTNODE *root) {
/*在二叉排序树中查询用户输入的结点是否存在*/
int s;
BSTNODE *p;
printf("\n"); printf("输入待查结点值(整数): "); scanf("%d",&s);
if(s != 0)
{p = searchnode(s, root);
if(p == NULL) printf("结点不存在 !\n");
else printf("结点存在 !\n");}
}
BSTNODE *delete(BSTNODE *root) {
/*在二叉排序树中删除用户指定的结点*/
int s;
BSTNODE *p;
char ch;
printf("\n"); printf("输入待删除结点值(整数): "); scanf("%d", &s);
if(s != 0)
{ p = searchnode(s,root); /*用户指定要删除的结点存在吗?*/
if(p == NULL) printf("结点不存在 !\n\n"); /*结点不存在 */
else { printf("结点存在,删除吗 ?(Y/N) ");
fflush(stdin);
scanf("%c",&ch);
if((ch=='y')||(ch =='Y')) {root = dele_bst(p,root); print_bst(root);} /*结点存在,确认删除*/
}
}
return root;
}
main()
{
BSTNODE *root;
int loop, i;
loop = 1;
while(loop)
{ printf("\n\n\n");
printf(" 1: 二叉排序树 --- 建立\n");
printf(" 2: 二叉排序树 --- 插入\n");
printf(" 3: 二叉排序树 --- 查找\n");
printf(" 4: 二叉排序树 --- 删除\n");
printf(" 5: 二叉排序树 --- 显示\n");
printf(" 0: 退出\n");
scanf("%d",&i);
switch(i)
{ case 0: loop = 0; break; /*退出*/
case 1: root = creat_bst(); break; /*建立*/
case 2: root = insert(root); break; /*插入*/
case 3: search_bst(root); break; /*查找*/
case 4: root = delete(root); break; /*删除*/
case 5: printf("\n"); /*显示*/
if(root != NULL) printf("二叉排序树的根是%d\n",root->key);
print_bst(root); break;
}
}
}
