习题6-二叉排序树的综合练习.c

数据结构各章实验源代码； 数据结构实验源代码

#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 = malloc(sizeof(BSTNODE));
           p->lchild = NULL;    p->rchild = NULL;    p->key = w;}   /*如果二叉排序树空,p作为新二叉排序树的根结点*/
   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;
          }
    }
}