bst.cpp

代码实现了二叉树基本操作:实现二叉树的基本操作（包括前序、中序、后序遍历）；从键盘读数

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

#include "BST.h"

//////////////////////////////////////////////////////////////////////
// Destruction
//////////////////////////////////////////////////////////////////////

//析构函数
BST::~BST()
{
	MakeEm(root);
}

//得到根节点地址指针
 BstNode * BST::Getroot()
 {
	  return root;
 }


 //在二叉树中插入元素
void BST::Insert(const int x,BstNode *&ptr)
 {
    if(ptr==NULL)
		ptr=new BstNode(x,NULL,NULL);
    else if(x < ptr->data) Insert(x,ptr->leftc);
	else if(x > ptr->data) Insert(x,ptr->rightc);
 }

//清空二叉树
void BST::MakeEm(BstNode* &ptr)
{
	if(ptr==NULL) return ;
	MakeEm(ptr->leftc);
	MakeEm(ptr->rightc);
	delete ptr;
}

//按照中序遍历二叉树
void BST::PrintTree(BstNode *&ptr) const 
{
	if(ptr==NULL) return ;
	PrintTree(ptr->leftc) ;
	cout << ptr->data <<" ";
	PrintTree(ptr->rightc);
}

void BST::PrintTree1(BstNode *&ptr) const 
{
	if(ptr==NULL) return ;
	cout << ptr->data <<" ";
	PrintTree1(ptr->leftc) ;	
	PrintTree1(ptr->rightc);
}

void BST::PrintTree2(BstNode *&ptr) const 
{
	if(ptr==NULL) return ;
	PrintTree2(ptr->leftc) ;	
	PrintTree2(ptr->rightc);
	cout << ptr->data <<" ";
}

//查找指定的元素，找不到返回 NULL
BstNode * BST::Find(const int x,BstNode *ptr)const
{
	if(ptr==NULL)return NULL;	 
	else if(x < ptr->data)
	{
		return Find(x,ptr->leftc);
	}
	else if(x > ptr->data)
	{
		return Find(x,ptr->rightc);	
	}
	else return ptr;
	 
}


//求最小的元素，返回其地址指针 
BstNode * BST::Min(BstNode * ptr)const
{
    if(ptr==NULL)return NULL;
	else 
	{
		if(ptr->leftc==NULL)
		   return ptr;
	    else return Min(ptr->leftc);
	}
}

BstNode * BST::Max(BstNode *ptr)const
{
	if(ptr==NULL)return NULL;
	else
	{
		if(ptr->rightc==NULL)
           return ptr;
         else return Max(ptr->rightc);
	}
}

//删除指定的元素
void BST::Remove(const int x,BstNode *&ptr)
{
	BstNode *temp=NULL;
	if(ptr!=NULL)
	{
		 if (x < ptr->data)
		 {
			 Remove(x,ptr->leftc);
		 }
		 else if(x > ptr->data)
		 {
			 Remove(x,ptr->rightc);
		 }
		 else if(ptr->leftc!=NULL&&ptr->rightc!=NULL)
		 {    
			 
			 temp=Min(temp->rightc);
			 ptr->data=temp->data;
			 Remove(x,temp);
		 }
		 else 
		 {   
			 temp=ptr;
			 if     (temp->leftc==NULL) ptr=ptr->rightc;
			 else if(ptr->rightc==NULL) ptr=ptr->leftc;
			 delete temp;
		 }
	}
}

//按层次输出二叉树
void BST::Output(BstNode *&ptr)const
{
	BstNode *queue[1000];
	memset (queue,0,sizeof(queue));
	int *b = new int [1000];
	int i=0,j=0,head = 0;
	if(ptr == NULL)
	{
		cout << "this is an empety tree!\n";
		exit(0);
	}
	BstNode *p = ptr;
	queue[i++]=p;
	while(head != i)
	{
		b[j++] = queue[head]->data;
		if(queue[head]->leftc!=NULL)
			queue[i++] = queue[head]->leftc;
		if(queue[head]->rightc!=NULL)
			queue[i++] = queue[head]->rightc;
		head ++;
	}
	for(i=0;i<j-1;i++)
		cout << b[i]<<" ";
	cout << b[i];
	cout <<endl;

}

//计算叶子的个数
int BST::leaf(BstNode *&ptr)
{
	if(ptr == NULL)return 0;
	else if(ptr->leftc==NULL&&ptr->rightc==NULL) return 1;
	else return leaf(ptr->leftc) + leaf(ptr->rightc);
}

//求二叉树的高度
int BST::hight(BstNode *&ptr)
{
	int hl,hr;
	if(ptr == NULL) return -1;
	hl = hight(ptr -> leftc);
	hr = hight(ptr -> rightc);
	return 1 + (hl > hr ? hl : hr);
}