データ構造-ツリーの並べ替え

二叉ソートツリー(Binary SortTree):
下記の性質を持つ二叉樹:
(1)左のサブツリーが空でない場合、左のサブツリーのすべてのノードの値は、そのルートのノードの値より小さい.
(2)右のサブツリーが空でない場合、右のサブツリーのすべてのノードの値は、そのルートのノードの値よりも大きい.
(3)左、右のツリーもそれぞれ二叉の順序付けツリーである.

#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct node        	//    
{	
  int key;            	//    
  struct node *lchild,*rchild;	//      
} BSTNode,*BSTree;

void InsertBST(BSTree *t,int k)
{
 BSTNode *f,*p=*t;
 while(p)
 {
     if(p->key==k) return;//       
     f=p;
     p=(k<p->key)?p->lchild:p->rchild;
 }
 p=(BSTree)malloc(sizeof(BSTNode));
 p->key=k;
 p->lchild=p->rchild=NULL;
 if(*t==NULL) *t=p;
 else if (k<f->key) f->lchild=p;
      else f->rchild=p;
}

BSTree SearchBST(BSTree t, int k)
{ 
  BSTree p;
  p=t;
  while((p!=NULL)&&(p->key!=k))
      if(k<p->key)  p=p->lchild;
      else  p=p->rchild;
   return(p);
}

BSTree InsertBST2(BSTree t,int k)//     k，   
{
	//       t       k，   ，      
	
	BSTree p=t;//p        
	BSTree f;//f         
	while(p)//      ,             
	{
		if(p->key==k)//    k，    
		{
			cout<<"    "<<k<<",    "<<endl;
			return t;
		}
		f=p;
       // k<p->key，       ，         
		p=(k<p->key)?p->lchild:p->rchild;
	}
	p=(BSTree)malloc(sizeof(BSTNode));
	p->key=k;
	p->lchild=p->rchild=NULL;
	if(t==NULL)t=p;//          
	else if(k<f->key)f->lchild = p;//        
	else f->rchild = p;//        
	return t;
}

void DelBST(BSTree *t,int k)
{
/*      *t       k   */
 BSTree p,f,q,s,root;
 root=*t;
 p=*t;  f=NULL;
 while(p)
    {if(p->key==k) break;                        /*      k   */
     f=p;
     p=(k<p->key)?p->lchild:p->rchild;
   /*      *p  、      */
    }
 if(!p) return;                     /*           k   */
 if(p->lchild==NULL&&p->rchild==NULL)
   {if(p==*t) *t=NULL;
    else if(p==f->lchild) f->lchild=NULL;
	 else f->rchild=NULL;
    free(p);
    }
 else
   if(p->lchild==NULL&&p->rchild!=NULL)                    /* *p    */
       { if(f->lchild==p)
	       f->lchild=p->rchild;  /* *p               */
	     else
	       f->rchild=p->rchild;  /* *p               */
	 free(p);
       }
   else if(p->rchild==NULL&&p->lchild!=NULL)              /**p    */
	   { if (f->lchild==p)              /* *p      *p*/
		  f->lchild=p->lchild;
		else
		  f->rchild=p->lchild;
	      free(p);
	    }
	 else if(p->lchild!=NULL&&p->rchild!=NULL)
		{q=p;s=p->lchild;
		 while(s->rchild) {q=s;s=s->rchild;}
		 p->key=s->key;
		 if(q!=p) q->rchild=s->lchild;
		 else q->lchild=s->lchild;
		 free(s);
		 }
}

void InorderBSTree(BSTree p)
{
  if(p)
  {
   InorderBSTree(p->lchild);
   printf("%d ",p->key);
   InorderBSTree(p->rchild);}
 }
void operation()
{	
	cout<<"\t0,    "<<endl;
	cout<<"\t1,          "<<endl;
	cout<<"\t2,             "<<endl;
	cout<<"\t3,             "<<endl;
	cout<<"\t4,             "<<endl;
	cout<<"\t5,         "<<endl;
}
int main()
{
	BSTree t=NULL,p;
	int k,key;
	operation();
	while(true)
	{
	   printf("\t       :
");
	   scanf("%d",&k);
	   switch(k)
	   {
	   case 0: exit(0); 
	   case 1: printf("        , 0  :
");
		       scanf("%d",&key);
               while(key)
			   {
				  InsertBST(&t,key);
				  scanf("%d",&key);
			   }
			  printf("         :
");
			  break;
	   case 2: printf("               :
");
		       scanf("%d",&key);
			   p=SearchBST(t,key);
			   if(p==NULL) printf("        
");
               else printf("      
");
	           break;
	   case 3: printf("         :
");
			   scanf("%d",&key);
			   InsertBST2(t,key);
			   printf("      
");
			   break;
	   case 4: printf("               :
");
		        scanf("%d",&key);
                DelBST(&t,key);
				printf("      
");
				break;
	   case 5: printf("                :
");
		       InorderBSTree(t);
			   break;
		default:printf("         ");break;

	   }

	}
	return 0;
}