二叉排序树

#include <bits/stdc++.h>
using namespace std;
struct node{
	int n;
	struct node *lc,*rc;
};
node *getnum(node *root,int a)
{
	if(root == NULL)return NULL; 
	node * T = root;
	while(T)
	{
		if(a > T->n)
		{
			T = T->rc;
		}else if(a < T->n)
		{
			T = T->lc;
		}else if(a == T->n)
		{
			return T;
		}
    }
    return NULL;
} 
void Insert(node *&root,int a)
{

	node *p =new node;
	p->lc = NULL; 
	p->rc = NULL;
	p->n = a;
	if(root == NULL)
	{
		root = p;
		return ;
	}
	
	if(getnum(root,a) != NULL)return;//这个数在二叉查找树中已经存在 
	
	node * T = NULL;
	node * N = root;

	while(N!=NULL)
	{
	
		T = N;
		if(a > N->n)
		N = N->rc;
		else N = N->lc;
    
	}
	if(a < T->n)  T->lc = p;
	else if(a > T->n) T->rc = p;
 	return ;
}
void dele(node *&root,int a)
{
		if(root == NULL)return ; 
	node * T = root;
	node * LT = NULL; 
	int nf=-1;
	while(T)
	{
		if(a > T->n)
		{
			LT = T;
			T = T->rc;
			nf = 0;
		}else if(a < T->n)
		{
			LT = T;
			T = T->lc;
			nf = 1;
		}else if(a == T->n)
		{
			
		     if(T->lc&&T->rc)//有左右子树 
		     {
		     	node * rmin = T->rc;//找T中右子树最小的代替T的位置 
		     	node * rrmin = NULL;
		     	while(rmin->lc)
		     	{
		     		if(rmin->lc!=NULL)rrmin= rmin,rmin = rmin->lc;
				}
				
				if(LT!=NULL)//若非根节点，找直接前驱 
				{
				if(nf)LT->lc = rmin;
				else LT->rc = rmin;
				} 
				
				if(rrmin==NULL)
				{
					rmin->lc = T->lc;
					rmin->rc =NULL;
				}
				else 
				{
				rmin->lc = T->lc;
		     	rmin->rc = T->rc;
				rrmin->lc = NULL;
				if(LT==NULL)root = rmin;//删除的是根节点  
			    }
				 
		     	free(T);
		     	return ;
		     	
			 }else if(T->lc||T->rc)
			 {
			 	if(nf&&T->lc)LT ->lc = T->lc;//n = 1 表示 T是LT的左子树 
			 	else if(nf&&T->rc) LT->lc = T->rc;
			 	else if(T->lc) LT->rc = T->lc;
			 	else if(T->rc) LT->rc = T->rc;
			 	free(T);
			 	return ;
			 }else
			 {
			 	if(nf)LT->lc = NULL;
			 	else LT->rc = NULL;
			 	free(T);
			 	return ;
			 }
		}
    }
	
}
void build_tree(node *&root,int &num)
{
	int arr[11] = {17,12,19,10,15,18,25,8,11,13,16};
	int n = 11;

	for(int i=0;i<n;i++)
	{
		Insert(root,arr[i]);
		num++;
	}
}
void trave(node *root,int num)
{
	queue<node*> q;
	while(!q.empty())q.pop();
	if(root==NULL)return ;
	q.push(root);
	while(!q.empty())
	{
	   node *t = q.front();
	   q.pop(); 
	   printf("%d ",t->n);
	   if(t->lc)q.push(t->lc);
	   if(t->rc)q.push(t->rc);
	}
	printf("\n");
} 
int main()
{
	node * root=NULL; 
	int num=0;
	build_tree(root,num);
	trave(root,num);
	dele(root,17);
	trave(root,num);
	return 0;	
}