殷书数据结构7.2——二叉搜索树

BST.h

//殷书7.2节 二叉搜索树

#include
using namespace std;

//二叉搜索树节点类 
template
struct BSTNode{
    T data;    //数据域
    BSTNode* left, * right;    //左子女、右子女
    BSTNode() :left(NULL), right(NULL) {}    //构造函数
    //构造函数
    BSTNode(const T d, BSTNode* L = NULL, BSTNode* R = NULL) :data(d), left(L), right(R) {}
};

//二叉搜索树的定
template 
class BST{
public:
    //普通构造函数
    BST() :root(NULL) {}
    //构造BST
    BST(T value) :root(NULL), RefValue(value)
    {
        T x;
        cin >> x;
        while (x != RefValue)
        {
            Insert(x, root);    //新建一个结点，调用Insert插入到树中
            cin >> x;
        }
    }
    //析构
    ~BST() { Destroy(root); }
    //插入
    bool Insert(T x) { return Insert(x, root); }
    //删除
    bool Remove(T x) { return Remove(x, root); }
    //搜索
    bool Search(T x) { return (Search(x, root) != NULL) ? true : false; }
    //中序遍历
    void InOrder() { InOrder(root);cout< Destroy(root); } 
	//求最大
	T Max(){ return Max(root);}
	//求最小
	T Min(){ return Min(root);}

protected:
    //二叉搜索树插入算法 
	bool Insert(const T&e1,BSTNode*& ptr){
		if(ptr==NULL){
			ptr=new BSTNode(e1);
			if(ptr==NULL) { cerr<<"Out of Space"<data) Insert(e1,ptr->left);
		else if(e1>ptr->data) Insert(e1,ptr->right);
		else return false;
	}
	
	//二叉搜索树的删除算法
	bool Remove(const T &x,BSTNode*& ptr){
		BSTNode *temp;
		if(ptr!=NULL){	
			if(xdata) Remove(x,ptr->left);
			else if(x>ptr->data) Remove(x,ptr->right);
			else if(ptr->left!=NULL&&ptr->right!=NULL){
				temp=ptr->right;
				while(temp->left!=NULL)  temp=temp->left;
				ptr->data=temp->data;
				Remove(ptr->data,ptr->right);	
			}
			else{
				temp=ptr;
				if(ptr->left==NULL) ptr=ptr->right;
				else ptr=ptr->right;
				delete temp;
				return true;
			}	
		}
		return false;
	}
	//二叉搜索树的搜索算法
	BSTNode* Search(const T x,BSTNode* ptr){
		if(ptr==NULL) return NULL;
		else if(xdata) return Serch(x,ptr->left);
		else if(x>ptr->data) return Search(x,ptr->right);
		else return ptr;
	}
	//中序遍历
	void InOrder(BSTNode* root){
		if(root!=NULL){
			InOrder(root->left);
			cout<data<<" ";
			InOrder(root->right);
		}
	}
	
	//销毁以root为根的二叉树搜索树
  	void Destroy(BSTNode* &root){
  		if(root==NULL) return;
  		if(root->left!=NULL)  Destroy(root->left);
  		if(root->right!=NULL)  Destroy(root->right);
  		delete root;
  		root=NULL;
	  }
	  
	//复制
	BSTNode* Copy(BSTNode* root){
		if(root==NULL) return NULL;
		BSTNode* node=new BSTNode(root->data);
		node->left=Copy(root->left);
		node->right=Copy(root->right);
		return node;
	} 
	
	//最大
	T Max(BSTNode* root){
		if(root==NULL) {
			cerr<<"Error:Tree is empty."<* temp=root;
		while(temp->right!=NULL){
			temp=temp->right;
		}
		return temp->data;
	}
	//最小 
	T Min(BSTNode* root){
		if(root==NULL) {
			cerr<<"Error:Tree is empty."<left==NULL) return root->data;
		return Min(root->left); 
	} 
	
	
private:
    BSTNode* root;    //根指针
    T RefValue;    //输入结束标识
};
 

mian.cpp

#include
#include"BST.h"
using namespace std; 


int main(){
	BST  bst;
	int a[7] = {10, 2, 7, 13, 11, 18, 15};
	for(int v:a){
		bst.Insert(v);
	}
	bst.InOrder();
	bst.Remove(2); 
	bst.InOrder();
	bst.Remove(12); 
	bst.InOrder();
	cout< bst1;
	bst1=bst;
	bst1.InOrder();
}