binarytree.cpp

以二叉链表作为存储结构

#include"BinaryTree.h"
#include<iostream.h>
template<class T>
bool BinaryTree<T>::Root(T&x)const
{
	//x为返回的根信息
	//如果为空二叉树，则返回FALSE
	if(root)
	{
		x=root->data;
		return TRUE;
	}
	else return FALSE;
}

template<class T>
BinaryTreeNode<T> *BinaryTree<T>::MakeTree(const T&data,
		  BinaryTreeNode<T> *left,BinaryTreeNode<T> *right)
{
	//结合指针left、right和结点信息element产生的树
	//左、右子树为不同的树
	//构建组合后的树
	root=new BinaryTreeNode<T>(data,left,right);
	if(root==NULL)
	{
		cout<<"Merory allocation failure!"<<endl;
		exit(1);
	}
	return root;
}

template<class T>
void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *t)
{
	//前序遍历
	if(t)
	{
		cout<<t->data;
		PreOrder(t->LeftChild);
		PreOrder(t->RightChild);
	}
}

template<class T>
void BinaryTree<T>::InOrder(BinaryTreeNode<T> *t)
{
	//对称序遍历
	if(t)
	{
		InOrder(t->LeftChild);
		cout<<t->data;
		InOrder(t->RightChild);
	}
}

template<class T>
void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *t)
{
	//后序遍历
	if(t)
	{
		PostOrder(t->LeftChild);
		PostOrder(t->RightChild);
		cout<<t->data;
	}
}

template<class T>
void BinaryTree<T>::create(int *Tree,int size)
{
	BinaryTreeNode<int> *tnode;
	BinaryTreeNode<int> *rnode;
	int count=0;
	for(int i=0;i<size;i++)
	{
		if(root==NULL)                   //如果根结点不存在，即树为空
		{
			{
			cout<<"Merory allocation failure!"<<endl;
			exit(1);
			}
		root->data=Tree[i];              //将数组的第一个元素置为根结点
		root->LeftChild=NULL;
		root->RightChild=NULL;
		count++;
		}
        else
		{
			tnode=root;
			count++;
		}
		do
		{
			if(Tree[i]<tnode->data)
			{
				if(tnode->LeftChild=NULL)
				{
					rnode->data=Tree[i];
					rnode->LeftChild=NULL;
					rnode->RightChild=NULL;
					tnode->LeftChild=rnode;
				}
				else
					tnode=tnode->LeftChild;
			}
			else
			{
				if(tnode->RightChild=NULL)
				{
					rnode->data=Tree[i];
					rnode->LeftChild=NULL;
					rnode->RightChild=NULL;
					tnode->RightChild=rnode;
				}
				else
					tnode=tnode->RightChild;
			}
		}while(1);
	}
}

template<class T>
void BinaryTree<T>::NLR(BinaryTreeNode<T>*t)
{
	//t指向二叉数根结点
	BinaryTreeNode<T>*stack[100];
	//假定进栈的结点个数不超过100
	unsigned top;
	cout<<"中序遍历的结果为："<<endl;
	top=0;stack[0]=t;
	do
	{
		while(stack[top]!=NULL)
		{
			cout<<stack[top]->data;
			stack[++top]=stack[top]->LeftChild;
		}
		if(top>0)stack[top]=stack[--top]->RightChild;
	}while(top>0||stack[top]!=NULL);
}