[数据结构课程设计——C语言描述第2版 程序源代码

[数据结构课程设计——C语言描述（第2版）][阮宏一,宋婉娟][程序源代码].zip

// 进行二叉排序树和文件操作的主程序文件 bst_and_file.c

#include“bst_and_file.h“  //二叉排序树的头文件

//0.  初始化二叉排序树，即把树根指针置空
PBinTree InitBSTree（ ）
{  
	return NULL;
}

//1. 串比较函数
static int operator_equal（const ElemType *x1 const ElemType *x2） 
{
    // 元素相等比较 ==
    return strcmp（x1->num x2->num）==0;
}

static int operator_small（const ElemType *x1 const ElemType *x2） 
{
    //元素小于比较 <
  	return strcmp（x1->num x2->num）<0;
}

//2. 判断二叉排序树是否为空
int BSTreeEmpty（PBinTree BST）
{
     return BST==NULL;
}

//3. 在二叉排序树中查找元素
int Find（PBinTree BST ElemType *item）
{
     if（BST==NULL） 
		 return 0;  
     else 
	 {
         if（operator_equal（item&BST->data）） 
		 { 
             item=&BST->data; 
			 printf（“     查找值为：  %s   %d\n“BST->data.numBST->data.grade）;//输出查找到的值
			 return 1;
		 }
         else 
		 {	if（operator_small（item&BST->data））                   //递归排序左子树
                  return Find（BST->left item）;  
			else                                                  //递归排序右子树
                  return Find（BST->right item）;
		 }
     }
}

//4. 更新二叉排序树中的结点值
int Update（PBinTree BST ElemType *item）
{
     if（BST==NULL） 
		return 0;
     else 
	 {
       if（operator_equal（item&BST->data）） 
	   {
           BST->data=*item; return 1;
	   }
       else if（operator_small（item&BST->data））
               return Update（BST->left item）;
       else
               return Update（BST->right item）;
	 }
}

//5. 向二叉排序树中插入元素
void Insert（PBinTree *BST const ElemType *item）
{
     if（*BST==NULL） 
     { 
         struct BSTNode *p=（struct BSTNode *）malloc（sizeof（struct BSTNode））;
         p->data=*item; 
         p->left=p->right=NULL;
         *BST=p;
	 }
     else 
	 {  if（operator_small（item&（*BST）->data））
            Insert（&（*BST）->left item）;  //向左子树中插入元素
        else
            Insert（&（*BST）->right item）; //向右子树中插入元素
	 }
}

//6. 从二叉排序树中删除元素
int Delete（PBinTree BST const ElemType *item）
{    
  //从二叉排序树中查找值为item的待删结点，指针t指向待比较的结点，
  //指针s指向t的双亲结点，从树根结点开始比较。
     PBinTree t=BST s=NULL;
     while（t!=NULL） 
	 {
          if（operator_equal（item&t->data）） 
			  break;
          else
		  {	if（operator_small（item&t->data）） 
			{	s=t; 
				t=t->left;
			}
			else 
			{
				s=t; 
				t=t->right;
			}
		  }
	 }//endwhile
    
	if（t==NULL） return 0;  //若没有找到待删除的结点，则返回假
  
	//分三种不同情况删除已查找到的t结点且保证二叉排序树的有序性不变
    
	if（t->left==NULL && t->right==NULL） 
    {   //对t结点（即待删除的结点）为叶子结点的情况进行处理
        if（t==BST） 
			BST=NULL;
        else 
		{	if（t==s->left） 
				s->left=NULL;
			else 
				s->right=NULL;
		}
        free（t）;//
    }
    else 
	{	if（t->left==NULL || t->right==NULL）
		{	//对t结点为单分支结点的情况进行处理
			if（t==BST） 
			{  //删除树根结点
				if（t->left==NULL） 
					BST=t->right;
				else 
					BST=t->left;
			}
			else 
			{ //删除非树根结点时，分四种情况进行处理
				if（t==s->left && t->left!=NULL） 
					s->left=t->left;
				else 
					if（t==s->left && t->right!=NULL）

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件       11466  2016-06-20 15:34  bst_and_file.c
     文件        1183  2016-06-18 22:43  bst_and_file.h
     文件        9113  2016-08-21 19:21  串基本操作演示.c
     文件        6846  2010-12-05 11:14  二叉树的基本操作.c
     文件        4631  2016-06-11 20:35  哈夫曼编码.c
     文件        9100  2016-08-04 15:36  学生通讯录管理系统.c
     文件       12312  2010-07-11 16:34  广义表.c
     文件        3127  2010-07-11 15:13  文学研究助手.c
     文件       22184  2016-07-31 20:36  校园导游系统2016.c
     文件       11583  2010-07-03 14:13  模拟动态存储管理设计.c
     文件        9736  2016-08-22 12:07  稀疏矩阵运算器.c
     文件       10053  2016-08-22 16:49  航班信息查询与检索.c
     文件       22556  2016-08-20 20:43  航空客运订票系统.c
     文件        3928  2016-08-20 18:36  表达式求值.c
     文件       12792  2016-08-02 18:45  银行排队系统.c