bst.h

二岔搜索树 可完成基本操作 遍历 查找 删除 判断两树是否相等

#ifndef BST_H
#define BST_H

#include <assert.h>
#include <iostream>
#include <stdlib.h>
using namespace std;

int max(int a, int b)
{
	return ((a >= b) ? a : b);		
}

template<class Type> class BST;

// 二叉搜索树的节点类
template<class Type> class BSTNode {
	friend class BST<Type>;
public:
	BSTNode(Type d = 0, BSTNode<Type> *left = 0, BSTNode<Type> *right = 0) : data(d), leftChild(left), rightChild(right) { }
	Type getData() const { return data; }
private:
	BSTNode<Type> *leftChild;  // 指向左子女结点
	BSTNode<Type> *rightChild; // 指向右子女结点
	Type data;  // 数据
};

//////////////////////////////////////////////////////////////////////////////////////////

// 二叉搜索树的类BST
template<class Type> class BST {
public:
	BST() : root(0) { }  // 构造函数：创建一个空树
	BST(const BST<Type> &); // 复制构造函数
	BST& operator=(const BST<Type> &); // 重载运算符'='
	~BST(); // 析构函数
	
	bool isEmpty() const { return root == 0; }  // 判断二叉搜索树是否为空	
	bool operator==(const BST<Type> &t) const;  // 判断当前树（*this）与树t是否相等

	BSTNode<Type> *getRoot() const { return root; }  // 取根root的指针值
	BSTNode<Type> *parent(BSTNode<Type> *current) const;  // 返回双亲节点的地址
	BSTNode<Type> *leftChild(BSTNode<Type> *current) const; // 返回左子女的节点地址
	BSTNode<Type> *rightChild(BSTNode<Type> *current) const; // 返回右子女的节点地址
	bool find(const Type &item) const;  // 搜索元素

	void insert(const Type &item);  // 插入新元素
	
	void remove(const Type &x);  // 删除含x的节点

	Type min() const; // 求最小元素
	Type max() const; // 求最大元素

	void inOrder() const; // 中序遍历二叉搜索树

	int size() const;  // 计算二叉搜索树的节点个数
	int depth() const;  // 计算二叉搜索树的高度
private:
	BSTNode<Type> *root;  // 二叉搜索树的根指针	
	void destroy(BSTNode<Type> *current);  // 删除根为current的子树	
	// 从节点start开始，搜索current的双亲节点
	BSTNode<Type> *parent(BSTNode<Type> *start, BSTNode<Type> *current) const;  
	void insert(BSTNode<Type> * &start, const Type &item);  // 插入
	void remove(BSTNode<Type> * &start, const Type &item); // 删除

	BSTNode<Type>* find(const Type &item, BSTNode<Type> *ptr) const; // 搜索

	BSTNode<Type> *min(BSTNode<Type> *ptr) const;  // 求最小
	BSTNode<Type> *max(BSTNode<Type> *ptr) const;  // 求最大

	void inOrder(BSTNode<Type> *current) const; // 中序遍历以current为根的二叉搜索树
	
	int size(const BSTNode<Type> *current) const;   // 计算以current为根的二叉搜索树的节点个数
	int depth(const BSTNode<Type> *current) const;  // 计算以current为根的二叉搜索树的高度

	// 复制以current为根的树
	BSTNode<Type>* copy(BSTNode<Type> *current);

	bool equal(BSTNode<Type> *a, BSTNode<Type> *b) const;  // 判断树a和b是否相等
};

// 复制构造函数
template<class Type> 
BST<Type>::BST(const BST<Type> &right)
{
	root = copy(right.root);
}

// 复制以current为根的树
template<class Type> 
BSTNode<Type>* BST<Type>::copy(BSTNode<Type> *current)
{
	if (!current)  // 根为空，返回空指针
		return 0;

	BSTNode<Type> *temp = new BSTNode<Type>;
	temp->data = current->data;
	temp->leftChild = copy(current->leftChild);
	temp->rightChild = copy(current->rightChild);

	return temp;
}

