데이터 구조찾기동적 탐색 표두 갈래 정렬 트 리

정의:
두 갈래 정렬 트 리 (Binary Sort Tree) 는 두 갈래 찾기 트 리 라 고도 부른다.그것 은 혹은 빈 나무 이다.또는 다음 과 같은 성질 을 가 진 이 진 트 리: 
(1) 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 은 뿌리 노드 의 값 보다 작 습 니 다.
(2) 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 이 뿌리 노드 의 값 보다 크다.
(3) 왼쪽, 오른쪽 나무 도 각각 이 진 트 리 이다.
다음 코드 에 서 는 주로 이 진 트 리 의 삽입, 삭제, 세 가지 기능 을 찾 습 니 다.구체 적 인 실현 에는 주석 이 있 습 니 다. 잘못 되 거나 이해 하지 못 하 는 부분 이 있 으 면 말씀 하 시 는 것 을 환영 합 니 다. 모두 가 공동으로 토론 합 니 다.

#include<stdio.h>
#include<malloc.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int KeyType ;
typedef struct ElemType			//      ，    ，       
{
	KeyType key;//   
}ElemType;
typedef struct BSTNode			//        
{
	ElemType data;
	BSTNode *lchild,*rchild;
}*BSTree;
void InitBSTree(BSTree &T)	//     
{
	T=NULL;
}
int SearchBST(BSTree T,KeyType key,BSTree f,BSTree &p)
//      key   ，       ，  p         ，
//       ， p                  ，   0
{
	if(!T)
	{
		p=f;
		return 0;
	}
	else if(EQ(T->data.key,key))
	{
		p=T;
		return 1;
	}
	else if(LT(T->data.key,key))
		SearchBST(T->rchild,key,T,p);
	else
		SearchBST(T->lchild,key,T,p);
}
int InsertBST(BSTree &T,ElemType e)
{
	BSTree p;
	if(!SearchBST(T,e.key,NULL,p))	//                     ，    ，  0，   ，p            
	{
		BSTree s=(BSTree)malloc(sizeof(BSTNode));
		s->data=e;
		s->lchild=s->rchild=NULL;
		if(!p)								//  p     
			T=s;
		else if(LT(e.key,p->data.key))		//                ，       
			p->lchild=s;
		else								//        
			p->rchild=s;
		return 1;
	}
	else
		return 0;
}
void Delete1(BSTree & p)
//  p    ，                 ，
//   p        ，p                p  ，
//                   ，           
//      p       ，            ，              
{
	BSTree q;
	if(p->lchild==NULL)//       ，                    
	{
		q=p;
		p=p->rchild;
		free(q);
	}
	else if(p->rchild==NULL)
	{
		q=p;
		p=p->lchild;
		free(q);
	}
	else
	{
		BSTree s=p->lchild;
		q=p;
		while(s->rchild!=NULL)
		{
			q=s;
			s=s->rchild;
		}
		p->data=s->data;
		if(q!=p)
			q->rchild=s->rchild;
		else
			q->lchild=s->lchild;
	}

}
int DeleteBST(BSTree &T,KeyType key)
{
	if(!T)
		return 0;
	else
	{
		if(EQ(key,T->data.key))
			Delete1(T);
		else if(LT(key,T->data.key))
			DeleteBST(T->lchild,key);
		else
			DeleteBST(T->rchild,key);
		return 1;
	}
}
void InOrderTraverse(BSTree T)
{
	if(T)
	{
		InOrderTraverse(T->lchild);
		printf("%d ",T->data.key);
		InOrderTraverse(T->rchild);
	}
}
int main()
{
	BSTree T,p;
	InitBSTree(T);
	int i;
	ElemType e[6];
	e[0].key=45;
	e[1].key=24 ;
	e[2].key=53;
	e[3].key=12 ;
	e[4].key=37 ;
	e[5].key=93 ;
	for(i=0;i<6;i++)
		InsertBST(T,e[i]);
	InOrderTraverse(T);
	printf("
");
	SearchBST(T,54,NULL,p);
	printf("%d
",p->data.key);
	DeleteBST(T,24);
	InOrderTraverse(T);
}