binsearchtree1.cpp

二叉搜索树的基本操作

#include<iostream.h>
#include<stdlib.h>

#include"binSearchTree1.h"

void InitBSTree(BSTNode* & BST)
{
	BST=NULL;
}

bool BSTreeEmpty(BSTNode* BST)
{
	return BST==NULL;
}

bool Find(BSTNode *BST,ElemType &item)
{
	if(BST==NULL) return false;
	else{
		if(item ==BST->data){
			item= BST->data;
		    return true;
		}
	    else if(item<BST->data)
		    return Find(BST->left,item);
    	else
	     	return Find(BST->right,item);
	}
}

bool Update(BSTNode* BST,const ElemType& item)
{
	if(BST==NULL) return false;
	else{
		if(item==BST->data) {
			BST->data =item;
			return true;
		}
		else if(item<BST ->data)
			return Update(BST->left,item);
		else 
			return Update(BST->right,item);
	}
}

void Insert(BSTNode* &BST,const ElemType& item)
{
	if(BST==NULL)
	{
		BSTNode* p=new BSTNode;
		p->data=item;
		p->left=p->right=NULL;
		BST=p;
	}
	else if(item<BST->data)
		 Insert(BST->left,item);
	else 
		Insert(BST->right,item);
}

bool Delete(BSTNode * &BST,const ElemType &item)
{
	BSTNode *t = BST,*s=NULL;
	while(t!=NULL) {
		if(item==t->data) break;
		else if(item<t->data){
			s=t;t=t->left;
		}
		else{s=t;t=t->right;}
	}
	if(t==NULL)return false;
	if(t->left ==NULL&&t->right==NULL)
	{
		if(t==BST)
			BST=NULL;
		else if(t==s->left)
			s->left=NULL;
		else
			s->right =NULL;
		delete t;
	}
	else if(t->left==NULL||t->right==NULL)
	{
		if(t==BST){
			if(t->left==NULL)
				BST =t ->right;
			else
				BST=t->left;
		}
		else{
			if(t==s->left&&t->left!=NULL)
				s->left=t->left;
			else if(t==s->left&&t->right!=NULL)
				s->left=t->right;
			else if(t==s->right&&t->left!=NULL)
				s->right=t->left;
			else if(t==s->right &&t->right!=NULL)
				s->right=t->right;
		}
		delete t;
	}
	else if(t->left!=NULL && t->right!=NULL)
	{
		BSTNode *p=t,*q=t->left;
		while(q->right!=NULL){
			p=q;
	    	q=q->right;
		}
    	t->data=q->data;
    	if(p==t)t->left=q->left;
    	else p->right =q->left;
    	delete q;
	}
    return true;
}

  void CreateBSTree(BSTNode *&BST,ElemType a[],int n)
  {
	  BST=NULL;
	  for(int i=0;i<n;i++)
		  Insert(BST,a[i]);
  }

  void Inorder(BSTNode *BST)
  {
	  if(BST!=NULL){
		  Inorder(BST->left);
		  cout<<BST->data<<' ';
		  Inorder(BST->right);
	  }
  }

  int BSTreeDepth(BSTNode *BST)
  {
	  if(BST==NULL)
		  return 0;
	  else
	  {
		  int dep1 =BSTreeDepth(BST->left);
		  int dep2 =BSTreeDepth(BST->right);
		  if(dep1>dep2)return dep1 +1;
		  else return dep2 +1;
	  }
  }


int BSTreeCount(BSTNode *BST)
{
	if(BST ==NULL) return 0;
	else
		return BSTreeCount(BST->left)+BSTreeCount(BST->right)+1;
}

int BSTreeLeafCount(BSTNode *BST)
{
	if(BST == NULL) return 0;
	else if(BST->left == NULL && BST->right == NULL) return 1;
	else return BSTreeLeafCount(BST->left)+BSTreeLeafCount(BST->right);
}
void PrintBSTree(BSTNode  * BST)
{
	if(BST==NULL) return;
	else{
		cout<<BST->data;
		if(BST->left!=NULL || BST->right!=NULL)
		{
			cout<<'(';
			PrintBSTree(BST->left);
			if(BST->right!=NULL)
				cout<<',';
			PrintBSTree(BST->right);
			cout<<')';
		}
	}
}

void ClearBSTree(BSTNode *& BST)
{
	if(BST!=NULL)
	{
		ClearBSTree(BST->left);
		ClearBSTree(BST->right);
		delete BST;
		BST = NULL;
	}
}