bst.cpp

这是用vc编写的二叉树排序算法 希望大家多给意见 是数据结构的一种算法

// BST.cpp: implementation of the BST class.
//
//////////////////////////////////////////////////////////////////////

#include "BST.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


bool BST::findhelp(binnode*subroot,const int& k,int& e)const
{
	if(subroot==NULL)return false;
	else if(k<subroot->val())return findhelp(subroot->left(),k,e);
	else if(k>subroot->val())return findhelp(subroot->right(),k,e);
	else{e=subroot->val();return true;}
}
binnode* BST::deletemin(binnode* subroot,binnode*& min){
	if(subroot->left()==NULL){
		min=subroot;
		return subroot->right();
	}
	else {
		subroot->setleft(deletemin(subroot->left(),min));
		return subroot;
	}
}
void BST::clearhelp(binnode* subroot){
	if(subroot==NULL) return ;
	clearhelp(subroot->left());
	clearhelp(subroot->right());
	delete subroot;
}


binnode* BST::removehelp(binnode* subroot,const int& k,binnode*& t){
	if(subroot==NULL)return NULL;
	else if(k<subroot->val())
		subroot->setleft(removehelp(subroot->left(),k,t));
	else if(k>subroot->val())
		subroot->setright(removehelp(subroot->right(),k,t));
	else{
		binnode* temp;
		t=subroot;
		if(subroot->left()==NULL)
			subroot=subroot->right();
		else if(subroot->right()==NULL)
			subroot=subroot->left();
		else{
		subroot->setright(deletemin(subroot->right(),temp));
		int te=subroot->val();
		subroot->setval(temp->val());
		temp->setval(te);
		t=temp;
		}
	}
	return subroot;
}


void BST::printhelp(binnode* subroot,int level)const{
	if(subroot==NULL)return;
	printhelp(subroot->left(),level+1);
	for(int i=0;i<level;i++)
		cout<<"   ";
	cout<<subroot->val()<<"\n";
    printhelp(subroot->right(),level+1);
}



void BST::inserthelp(binnode* &ptr ,const int& e){

        if(ptr==NULL){
			ptr=new binnode(e);
			if(ptr==NULL){cerr<<"Can not give space!";exit(1);}}
		else if(e<ptr->val())inserthelp(ptr->left(),e);
		else if(e>=ptr->val())inserthelp(ptr->right(),e);
}



void BST::upprint()
{
 up(root);

}



void BST::downprint()
{
 down(root);

}



void BST::up(binnode *root)
{
	if(root==NULL)return; 	
	else
	{
		up(root->left());
		cout<<root->val()<<" ";
		up(root->right());
		
	}
}


void BST::down(binnode *root)
{
	if(root==NULL)return; 	
	else
	{
		down(root->right());
		cout<<root->val()<<" ";
		down(root->left());
		
	}


}