bst.cpp

关于二叉排序树胡数据结构程序课程设计代码

 
/***************************相关头文件和预定义*******************************/

 #include<string.h> // 字符串函数头文件
 #include<ctype.h> // 字符函数头文件
 #include<malloc.h> // malloc()等
 #include<limits.h> // INT_MAX等
 #include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
 #include<stdlib.h> // atoi()，exit()
 #include<io.h> // eof()
 #include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
 #include<sys/timeb.h> // ftime()
 #include<stdarg.h> // 提供宏va_start，va_arg和va_end，用于存取变长参数表
 
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0

 #define EQ(a,b) ((a)==(b))
 #define LT(a,b) ((a)<(b))
 #define LQ(a,b) ((a)<=(b))
 
 #define InitDSTable InitBiTree       // 构造二叉排序树和平衡二叉树与初始化二叉树的操作同
 #define DestroyDSTable DestroyBiTree // 销毁二叉排序树和平衡二叉树与销毁二叉树的操作同
 #define TraverseDSTable InOrderTraverse
 #define ClearBiTree DestroyBiTree
 typedef int Status; 
 typedef int Boolean; 

  /***************************相关的数据结构定义*******************************/

 typedef int KeyType; // 定义关键字类型为整型
 
 struct ElemType 
 { KeyType key; // 关键字
   int others;
   //char *name;
 };
 
 typedef ElemType TElemType; 

 typedef struct BiTNode
 { TElemType data; // 结点的值
   BiTNode *lchild,*rchild; // 左右孩子指针
 }BiTNode,*BiTree;

 typedef BiTree QElemType;

 typedef struct QNode
 { QElemType data;
   QNode *next;
 }*QueuePtr;

 struct LinkQueue
 { QueuePtr front,rear; // 队头、队尾指针
 };

 /***************************遍历二叉排序树时的函数*******************************/

 void Visit(ElemType c) 
 { printf("(%d,%d)",c.key,c.others);
 }

 /***************************从文本导入二叉排序树结点*****************************/
 
 void InputFromFile(FILE* f,ElemType &c)
 { fscanf(f,"%d%d",&c.key,&c.others);
 }

 /***************************由键盘输入关键字的函数*******************************/
 
 void InputKey(KeyType &k) 
 { scanf("%d",&k);
 }

 /***************************初始化二叉排序树*************************************/

 void InitBiTree(BiTree &T)
 { 
   T=NULL;
 }
 /***************************销毁二叉排序树***************************************/
 void DestroyBiTree(BiTree &T)
 { 
   if(T) // 非空树
   { DestroyBiTree(T->lchild); 
     DestroyBiTree(T->rchild); 
     free(T); 
     T=NULL; 
   }
 }
 /***************************前序遍历二叉排序树***********************************/
 void PreOrderTraverse(BiTree T,void(*Visit)(TElemType))
 { 
   if(T) // T不空
   { Visit(T->data); 
     PreOrderTraverse(T->lchild,Visit); 
     PreOrderTraverse(T->rchild,Visit); 
   }
 }

 /***************************中序遍历二叉排序树***********************************/
 void InOrderTraverse(BiTree T,void(*Visit)(TElemType))
 { 
   if(T)
   { InOrderTraverse(T->lchild,Visit); 
     Visit(T->data); 
     InOrderTraverse(T->rchild,Visit); 
   }
 }

 /***************************后序遍历二叉排序树***********************************/

 void PostOrderTraverse(BiTree T,void(*Visit)(TElemType))
 { 
   if(T) // T不空
   { PostOrderTraverse(T->lchild,Visit); 
     PostOrderTraverse(T->rchild,Visit); 
     Visit(T->data);
   }
 }

/***************************初始化队列********************************************/

void InitQueue(LinkQueue &Q)
 {
   Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); // 生成头结点
   if(!Q.front) // 生成头结点失败
     exit(OVERFLOW);
   Q.front->next=NULL; 
 }

 /***************************元素进入队列*****************************************/
   void EnQueue(LinkQueue &Q,QElemType e)
 { 
   QueuePtr p;
   p=(QueuePtr)malloc(sizeof(QNode)); // 动态生成新结点
   if(!p)
     exit(OVERFLOW); // 失败则退出
   p->data=e; 
   p->next=NULL; 
   Q.rear->next=p; 
   Q.rear=p; // 尾指针指向新结点
 }
 
/***************************弹出队头元素并删除掉*********************************/

   Status DeQueue(LinkQueue &Q,QElemType &e)
 {
   QueuePtr p;
   if(Q.front==Q.rear) // 队列空
     return ERROR;
   p=Q.front->next; // p指向队头结点
   e=p->data; // 将队头元素的值赋给e
   Q.front->next=p->next; 
   if(Q.rear==p) // 删除的是队尾结点
     Q.rear=Q.front; // 修改队尾指针指向头结点(空队列)
   free(p); 
   return OK;
 }