// 重载运算符'='
template<class Type> 
BST<Type>& BST<Type>::operator=(const BST<Type> &right) 
{
	 // 避免自我赋值和对已经相等的树进行赋值
	if ((this == &right) || equal(root, right.root)) 
		return *this;
	
	destroy(root);  // 删除原来的树
	root = copy(right.root); // 赋值

	return *this;
}

// 析构函数
template<class Type>
BST<Type>::~BST() 
{
	if (root)
		destroy(root); 

	root = 0;
}  

// 私有函数：若指针current不为空，则删除根为current的子树
template<class Type> void BST<Type>::destroy(BSTNode<Type> *current)
{
	if (current) {
		destroy(current->leftChild);  // 删除current的左子树
		destroy(current->rightChild);  // 删除current的右子树
		delete current;  // 删除current			
	}	
}

// 返回current的双亲节点的地址
template<class Type> 
BSTNode<Type>* BST<Type>::parent(BSTNode<Type> *current) const 
{
	if (root == 0 || root == current)
		return 0;
	else
		return parent(root, current);
}

// 所有函数：从节点start开始，搜索节点current的双亲节点
// 若找到，则函数返回双亲节点的地址，否则返回0
template<class Type>
BSTNode<Type>* BST<Type>::parent(BSTNode<Type> *start, BSTNode<Type> *current) const
{
	if (start == 0)
		return 0;
	if (start->leftChild == current || start->rightChild == current) // 找到
		return start;  

	BSTNode<Type> *temp;

	if (temp = parent(start->leftChild, current))  // 在左子树中搜索
		return temp;
	else
		return parent(start->rightChild, current);  // 在右子树中搜索
}

// 返回节点current的左子女节点地址
template<class Type>
BSTNode<Type>* BST<Type>::leftChild(BSTNode<Type> *current) const
{
	if (!root)
		return 0;
	return current->leftChild; 
} 

// 返回节点current的右子女节点地址
template<class Type>
BSTNode<Type>* BST<Type>::rightChild(BSTNode<Type> *current) const
{
	if (!root)
		return 0;
	return current->rightChild;
} 


// 在二叉搜索树中插入值为item的新节点
template<class Type>
void BST<Type>::insert(const Type &item)
{
	insert(root, item);
}

// 私有函数：在以根start的二叉搜索树中插入所含值为item的节点
// 若树中已经有含x的节点，则不插入
template<class Type> 
void BST<Type>::insert(BSTNode<Type> * &start, const Type &item)
{
	if (!start) {  // 新节点作为叶节点插入
		start = new BSTNode<Type>(item);  // 创建新节点
		assert(start);
	}
	else if ( item < start->data) // 小于根的关键码，向左子树插入
		insert(start->leftChild, item);   
	else if (item > start->data)
		insert(start->rightChild, item);  // 大于根的关键码，向右子树插入
}

// 删除含x的节点
template<class Type> 
void BST<Type>::remove(const Type &x)
{
	remove(root, x); 
} 

// 私有函数：在以ptr为根的二叉搜索树中。若删除成功，新根通过ptr返回
template<class Type> 
void BST<Type>::remove(BSTNode<Type> *&ptr, const Type &x)
{
	BSTNode<Type> *temp;
	if (ptr) {
		if (x < ptr->data)
			remove(ptr->leftChild, x);  // 在左子树中删除
		else if (x > ptr->data)
			remove(ptr->rightChild, x);  // 在右子树中删除
		else if(ptr->leftChild && ptr->rightChild) {  // ptr指示关键码为x的节点，它有两个子女
			temp = min(ptr->rightChild); // 在ptr的右子树中搜寻最小节点
			ptr->data = temp->data;  // 用该节点数据代替根节点数据
			remove(ptr->rightChild, ptr->data);  // 在右子树中删除该节点
		}
		else { // ptr指示关键码为x的节点，它只有一个或零个子女
			temp = ptr;
			if (!ptr->leftChild)
				ptr = ptr->rightChild;  // 只有右子女
			else if (!ptr->rightChild)
				ptr = ptr->leftChild;  // 只有左子女
			delete temp;
		}
	}	
} 

