二叉排序树(BST)

/*************************************
二叉排序树(BinarySortTree)
by Rowandjj
2014/7/11
*************************************/
#include<iostream>
using namespace std;
//-----------------------------------
typedef int KeyType;
typedef struct _BSTNODE_//结点类型
{
	KeyType key;//结点值
	struct _BSTNODE_ *lChild;//左孩子
	struct _BSTNODE_ *rChild;//右孩子
}BstNode;
typedef BstNode *BSTree;//BsTree是二叉排序树的类型
//-----------------------------------
void Insert_BST(BSTree *Tptr,KeyType key);//将值为key的结点插到二叉排序树的合适位置(非递归)
BSTree Create_BST(void);//构建二叉排序树
void DelNode_BST(BSTree *Tptr,KeyType key);//删除二叉排序树中值为key的结点
void MidTravel_BST(BSTree T);//中序遍历二叉排序树--->有序
BstNode* SearchBST(BSTree T,KeyType key);//递归
BstNode* SearchBST_2(BSTree T,KeyType key);//非递归
//------
void DelNode_BST(BSTree *Tptr,KeyType key)
{
	BstNode *parent=NULL,*p=*Tptr,*q,*child;
	//1.查找
	while(p)
	{ 
	    if(p->key==key) 
			break;
		parent=p; //parent指向*p的双亲
		p=(key<p->key) ? p->lChild : p->rChild;
        }
    if(!p)//找不到被删结点则返回
	{
		return;
	}
	//2.删除
	q=p;//q记住被删结点p
	if(q->lChild&&q->rChild)//*q的两个孩子均非空，故找*q的中序后继*p
	{
		for(parent=q,p=q->rChild;p->lChild;parent=p,p=p->lChild);
	}
	child=(p->lChild)?p->lChild:p->rChild;
    if(!parent)//*p的双亲为空，说明*p为根，删*p后应修改根指针
	{
		*Tptr=child;
	}
    else//*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
	{
      if(p==parent->lChild) 
	  {
		parent->lChild=child; 
	  }  
      else 
	  {
		parent->rChild=child;
      }
	  if(p!=q)
	  {
		q->key=p->key;
	  } 
    }
    free(p);
}
BstNode* SearchBST(BSTree T,KeyType key)//递归版本
{
	if(!T || T->key == key)
	{
		return T;
	}
	if(T->key < key)
	{
		return SearchBST(T->rChild,key);
	}else
	{
		return SearchBST(T->lChild,key);
	}
}
BstNode* SearchBST_2(BSTree T,KeyType key)
{
	BstNode *p = T;
	while(p)
	{
		if(p->key == key)
		{
			return p;
		}else if(p->key < key)
		{
			p = p->rChild;
		}else
		{
			p = p->lChild;
		}
	}
	return NULL;
}
void MidTravel_BST(BSTree T)
{
	if(T != NULL)
	{
		MidTravel_BST(T->lChild);
		cout<<T->key<<" ";
		MidTravel_BST(T->rChild);
	}
}
BSTree Create_BST()
{
	BSTree T = NULL;
	KeyType key;
	cin>>key;
	while(key)//输入0停止创建
	{
		Insert_BST(&T,key);
		cin>>key;
	}
	return T;
}
void Insert_BST(BSTree *Tptr,KeyType key)//非递归
{
	BstNode *f,*p = *Tptr;
	//1.寻找待插结点的位置，用f记录待插结点的父节点
	while(p)
	{
		if(p->key == key)//树中已有key，直接返回
		{
			return;
		}
		else
		{
			f = p;
			p = (p->key > key) ? p->lChild : p->rChild;
		}
	}
	//2.创建新节点，插入之
	p = (BstNode *)malloc(sizeof(BstNode));
	if(!p)
	{
		exit(0);
	}
	p->key = key;
	p->lChild = p->rChild = NULL;
	
	if(*Tptr == NULL)//若是空树
	{
		*Tptr = p;
	
	}
	else//否则
	{
		if(f->key > key)
		{	
			f->lChild = p;
		}else
		{
			f->rChild = p;
		}	
	}
}