/***************************判断队列是否为空*************************************/

  Status QueueEmpty(LinkQueue Q)
 { 
   if(Q.front->next==NULL)
     return TRUE;
   else
     return FALSE;
 }

/***************************层次遍历二叉排序树***********************************/

void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType))
 { 
   LinkQueue q;
   QElemType a;
   if(T) // T不空
   { InitQueue(q); 
     EnQueue(q,T); 
     while(!QueueEmpty(q)) 
     { DeQueue(q,a); 
       Visit(a->data);
       if(a->lchild!=NULL) 
         EnQueue(q,a->lchild);
       if(a->rchild!=NULL) 
         EnQueue(q,a->rchild); 
     }
     printf("\n");
   }
 
 }

/***************************查找二叉排序树的关键字*******************************/


BiTree SearchBST(BiTree T,KeyType key)
 { 
   if(!T||EQ(key,T->data.key)) 
     return T; // 查找结束，返回指针T
   else if LT(key,T->data.key) 
     return SearchBST(T->lchild,key); 
   else 
     return SearchBST(T->rchild,key); 
 }

/***********************查找二叉排序树关键字并确定插入结点指针********************/

Status SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p) 
 { 
   if(!T) // 查找不成功
   { p=f; // p指向查找路径上访问的最后一个结点
     return FALSE;
   }
   else if EQ(key,T->data.key) // 查找成功
   { p=T; // p指向该数据元素结点
     return TRUE;
   }
   else if LT(key,T->data.key) // key小于T所指结点的关键字
     return SearchBST(T->lchild,key,T,p); // 在左子树中继续递归查找
   else                       // key大于T所指结点的关键字
     return SearchBST(T->rchild,key,T,p); // 在右子树中继续递归查找
 }

/***************************在二叉排序树中插入关键字*******************************/


 Status InsertBST(BiTree &T,ElemType e)
 { 
   BiTree p,s;
   if(!SearchBST(T,e.key,NULL,p)) // 查找不成功，p指向查找路径上访问的最后一个叶子结点
   { s=(BiTree)malloc(sizeof(BiTNode)); // 生成新结点
     s->data=e; 
     s->lchild=s->rchild=NULL; 
     if(!p) // 树T空
       T=s; 
     else if LT(e.key,p->data.key) // 树T不空，*s的关键字小于*p的关键字
       p->lchild=s; 
     else // 树T不空，*s的关键字大于*p的关键字
       p->rchild=s; 
     return TRUE;
   }
   else
     return FALSE; 
 }

/***************************删除树中的某个结点*************************************/

 void Delete(BiTree &p)
 { 
   BiTree s,q=p; 
   if(!p->rchild) 
   { p=p->lchild;
     free(q); 
   }
   else if(!p->lchild) 
   { p=p->rchild; 
     free(q); 
   }
   else 
   { s=p->lchild; 
     while(s->rchild) 
     { q=s; 
       s=s->rchild; 
     } // s向右到尽头(s指向待删结点的前驱结点，q指向s的双亲结点)
     p->data=s->data; 
     if(q!=p) // 情况①，待删结点的左孩子有右子树
       q->rchild=s->lchild; 
     else // 情况②，待删结点的左孩子没有右子树
       q->lchild=s->lchild; 
     free(s); 
   }
 }

/***************************删除二叉排序树中的结点*********************************/

 Status DeleteBST(BiTree &T,KeyType key)
 {
   if(!T) // 树T空
     return FALSE;
   else // 树T不空
   { if EQ(key,T->data.key) // 关键字等于树T根结点的关键字
       Delete(T); 
     else if LT(key,T->data.key) 
       DeleteBST(T->lchild,key); // 在T的左孩子中递归查找
     else 
       DeleteBST(T->rchild,key); // 在T的右孩子中递归查找
     return TRUE;
   }
 }

/************************实现二叉排序树各个操作的主模块****************************/

