binarytree.template

二叉树的数据结构的代码

//****************************************************************************
//访问函数                                                                   *
//作用：其指针作为其他成员函数的参数，将访问的数据分别标准输出和文件输出     *
//****************************************************************************
template <class T>
void BinaryTree<T>::Visit(BinaryTreeNode<T> *node,Inorder select)//在类外定义成员函数时static不能再加上，否则出错
{
	ofstream outfile;
	if(select==RECURSIVEINORDER)
			outfile.open("recursiveInorder.dat",ios::app);
	//输入输出方式app:以输出方式打开文件，文件指针指向文件末尾，这在递归调用时尤为重要，使得在每次递归写入的数据不会丢失
	else
		outfile.open("nonrecursiveInorder.dat",ios::app);
		if(!outfile)
		{
			cerr<<"open error!"<<endl;
			exit(1);
		}
		outfile<<node->data<<" ";
		cout<<node->data<<" ";
		outfile.close();
}
//***************************************************************************************
//建树函数                                                                              *
//作用：根据私有数据成员str_pre构造二叉树，只在构造函数BinaryTree(char *s)中调用了此函数*
//***************************************************************************************
template <class T>
inline BinaryTreeNode<T> *BinaryTree<T>::MakeTree() 
{ 
	BinaryTreeNode<T> *r;
	char element;
            
	element=str_pre[counter++];
		
    if(element=='#')
	{ 
		r=NULL; 
    }
	else
	{ 
		r=new BinaryTreeNode<T>;
        r->data=element; 
        r->leftchild=MakeTree(); 
        r->rightchild=MakeTree(); 
	} 
	return r;                   
}
//****************************************************************************************
//毁树函数                                                                               *
//作用：销毁以参数作为根结点的二叉树，本程序只在析构函数BinaryTree(char *s)中调用了此函数*
//****************************************************************************************
template <class T>
inline void BinaryTree<T>::destroy(BinaryTreeNode<T> *current) 
{ 
	if(current!=NULL)
	{ 
		destroy(current->leftchild); 
		destroy(current->rightchild); 
		delete current; 
	} 
} 
//***************************************************************************************
//中序递归遍历二叉树函数                                                                *
//作用：使用递归法中序遍历二叉树                                                        *
//***************************************************************************************
template <class T>
void BinaryTree<T>::recursiveInorder()
{
	ofstream outfile;
	outfile.open("recursiveInorder.dat",ios::trunc);
	//输入输出方式trunc:打开一个文件，如果文件存在，则删除其中全部数据，如果文件不存在，则建立新文件
	//如果指定了ios::out方式，而未指定ios::app,iso::ate,iso::in，则同时默认此方式
	//由于在Visit函数中的输入输出方式是iso::app，不会在执行recursiveInorder()函数时将文件清空，所以这里要显示清空文件内容
	outfile.close();
	recursiveInorder(Visit,root);
}
//***************************************************************************************
//中序非递归遍历二叉树函数                                                              *
//作用：利用栈实现中序遍历二叉树的非递归算法                                            *
//***************************************************************************************
template <class T>
void BinaryTree<T>::nonrecursiveInorder()
{
	ofstream outfile;
	outfile.open("nonrecursiveInorder.dat",ios::trunc);
	outfile.close();
	nonrecursiveInorder(Visit,root);
}
//***************************************************************************************
//搜索函数                                                                              *
//作用：搜索序列中是否存在指定字符，存在返回字符下标，不存在返回-1                      *
//***************************************************************************************
template <class T>
int BinaryTree<T>::searchchar(char c,char *order)
{
	for(int i=0;i!=strlen(order);i++)
	{
		if(c==order[i])
			return i;
	}
	return -1;
}
//***************************************************************************************
//中序递归遍历二叉树函数                                                                *
//作用：使用递归法中序遍历二叉树                                                        *
//***************************************************************************************
template <class T>
inline void BinaryTree<T>::recursiveInorder(void(*Visit)(BinaryTreeNode<T> *node,Inorder select),BinaryTreeNode<T> *t)
{
	if(t)
	{
		recursiveInorder(Visit,t->leftchild);
        Visit(t,RECURSIVEINORDER);
        recursiveInorder(Visit,t->rightchild);
	}
}
//***************************************************************************************
//中序非递归遍历二叉树函数                                                              *
//作用：利用栈实现中序遍历二叉树的非递归算法                                            *
//***************************************************************************************
template <class T>
void BinaryTree<T>::nonrecursiveInorder(void(*Visit)(BinaryTreeNode<T> *node,Inorder select),BinaryTreeNode<T> *t)
{
	stack<BinaryTreeNode<T> *> tempstack;
	BinaryTreeNode<T> *pointer=t;
	while(!tempstack.empty()||pointer)
	{
		if(pointer)
		{
			tempstack.push(pointer);
		    pointer=pointer->leftchild;
		}
		else
		{
			pointer=tempstack.top();
			Visit(pointer,NONRECURSIVEINORDER);
			pointer=pointer->rightchild;
            tempstack.pop();
		}
	}
}
//*****************************************************************************************************
//造树函数                                                                                            *
//作用：根据前序序列和后续序列构造二叉树，本程序只在构造函数BinaryTree(char *p, char *s)中调用了此函数*
//*****************************************************************************************************
template <class T>
inline  BinaryTreeNode<T>* BinaryTree<T>::CreateTree(char *pre,char *in)
{
	char c=pre[0];
    char *temppre=new char[MAX_BINARYTREE_SIZE];
    char *tempin=new char[MAX_BINARYTREE_SIZE];
    char *p;
    int i=0; 
    BinaryTreeNode<T>* bnode=NULL;

    if(pre=='\0')
		return NULL;
	/*内存初始化函数memset()用法详解
	作用：在一段内存中填充某个给定的值，注意填充时是按照字节顺序填充的，而不是按照元素填充。
	此方法是对较大的结构体和数组进行清零操作的一种有效方法。
	函数形式：memset(void *buffer,int c,size_t n)
	在头文件cstring或string.h或memory.h中
	buffer是需要设置的内存的开始地址；c是期望填充值；n是需要填充的字节数。*/
	memset(temppre,0,MAX_BINARYTREE_SIZE);
	memset(tempin,0,MAX_BINARYTREE_SIZE);

	bnode=new BinaryTreeNode<T>(c);
	i=searchchar(pre[0],in);
	if(i==-1)
		return 0;
    p=in;
	strncpy(tempin,p,i);//如果找到，则将中序序列的前i个元素复制给tempin,此时tempin存放的是根结点左子树的节点元素的中序序列
	p=pre;
	strncpy(temppre,p+1,i);//将前序序列第二个元素后的前i个元素复制给temppre,此时temppre存放的根节点左子树结点元素的前序序列
	bnode->leftchild=CreateTree(temppre,tempin);//递归调用CreateTree函数构造当前结点的左子树

    memset(tempin,0,MAX_BINARYTREE_SIZE);//将tempin和temppre中的元素重新置为0
    memset(temppre,0,MAX_BINARYTREE_SIZE);

    p=in+i+1;//p指向前序序列第i+1个元素，此时，p是根结点右子树的基地址
	strncpy(tempin,p,strlen(in)-i);//将根结点的右子树的中序序列复制给tempin
	p=pre+i+1;//p指向前序序列第i+1个元素，此时，p是根结点右子树的基地址
	strncpy(temppre,p,strlen(in)-i);//将根结点的右子树的前序序列复制给tempin
	bnode->rightchild=CreateTree(temppre,tempin);//递归调用CreateTree函数构造当前结点的右子树
	delete [] temppre;
	delete [] tempin;
	return bnode;
}
//************************************************************************************************************
//测试算法结果函数                                                                                           *
//作用：测试两个遍历算法recursiveInorder和nonrecursiveInorder结果是否相同。如果相同，返回true, 否则返回false *
//************************************************************************************************************
template <class T>
bool BinaryTree<T>::testTraverse()
{
	char ch1=' ',ch2=' ';
	int flag=0;
	ifstream infile_recursiveInorder("recursiveInorder.dat");
	ifstream infile_nonrecursiveInorder("nonrecursiveInorder.dat");
	if(!infile_recursiveInorder)
	{
		cerr<<"open \"recursiveInorder.dat\" error!"<<endl;
		exit(1);
	}
	if(!infile_nonrecursiveInorder)
	{
		cerr<<"open \"nonrecursiveInorder.dat\" error!"<<endl;
		exit(1);
	}
	while(infile_recursiveInorder.get(ch1)&&infile_nonrecursiveInorder.get(ch2))
	{
		if(ch1!=ch2)
			flag++;
	}
	infile_recursiveInorder.close();
	infile_nonrecursiveInorder.close();
	if(flag==0)
		return true;
    else
		return false;
}