binsorttree.cpp

这里我在学习数据结构时的练习,主要是二叉排序树的基本操作

#include "BinSortTree.h"

int BinSortTree::SearchBST(BinNode *&T,int x,BinNode *f,BinNode *&p)
{
//f指向T的双亲，初值为NULL

	if(!T)    { p=f;return 0;}     //if T==NULL,
	else if(x==T->data)   {  p=T;return 1;	}
	else if(x<T->data) return SearchBST(T->lchild,x,T,p);
	else return SearchBST(T->rchild,x,T,p);
}

int BinSortTree::InsertBST(BinNode *&T,int x)
{
	BinNode *p=NULL;
	if(!SearchBST(T,x,NULL,p))             //if search failed,then insert x;
	{
		BinNode *s=new BinNode;
		s->data=x;
        if(!p) T=s;                        
		else if(x<p->data) p->lchild=s;
		else p->rchild=s;
		return 1;
	}
	else return 0;
}

void BinSortTree::DeleteNode(BinNode *&p)
{
	BinNode *q;
	if(!p->rchild)
	{
		q=p; p=p->lchild; delete q;
	}
	else if(!p->lchild)
	{
		BinNode *q=p; p=p->rchild; delete q;
	}
	else
	{
		q=p;
		BinNode *s=p->lchild;
		while(s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		p->data=s->data;
		if(q!=p) q->rchild=s->lchild;
		else q->lchild=s->lchild;
		delete s;
	}
}

int BinSortTree::DeleteBST(BinNode *&T,int x)
{
	if(!T)return 0;
	else 
	{
		if(x==T->data){    DeleteNode(T);
		}
		else if(x<T->data) return DeleteBST(T->lchild,x);
		else return DeleteBST(T->rchild,x);
		return 1;
	}
}

void BinSortTree::print(BinNode *T)
{
	if(T)             
	{
		print(T->lchild);
		cout<<T->data<<" ";
		print(T->rchild);
	}
	
}

BinSortTree::BinSortTree(int a[],int n)
{
	root=NULL;
	for(int i=0;i<n;i++)
		InSert(a[i]);
}