binarysorttree.c

一个算法问题包括

#define TRUE 1
#define FALSE 0
#include "stdio.h"
# define EQ(a,b) ((a)==(b))
# define LT(a,b)  ((a)<(b))
# define LQ(a,b)  ((a)>(b))
typedef struct data{
        int key;
}ElemType;
typedef struct BSTNode{
  ElemType data;
  struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

void CreatBST(BiTree &T,ElemType e){
	s=(BiTree)malloc(sizeof(BiTNode));
	s->data=e;
	s->lchild=s->rchild=NULL;
	T=s;
}
void InsertBST(BiTree &T,ElemType e){
    BSTree p；p=T;
	if(!p){
	s=(BiTree)malloc(sizeof(BiTNode));
	s->data=e;
	s->lchild=s->rchild=NULL;
    if LT(e.key,p->data.key)p->lchild=s;
    else if LQ(e.key,p->data.key) p->rchild=s;
     else printf("It is Equle!\n");
     return TRUE;
	}
	else return FALSE;
}
/*InsertBST*/

void DeleteBST(Bitree t,ElemType x)
{	Bitree p,q,r,h;
      	p=t;                         
        q=NULL;                      
    	while(p!=NULL&&(p->data.key!=x))
		if(x<p->data.key)
                  {   q=p;
		      p=p->lchild;
		   }
		 else
		  { q=p;
		    p->rchild;
		  }
		if(p==NULL)printf("Have't found the node you want !\n");
		else if(p->lchild==NULL)            
		   {if(q==NULL)h=p->rchild;
		        else if(q->lchild==p)q->lchild=p->rchild;
		        else q->rchild=p->rchild;
		   }
		else                                
		{ 
			r=p->lchild;
		   while(r->Rchild!=NULL)
			   r=r->rchild;    
		     r->Rchild=p->rchild;     
			 if(q==NULL)h=p->lchild;   
			 else if(q->lchild==p) q->lchild=p->lchild;
			 else q->rchild=p->lchild;
		}
}
/* DeleteBST*/

void main()
{      Bitree t;
            CreatBST(t);
	    BSTNode *s;
	    printf("Please input the information of the 6 key!\n");
       for(int i=0;i<6;i++)
	   {scanf("%d",&s->data.key);
	    	InsertBST( t, s);
	   }
}