데이터 구조 - 두 갈래 검색 트 리 의 생 성, 결점 의 삽입 과 삭제

코드 는 다음 과 같 습 니 다:
헤더 파일 StudyBST. h

#define TRUE        1
#define ERROR       0
#define OK          1
#define REEOR       1
#define INFEASIBLE -1
#define OVERFLOW   -2
typedef int Status;

원본 파일 StudyBST. cpp

//     (BST)   ，  、    
//     ：（Binary Search Tree）        、     。        ，             
//(1)        ，                  
//(2)        ，                  
//(3)              
//   <   <  ，BST           ，         
//                 ，         
#include
#include 
#include "StudyBST.h"
typedef struct node
{
	int key;
	struct node *lchild,*rchild;
}Node,*BST;
//    BST     ，     element，      BST
bool BSTInsert(Node *&p,int element)
{
	if (NULL==p)                   //      (     )
	{
		p=(Node *)malloc(sizeof(Node));
		p->key=element;
		p->lchild=p->rchild=NULL;
		return true;
	}
	else if(element==p->key)   //      ，      
		return false;
	else if (elementkey)
		return BSTInsert(p->lchild,element);  //    ,     ，    
	else
	return BSTInsert(p->rchild,element);
}

//  BST
bool CreateBST(Node *&T,int a[],int n)
{
	T=NULL;
	int i;
	for (i=0;ikey);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
//    
void MidOrder(BST T)
{
	if(T)
	{
		MidOrder(T->lchild);
		printf("%d ",T->key);
		MidOrder(T->rchild);
	}
}
//    
void PostOrder(BST T)
{
	if(T)
	{
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		printf("%d ",T->key);
	}
}
//《    （C   ）》   ,            ，   
//        
BST SearchBst(BST T,int key)
{
	if ((!T)||(T->key==key))
		return (T);              //    
	else if(T->keyrchild,key));
	else
		return (SearchBst(T->lchild,key));
}
//        ，     true,    false,                 
Status SearchBST2(Node *T,int key,Node * f,Node *&p)
{
	if (!T)
	{
		p=f;
		return FALSE;
	}
	else if(T->key==key)
	{
		p=T;
		return TRUE;
	}
	else if(T->key>key)
		return SearchBST2(T->lchild,key,T,p);
	else 
		return SearchBST2(T->rchild,key,T,p);
}
//        
Status InsertBST(Node *T,int key)
{
	//           key ，    
	Node *p=(Node *)malloc(sizeof(Node));
	if(!SearchBST2(T,key,NULL,p))
	{
		Node *s=(Node *)malloc(sizeof(Node));
		s->key=key;
		s->lchild=NULL;
		s->rchild=NULL;
		if(!p)        //  s    
			T=s;
		else if(p->key>key)
			p->lchild=s;
		else
			p->rchild=s;
		return TRUE;
	}
	else
		return FALSE;
}
//          
Status Delete(Node *p)
{
	Node *q;
	if (!p->rchild)       //  p     
	{
		q=p;
		p=p->lchild;
		free(q);
	}
	else if (!p->lchild)   //  p     
	{
		q=p;
		p=p->rchild;
		free(q);
	}
	else          //           
	{
		q=p;
		Node *s=p->lchild;
		while(s->rchild)        //  ，       
		{
			q=s;
			s=s->rchild;
		}
		p->key=s->key;          //s          (     )
		if(q!=p)
			q->rchild=s->lchild;  //  q    
		else
			q->lchild=s->lchild;  //  q    
	free(s);
	}
	return TRUE;
}
Status DeleteBST(Node *T,int key)
{
	if (!T)
	   return FALSE;
	else if(T->key==key)
		Delete(T);
	else if(T->key>key)
		return DeleteBST(T->lchild,key);
	else 
		return DeleteBST(T->rchild,key);
}
//    
void DestoryBST(BST T)
{
	if (T)
	{
		DestoryBST(T->lchild);
		DestoryBST(T->rchild);
		delete T;
	}
}
//    
int main()
{
	int a[]={4,5,2,1,0,9,3,7,6,8};
	int len=sizeof(a)/sizeof(a[0]);
	Node *T,*temp;
    if (CreateBST(T,a,len))
	{
		PreOrder(T);
		printf("
");
		MidOrder(T);
		printf("
");
	}
	else
		printf("data error,cannot create binary search tree!
");
	if (temp=SearchBst(T,9))
	{
	     printf("Search successful!
");
		 printf("%d
",temp->key);
	}
// 	if(BSTInsert(T,-1))
// 		MidOrder(T);
	if (InsertBST(T,10))
	    MidOrder(T);
	printf("
");
	DeleteBST(T,10);
	MidOrder(T);
	printf("
");
	DestoryBST(T);
	system("pause");
	return 0;
}

참고 페이지:http://blog.csdn.net/stpeace/article/details/9067029그리고 엄 울 민 선생님 의 데이터 구조 (C 언어 판)