二叉排序树.c

二叉排序树,建立一棵二叉树树,并输入数字进行排序

#include<stdio.h>
#include<malloc.h>
#define OVERFLOW -2
#define OK 1
#define TURE 1
#define FALSE 0
#define Insert_Fail 0;
#define Insert_Success 1;
//对于数值型关键字
#define EQ(a,b) ((a)==(b)) 
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef struct     //查找表data类型
{
	int  key;      //关键字项
    char c;        //其它数据项
}TElemType;
typedef struct BiTNode 
{ 
   TElemType  data; 
   struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree;

//*1二叉排序树的查找
int SearchBST(BiTree T,int key,BiTree f,BiTree *p)//T为根节点，f为p的父结点，p为查找到后返回的节点
{
	if(!T)               //T为空，查找失败
	{
		(*p)=f;
		return FALSE;
	}
	else if(EQ(key,T->data.key))
	{
		(*p)=T;            //要查找的为根节点
		return TURE;
	}
	else if(LT(key,T->data.key))
		return SearchBST(T->lchild,key,T,p);    //在左子树中继续查找
	else
		return SearchBST(T->rchild,key,T,p);   //在右子树中继续查找
}
//*2二叉排序树的插入
int InsertBST(BiTree *T,TElemType e) 
{
	BiTNode *s;
	int result;
	BiTree p;
	s=(BiTNode*)malloc(sizeof(BiTNode));
	s->data=e;   
	s->lchild=s->rchild=NULL;
    result=SearchBST(*T,e.key,NULL,&p); 
    if(result==TURE) return Insert_Fail;                     // 插入失败  
    if(!p)   	(*T)=s;                                      // 插入 s 为新的根结点
      else if(LT(e.key,p->data.key))      p->lchild=s;       // 插入 *s 为 *p 的左孩子
	  else  p->rchild=s;                                     // 插入 *s 为 *p 的右孩子
	return Insert_Success;                                   // 插入成功
} // Insert BST
//3二叉排序树的删除
int Delete(BiTree *f, BiTree *p)//从二叉排序树中删除结点 p，重接它的左(右)子树
{
	BiTree q,s;
	if(!((*p)->rchild)&&!((*p)->lchild)) 
    {  
		if((*f)->lchild==(*p)) (*f)->lchild=NULL;
        else (*f)->rchild=NULL;  
		free(*p);
	} 
    else if(!((*p)->rchild)) 
    {  
		if((*f)->lchild==(*p)) (*f)->lchild=(*p)->lchild;
          else 	(*f)->rchild=(*p)->lchild; 
		free(*p);
	} 
	else if(!((*p)->lchild)) 
    {  
		if((*f)->lchild==(*p)) 	(*f)->lchild=(*p)->rchild;
        else 	(*f)->rchild=(*p)->rchild; 
		free(*p);
	} 
	else                      // 左右子树均不空
	{  
		q=*p;  
		s=(*p)->lchild;
		while(s->rchild)
		{ 
			q=s; 
			s=s->rchild;
		}                      // s 指向被删结点的前驱
		(*p)->data=s->data;
		if(q!=*p)  q->rchild=s->lchild;
		else  q->lchild=s->lchild;
		free(s);
    }
	return TURE;
}
int DeleteBST(BiTree T,BiTree f,int key)
{
	if(!T)	return FALSE;
	else{
		if(EQ(key,T->data.key))
			return  Delete(&f,&T);
		else if(LT(key,T->data.key))
			return DeleteBST(T->lchild,T,key);
		else
			return DeleteBST(T->rchild,T,key);
	}
}
//*4遍历
void Preorder(BiTree T,void(*visit)())// 先序遍历二叉树 
{                    

	if(T) 
	{
		(*visit)("%d\t",(T->data).key);                    // 访问结点
	    Preorder(T->lchild, *visit);  // 遍历左子树
        Preorder(T->rchild, *visit); // 遍历右子树
    }
}
void Inorder(BiTree T,void(*visit)())// 中序遍历二叉树 
{                    
   if (T) 
   {
      Inorder(T->lchild,*visit);   // 遍历左子树
      (*visit)("%d  ",(T->data).key);                // 访问结点
      Inorder(T->rchild,*visit);  // 遍历右子树
   } 
   
}

void main()
{
	BiTree T;
	int a[10]={503,87,512,061,908,170,897,275,653,426};
	TElemType b[10],e1,e2;
	int i;
	int key1,key2,key3;
	T=NULL;
	key1=653;
	key2=512;
	key3=87;
	e1.key=136;
	e2.key=56;
	for(i=0;i<=9;i++)	
		b[i].key=a[i];
	printf("想要建立的二叉排序树中的节点为");
    for(i=0;i<=9;i++)
		printf("%d  ",b[i].key);
	printf("\n");
	printf("将这些节点插入到二叉排序数后，中序遍历这个树为\n");
	for(i=0;i<=9;i++)	InsertBST(&T,b[i]);
	Inorder(T,printf);
	printf("\n");
	printf("插入节点136后，中序遍历这个树为\n");
	InsertBST(&T,e1);
	Inorder(T,printf);
	printf("\n");
	printf("插入节点56后，中序遍历这个树为\n");
	InsertBST(&T,e2);
	Inorder(T,printf);
    printf("\ninsert over\n");
    printf("删除节点653后，中序遍历这个树为\n");
	DeleteBST(T,NULL,key1);
	Inorder(T,printf);
	printf("\n");
	printf("删除节点512后，中序遍历这个树为\n");
	DeleteBST(T,NULL,key2);
	Inorder(T,printf);
	printf("\n");
	printf("删除节点87后，中序遍历这个树为\n");
	DeleteBST(T,NULL,key3);
	Inorder(T,printf);
	printf("\n");
}