void main()
 {
   BiTree dt,p;
   int i,n;
   KeyType j,m;
   ElemType r,x;
   Status k;
   char ch;
   FILE *f;
   f=fopen("wenjian.txt","r"); 
   fscanf(f,"%d",&n); 
   InitDSTable(dt); 
   for(i=0;i<n;i++) // 依次在二叉排序树dt中插入n个数据元素
   { InputFromFile(f,r); 
     k=InsertBST(dt,r); // 依次将数据元素r插入二叉排序树dt中
     if(!k) // 插入数据元素r失败
       printf("二叉排序树dt中已存在关键字为%d的数据，故(%d,%d)无法插入到dt中。\n",
       r.key,r.key,r.others); 
	}
   printf("\n") ;
   
   fclose(f); 
   printf("*****                   选择需要执行的操作                 ***********\n"); 
   printf("*****  S—查找关键字(查找成功选择是否删除失败选择是否插入) ***********\n");
   printf("*****                   T—中序遍历二叉排序树              ***********\n");
   printf("*****                   P—前序遍历二叉排序树              ***********\n") ;
   printf("*****                   L—层次遍历二叉排序树              ***********\n") ;
   printf("*****                   B—后序遍历二叉排序树              ***********\n") ;
   printf("*****                   #—退出                            ***********\n") ;
   printf("\n") ;
   printf("\n") ;
   
while( ch=getchar(),ch=='P'||'T'||'S'||'#'||'L'||'B')
   {//printf("*****                   选择需要执行的操作                 ***********\n"); 
	   switch(ch)
	 {  case 'T':
		case 't':
		  { printf("\n中序遍历二叉排序树dt：\n");
			TraverseDSTable(dt,Visit); 
	    	printf("\n");
			printf("\n");	
			break;
		  }	
	    case 'P':
	    case 'p':
		  { printf("\n先序遍历二叉排序树dt：\n");
            PreOrderTraverse(dt,Visit);
			printf("\n");
			printf("\n");	
			break;
		  }
        case 'l':
	    case 'L':
		  { printf("\n层次遍历二叉排序树dt：\n");
            LevelOrderTraverse(dt,Visit);
			printf("\n");
			printf("\n");	
			break;
		  }

        case 'b':
	    case 'B':
		  { printf("\n后序遍历二叉排序树dt：\n");
            PostOrderTraverse(dt,Visit);
			printf("\n");
			printf("\n");
			break;
		  }
	    case 'S':
	    case 's':
		  { printf("\n请输入待查找的关键字的值：");
            printf("\n");
			InputKey(j); // 由键盘输入关键字j，在wenjian.cpp中
			p=SearchBST(dt,j); 
			if(p) // 找到，p指向该结点
			 { 
			   printf("dt中存在关键字为%d的结点!\n",j);
               int sh;
                printf("*****************  选择需要执行的操作   ********\n"); 
                printf("*****************  1—删除该结点%d        ********\n", j);
                printf("*****************  2—不删除该结点%d      ********\n", j);
               printf("\n");
               while(InputKey(m),sh=m)
			  {
				switch(sh)
                 
				{ case 1:
					 { 
						 DeleteBST(dt,j);
					     n--;	 
				         printf("\n中序遍历二叉排序树dt：\n");
				         TraverseDSTable(dt,Visit); // 中序遍历二叉排序树dt
			             printf("\n先序遍历二叉排序树dt：\n");
				         PreOrderTraverse(dt,Visit); // 先序遍历二叉排序树dt
                         printf("\n后序遍历二叉排序树dt：\n");
				         PostOrderTraverse(dt,Visit); // 后序遍历二叉排序树dt
                         printf("\n层次遍历二叉排序树dt：\n");
				         LevelOrderTraverse(dt,Visit); // 层次遍历二叉排序树dt
						 printf("\n");
                         printf("*********         n=%d       **************\n",n);
				        
						 break;
					 }
                
		         case 2:
					 {
						 printf("不删除此结点！\n");
					     break;
					 }
				default:
					printf("输入有误！");
				}//switch
		 break;	   }//while
             
			}//if
	      
			
			else // 未找到，p为空
			{
				printf("dt中不存在关键字为%d的结点。\n",j);	
                printf("*****************  选择需要执行的操作     ********\n"); 
                printf("*****************  1—插入该结点%d        ********\n",j);
                printf("*****************  2—不插入该结点&d      ********\n",j);
			    int mh;
               while(InputKey(m),mh=m)
			   {
					switch(mh)
                 {
		             case 1:
					  {
						x.key=j;
				       	x.others=++n;
					//	x.name="newname";
				        InsertBST(dt, x); 
						 printf("\n中序遍历二叉排序树dt：\n");
				         TraverseDSTable(dt,Visit); // 中序遍历二叉排序树dt
			             printf("\n先序遍历二叉排序树dt：\n");
				         PreOrderTraverse(dt,Visit); // 先序遍历二叉排序树dt
						 printf("\n后序遍历二叉排序树dt：\n");
				         PostOrderTraverse(dt,Visit); // 后序遍历二叉排序树dt
                         printf("\n层次遍历二叉排序树dt：\n");
				         LevelOrderTraverse(dt,Visit); // 层次遍历二叉排序树dt
						 printf("\n");
                         printf("*************           n=%d        ***************\n",n);
				         printf("\n");
						break;
					  }
				     case 2:
						 { 
						  printf("不插入！"); 
						  break;
						 }
                     default :
						 printf("输入有误！");
					
					}//switch

				    printf("\n");
			     	
			break;	}//while
			   
			}//else
			
		                break;
		 }//case
     
		case '#':exit(0);
	
   }//switch
 
  }//while
           DestroyDSTable(dt); // 销毁二叉排序树dt
		   
 }