BST C

来自"NOCOW"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_NODE 100
typedef struct node 
{
      int data;
      struct node *l,*r;
}BST ;
BST *insert_bst(BST *root,int value)
{
    BST **p;
    p=&root;
    while (*p!=NULL)
    {
          if((*p)->data>value)
          p=&((*p)->l);
          else
          p=&((*p)->r);
    }
    *p=(BST*)malloc(sizeof(BST));
    (*p)->data=value;
    (*p)->l=NULL;
    (*p)->r=NULL;
    return root;
}
void mid_output(BST *pt)
{
 	 if(pt!=NULL)
 	 {
	 mid_output(pt->l);
	 printf("%d ",pt->data);
	 mid_output(pt->r);
	 } 
}
BST *creat_bst(BST *root,int *data,int i ,int n)
{
	for (;i<n;)
	root=insert_bst(root,data[i++]);
	return root;
}
BST **search_bst(BST **p,int value)
{
	while(*p!=NULL)
	{
		if ((*p)->data==value)
		return p;
		else
		{
			if ((*p)->data>value)
			p=&((*p)->l);
			else
			p=&((*p)->r);
		}
	}
	return p;
}
BST *del(BST *root)
{
	BST *p,*q,*r;
	q=root;
	if(q->l==NULL)
	p=q->r;
	else
	if(q->r==NULL)
	p=q->l;
	else
	{
		p=q->l;
		r=q->r;
		q=q->l;
		while (q->r!=NULL)
		q=q->r;
		q->r=r;
	}
	free(root);
	return p;
}
int main(void)
{
    int data1[MAX_NODE]={0},n,value ;
    int i,data = 0 ;
    BST *root=NULL,*pt,*temp,**f ;
    FILE *in1;
    /*Input the data */
    in1=fopen("a.in","r");
    fscanf(in1,"%d",&n) ;
    for(i=0 ; i< n; i++)
    fscanf(in1,"%d",&data1[i]) ;
    root = creat_bst(root,data1,0,n) ; /*建立二叉排序树*/
    if( root )
    printf("Good,The bst tree is creat!!!\n");
    printf("Now,which do  you want to do?\n");
    printf("NO.1 Find a Node in BST !!!\n");
    printf("NO.2 Del  a  Node from BST !!!\n");
    printf("NO.3 Insert a Node into BST !!!\n");
    printf("NO.4 Print the Node messeage!!!\n");
    printf("Please Input a data to do (0 to end) : ");
 
    while ( scanf("%d",&data) != EOF && data != 0 )
    {
          switch ( data )
          {
                 case 1: printf("Please input the node's value :  ");
                         scanf("%d",&value) ;
                         temp = *search_bst (&root,value) ;
                         if( temp )
                         printf("The node is find !!!\n");
                         else
                         printf("Sorry,The node is not find!!!\n");
                         break ;
 
                 case 2: printf("Please input the node's value :  ");
                         scanf("%d",&value) ;
                         f=search_bst(&root,value);
                         if( *f )
                         {//if root is deleted , temp shall be NULL and root shall to ,but in this way it won't
                             if ((*f)->data==root->data)
                             f=&root;
                             *f=del(*f);
                             printf("The node is deleted!!!\n");
                             mid_output(root) ;
                             printf("\n");
                         }
                         else
                         {
                             printf("The node is not found!!!  or every thing is over......\n");
                         }
 
                         break ;
 
                 case 3: printf("Please input the new node's value : ");
                         scanf("%d",&value) ;
                         root = insert_bst(root,value) ;
                         printf("The node is inserted!!!\n");
                         mid_output(root) ;
                         printf("\n");
                         break ;
 
                 case 4: printf("Now,the BST's Node is : ") ;
                         mid_output(root) ;
                         break ;
                 case 5: printf("\n %d  \n",root->data);                
                 default: break ;
          }
    }
 
 
 return 0 ;
}