genbst.h

通用二叉搜索树

//******************************  genBST.h  ******************************
//               definition of class BST: generic binary search tree
//                             通用二叉搜索树
#ifndef GENBST_H
#define GENBST_H

#include <queue>
#include <string>
#include "BSTNode.h"

using namespace std;

template<class T>
class BST 
{
public:
    BST() { root = 0; }
	~BST();
	BST( BSTNode* p ) { root = p; }
	void insertNode( const T& el );								                   // 插入节点
	void displayTree() const { displayTreeHelper( root, 0 ); }					   // 打印树
	void breadthFirst() const;							                           // 广度优先遍历
	void preOrderTraversal() const{ preOrderHelper(root); }                        // VLR——前序树遍历
	void inOrderTraversal() const{ inOrderHelper(root); }                          // LVR——中序树遍历
	void postOrderTraversal() const{ postOrderHelper(root); }                      // LRV——后序树遍历
	int nodesCount() const{ return nodesCountHelper(root); }                       // 节点数
	int leafCount() const{ return leafCountHelper(root); }                         // 叶子节点数
	int rightChildCount() const { return rightChildCountHelper(root); }            // 右子节点数
	int height() const { return heightHelper(root); }                              // 树的高度
	void deleteLeaves() { deleteLeavesHelper(root); }                              // 删除所有叶子节点
	BSTNode<T>* search(const T& el);											   // 查找节点
	void deleteByMerging(BSTNode<T>* & node) { deleteByMergingHelper(node); }      // 合并删除
    bool findAndDeleteByMerging(const T& el){ return findAndDeleteByMergingHelper(el); }     // 查找并合并删除
	void preInCreateTree(string pre, string in){ preInCreateTreeHelper(pre, in, root); }     // 根据先序中序创建树
	void postInCreateTree(string post, string in){ postInCreateTreeHelper(post, in, root); } // 根据后序中序创建树
private:
	BSTNode<T>* root;	
	/*--------------------utility functions--------------------*/     //利用工具函数实现封装
	void displayTreeHelper( BSTNode<T>*, int ) const;
	void preOrderHelper( BSTNode<T>* ) const;
	void inOrderHelper( BSTNode<T>* ) const;
	void postOrderHelper( BSTNode<T>* ) const;
	int nodesCountHelper( BSTNode<T>* ) const;
	bool isLeafHelper( BSTNode<T>* ) const;
	int leafCountHelper( BSTNode<T>* ) const;
	int rightChildCountHelper( BSTNode<T>* ) const;
	int heightHelper( BSTNode<T>* ) const;
	void deleteLeavesHelper( BSTNode<T>*& );
	void deleteByMergingHelper(BSTNode<T> *& node);
	bool findAndDeleteByMergingHelper(const T& el);
	void preInCreateTreeHelper(string, string, BSTNode<T>*&);
	void postInCreateTreeHelper(string, string, BSTNode<T>*&);		
};
//-------------------------------------------------------------------------
template<class T>
BST<T>::~BST()
{
	while ( root != 0 )
	{
		deleteLeaves();
	}
}
//-------------------------------------------------------------------------
template<class T>                                               // 插入节点
void BST<T>::insertNode( const T& el ) 
{
	BSTNode<T> *cur = root, *prev = 0;
	while ( cur != 0 ) {       // find a place for inserting new node;
		prev = cur;
		if( cur->data < el )
			cur= cur->rc;
		else if( cur->data > el )
			cur = cur->lc;
		else{
			cout << "Data " << el 
				 << " has been found in the tree,and it won't be inserted to the tree!\n";
			return;
		}
	}
	if( root == 0 )
		root = new BSTNode<T>(el);
	else if( prev->data < el )
		prev->rc = new BSTNode<T>(el);
	else
		prev->lc = new BSTNode<T>(el);
}
//-------------------------------------------------------------------------
template<class T>                                           // 广度优先遍历
void BST<T>::breadthFirst() const 
{
	queue< BSTNode<T>* > Q;
	BSTNode<T>* p = root;
	if( p != 0 ) {
		Q.push( p );
		while ( !Q.empty() ) {
			p = Q.front();
			Q.pop();
			cout << p->data << ' ';
			if ( p->lc != 0 )
				Q.push( p->lc );
			if ( p->rc != 0 )
				Q.push( p->rc );
		}
	}
}
//******************** definition of utility functions ****************************
//-------------------------------------------------------------------------
template<class T>                                                 // 打印树
void BST<T>::displayTreeHelper( BSTNode<T>* p, int totalSpaces ) const 
{
	while ( p )
	{
		displayTreeHelper( p->rc, totalSpaces+5 );
		for ( int i = 0; i <= totalSpaces; i++ )
			cout << ends;
		cout << p ->data << endl;
		p = p->lc;
		totalSpaces += 5;
	}
}
//-------------------------------------------------------------------------
template<class T>                                      // VLR——前序树遍历
void BST<T>::preOrderHelper( BSTNode<T>* p ) const
{
	if ( p ) {
		cout << p->data << ' ';
		preOrderHelper( p->lc );
		preOrderHelper( p->rc );
	}
}
//-------------------------------------------------------------------------
template<class T>                                      // LVR——中序树遍历
void BST<T>::inOrderHelper( BSTNode<T>* p ) const 
{
	if( p ) {
		inOrderHelper( p->lc );
		cout << p->data << ' ';
		inOrderHelper( p->rc );
	}
}
//-------------------------------------------------------------------------
template<class T>                                      // LRV——后序树遍历
void BST<T>::postOrderHelper( BSTNode<T>* p ) const 
{
	if( p ) {
		postOrderHelper( p->lc );
		postOrderHelper( p->rc );
		cout << p->data << ' ';	
	}
}
//-------------------------------------------------------------------------
template<class T>                                                 // 节点数
int BST<T>::nodesCountHelper( BSTNode<T>* p ) const 
{
	if( !p )
		return 0;
	else {
		int lcount = nodesCountHelper( p->lc );
		int rcount = nodesCountHelper( p->rc );
		return lcount + rcount + 1;
	}
}
//-------------------------------------------------------------------------
template<class T>                                // 判断某节点是否为叶子节点
bool BST<T>::isLeafHelper( BSTNode<T>* p ) const
{
	if( !p ) {
		cout << "Wrong: isLeafHelper() requires non-null pointer!\n";
		exit(1);
	}
	else
		if( p->lc == 0 && p->rc == 0 )
			return true;
		else
			return false;
}	
//-------------------------------------------------------------------------
template<class T>                                             // 叶子节点数
int BST<T>::leafCountHelper( BSTNode<T>* p ) const 
{
	if( !p )
		return 0;
	else {
		if( isLeafHelper( p ) )
			return 1;
		else {
			int lcount = leafCountHelper( p->lc );
			int rcount = leafCountHelper( p->rc );
			return lcount + rcount;
		}
	}		
}
//-------------------------------------------------------------------------
template<class T>                                             // 右子节点数
int BST<T>::rightChildCountHelper( BSTNode<T>* p ) const 
{
	if( !p )
		return 0;
    else    
    {
		int rcount = rightChildCountHelper( p->rc );
		if( p == root )
			return rcount;
		else
			return rcount + 1;
	}
}
//-------------------------------------------------------------------------
template<class T>                                               // 树的高度
int BST<T>::heightHelper( BSTNode<T> *p ) const {
	if( !p )
		return 0;
	else {
		int lheight = heightHelper( p->lc );
		int rheight = heightHelper( p->rc );
		if( lheight > rheight )
			return ++lheight;
		else
			return ++rheight;
	}	
}
//-------------------------------------------------------------------------
template<class T>                                       // 删除所有叶子节点
void BST<T>::deleteLeavesHelper( BSTNode<T>*& p )
{
	BSTNode<T>* tmp = p;
	if( !p )
		return;
	else if( isLeafHelper(p) ) {
		p = NULL;
		delete tmp;
	}
	else {
		if ( p->lc )
			deleteLeavesHelper( p->lc );
		if ( p->rc )
			deleteLeavesHelper( p->rc );
	}
}
//-------------------------------------------------------------------------
template<class T>                                               // 查找节点
BSTNode<T>* BST<T>::search( const T& el )
{
	BSTNode<T>* p = root;
	while ( p ){
		if( el == p->data )
			return p;
		else if( el < p->data )
			p = p->lc;
		else 
			p = p->rc;
	}
	return 0;
}
//-------------------------------------------------------------------------
template<class T>                                               // 合并删除
void BST<T>::deleteByMergingHelper( BSTNode<T>*& node ) 
{
	BSTNode<T>* tmp = node;
	if( node ) 
	{
		if( !node->rc )				// 右子树为空
			node = node->lc;
		else if( !node->lc )		// 左子树为空
			node = node->rc;
		else {
			tmp = node->lc;         // 1. move left
			while( tmp->rc )        // 2. and then right as far as possible
				tmp = tmp->rc;
			tmp->rc = node->rc;
			tmp = node;
			node = node->lc;
		}
		delete tmp;
	}
}
//-------------------------------------------------------------------------
// 要想访问以被删除节点为根的整个子树，必须从被删除节点的父节点的左或者右指
// 针数据成员中访问该节点，这样才能修改其父节点的左或右指针
template<class T>                                          //查找并合并删除
bool BST<T>::findAndDeleteByMergingHelper( const T& el ) 
{
	BSTNode<T> *p = root, *prev = 0;
	while ( p ) {
		if( el == p->data )
			break;
		prev = p;
		if(el < p->data)
			p = p->lc;
		else 
			p = p->rc;
	}
	if( p && p->data == el )
	{
		if( p == root )
			deleteByMerging( root );
		else if ( p == prev->lc )
			deleteByMerging( prev->lc );
		else
			deleteByMerging( prev->rc );
		return true;
	}
	else if( root )
		cout << "Data " << el << " is not in the tree\n";
	else
		cout << "The tree is empty\n";
	return false;
}
//-------------------------------------------------------------------------
// 使用C++标准库中的string类
// string类提供的substr函数可以读取string的子串。参数1：开始下标；参数2：子串字符数
template<class T>                                      // 根据先序中序创建树
void BST<T>::preInCreateTreeHelper(string pre, string in, BSTNode<T>*& r) 
{
	if( pre.size() == 0 )
		r = NULL;
	else {
		for( int split = 0; split < pre.size(); split++ )
			if ( in[split] == pre[0] )
				break;
		r = new BSTNode<T>( pre[0] );
		preInCreateTreeHelper( pre.substr(1, split), in.substr(0, split), r->lc );
		preInCreateTreeHelper( pre.substr(split+1, pre.size()-split-1), in.substr(split+1, in.size()-split-1), r->rc );	
	}
}
//-------------------------------------------------------------------------
// 使用C++标准库中的string类
// string类提供的substr函数可以读取string的子串。参数1：开始下标；参数2：子串字符数
template<class T>                                      // 根据后序中序创建树
void BST<T>::postInCreateTreeHelper(string post, string in, BSTNode<T>*& r)
{
	if( post.size() == 0 )
		r = NULL;
	else {
		for(int split = 0; split < post.size(); split++ )
			if ( in[split] == post[post.size()-1] )
				break;
		r = new BSTNode<T>( post[post.size()-1] );
		postInCreateTreeHelper( post.substr(0, split), in.substr(0, split), r->lc );
		postInCreateTreeHelper( post.substr(split, post.size()-split-1), in.substr(split+1, in.size()-split-1), r->rc );	
	}
}
//-------------------------------------------------------------------------
#endif