// 求最小元素
template<class Type> Type BST<Type>::min() const {
	return min(root)->getData(); 
}

// 寻找以ptr为根的二叉搜索树的最小值的地址
template<class Type> 
BSTNode<Type>* BST<Type>::min(BSTNode<Type> *ptr) const 
{
	if (!ptr)
		return 0;

	BSTNode<Type> *temp = ptr;
	
	while (temp->leftChild) 
		temp = temp->leftChild;

	return temp;	
}

// 求最大元素
template<class Type> Type BST<Type>::max() const {
	return max(root)->getData(); 
}

// 寻找以ptr为根的二叉搜索树的最大值的地址
template<class Type> 
BSTNode<Type>* BST<Type>::max(BSTNode<Type> *ptr) const 
{
	if (!ptr)
		return 0;

	BSTNode<Type> *temp = ptr;
	
	while (temp->rightChild) 
		temp = temp->rightChild;

	return temp;	
}

// 搜索元素item
template<class Type>
bool BST<Type>::find(const Type &item) const
{
	return (find(item, root) != 0);
}

// 私有函数：在以ptr为根的二叉搜索数中搜索含item的节点
template<class Type>
BSTNode<Type>* BST<Type>::find(const Type &item, BSTNode<Type> *ptr) const
{

	if (ptr) { // 树不空

		
		// 递归算法
		if (item < ptr->data)
		return find(item, ptr->leftChild); // 到左子树中搜索
		else if (item > ptr->data)
		return find(item, ptr->rightChild);  // 到右子树中搜索
		else
		return ptr; // 搜索成功	
		

		/*

		// 迭代算法	

		BSTNode<Type> *temp = ptr;  // 从根开始搜索

		while (temp) {
			if (temp->data == item)  // 搜索成功
				return temp;  
			else if (temp->data < item)
				temp = temp->rightChild; // 否则，继续搜索右子树
			else
				temp = temp->leftChild;  // 否则，继续搜索左子树
		}
		*/
	}
	
	return 0;	
}

// 中序遍历二叉搜索树
template<class Type>
void BST<Type>::inOrder() const
{
	inOrder(root);
}

// 私有函数：中序遍历以current为根的二叉搜索树
template<class Type>
void BST<Type>::inOrder(BSTNode<Type> *current) const
{
	if(current) {
		inOrder(current->leftChild);  // 中序遍历左子树
		cout << current->data << ' '; // 访问根节点，用输出语句暂代
		inOrder(current->rightChild); // 中序遍历右子树
	}
}

// 计算二叉搜索树的节点个数
template<class Type>
int BST<Type>::size() const
{
	return size(root);
}

// 私有函数：计算以current为根的二叉搜索树的节点个数
template<class Type>
int BST<Type>::size(const BSTNode<Type> *current) const
{
	if (!current)  // 递归结束条件
		return 0;
	else
		return 1 + size(current->leftChild) + size(current->rightChild);
}

// 计算二叉搜索树的高度
template<class Type>
int BST<Type>::depth() const
{
	return depth(root);
}

// 私有函数：计算以current为根的二叉搜索树的节点个数
template<class Type>
int BST<Type>::depth(const BSTNode<Type> *current) const
{
	if (!current)  // 递归结束条件
		return -1;
	else
		return 1 + ::max(depth(current->leftChild), depth(current->rightChild));
}

// 判断当前树（*this）与树t是否相等
template<class Type>
bool BST<Type>::operator==(const BST<Type> &t) const
{
	return equal(root, t.root);
}

// 私有函数：判断树a和b是否相等
template<class Type>
bool BST<Type>::equal(BSTNode<Type> *a, BSTNode<Type> *b) const
{
	if (!a && !b)
		return true;
	if (a && b && (a->data == b->data) && 
		equal(a->leftChild, b->leftChild) && 
		equal(a->rightChild, b->rightChild))
		return true;
	else
		return false;
}

#endif // BST_H