btree.h

postfixComputer, Calculate the postfix expression, such as 45+,which means 4+5,and the result is 9.

//二叉树的抽象数据类型(二叉链表表示)

template<class T>

class BTree
{
private:

	BTreeNode<T> *root;	//二叉树根节点						

	BTreeNode<T> *GetParent(BTreeNode<T> *root,BTreeNode<T> *current);//从二叉树的根结点开始，查找当前结点的父结点

public:

	BTree(root=NULL);//构造函数

	~BTree(){DeleteBTree(root);};//析构函数

	bool isEmpty() const; //判定二叉树是否为空树

	BTreeNode<T> *Root(){return root;};	//返回二叉树根结点

	BTreeNode<T> *Parent(BTreeNode<T> *current);//返回当前结点的父结点

	BTreeNode<T> *LeftSibling(BTreeNode<T> *current);//返回当前结点的左兄弟结点

	BTreeNode<T> *RightSibling(BTreeNode<T> *current);//返回当前结点的右兄弟结点

	void CreateBTree(const T&elem,BTreeNode<T> *leftTree,BTreeNode<T> *rightTree);
		//以elem作为根结点、leftTree作为左子树、rightTree作为右子树，构造一棵新的二叉树

	void PreOrder(BTreeNode<T> *root);//前序周游二叉树或其子树

	void InOrder(BTreeNode<T> *root);//中序周游二叉树或其子树

	void PostOrder(BTreeNode<T> *root);//后序周游二叉树或其子树

	void LevelOrder(BTreeNode<T> *root);//按层次周游二叉树或其子树

	void DeleteBTree(BTreeNode<T> *root);//以后序周游方式删除二叉树或其子树

};


template<class T>

bool BTree<T>::isEmpty() const 

{//判定二叉树是否为空树

	return((root)?false:true);

}


template<class T>

BTreeNode<T> *BTree<T>::GetParent(BTreeNode<T> *root,BTreeNode<T> *current)

{//从二叉树的根结点开始，查找当前结点的父结点

	BTreeNode<T> *temp;

	if(root==NULL)//当前树为空树

		return NULL;

	if((root->leftchild()==current)||(root->rightchild()==current))//找到父结点

		return root;

	if((temp=GetParent(root->leftchild(),current)!=NULL)//递归寻找父结点

		return temp;

	else 

		return GetParent(root->rightchild(),current);

}


template<class T>

BTreeNode<T> *BTree<T>::LeftSibling(BTreeNode<T> *current)

{//返回当前结点的左兄弟结点

	if(current)

	{

		BTreeNode<T> *temp=Parent(current);//返回当前结点的父结点

		if((temp==NULL)||current==temp->leftchild()) //如果父结点为空，或者当前结点没有左兄弟

			return NULL;

		else

			return temp->leftchild();

	}

	return NULL;

}


template<class T>

BTreeNode<T> *BTree<T>::RightSibling(BTreeNode<T> *current)

{//返回当前结点的右兄弟结点

	if(current)

	{

		BTreeNode<T> *temp=Parent(current);//返回当前结点的父结点

		if((temp==NULL)||current==temp->rightchild()) //如果父结点为空，或者当前结点没有右兄弟

			return NULL;

		else

			return temp->rightchild();

	}

	return NULL;

}



template<class T>

void BTree<T>::CreateBTree(const T&elem,BTreeNode<T> *leftTree,BTreeNode<T> *rightTree)

{//以elem作为根结点、leftTree作为左子树、rightTree作为右子树，构造一棵新的二叉树

	root = new BTreeNode<T>(elem, leftTree.root, rightTree.root);//创建新树

	leftTree.root = rightTree.root = NULL;//原来两棵子树的根结点指空，避免访问

}



template<class T>

void BTree<T>::PreOrder(BTreeNode<T> *root)//前序周游二叉树或其子树

{

	if( root!=NULL)

	{

		Visit(root);

		PreOrder(root->leftchild);

		PreOrder(root->rightchild);

	}

}



template<class T>

void BTree<T>::InOrder(BTreeNode<T> *root)//中序周游二叉树或其子树

{

	if( root!=NULL)

	{

		InOrder(root->leftchild);

		Visit(root);

		InOrder(root->rightchild);

	}

}



template<class T>

void BTree<T>::PostOrder(BTreeNode<T> *root)//后序周游二叉树或其子树

{

	if( root!=NULL)

	{

		PostOrder(root->leftchild);

		PostOrder(root->rightchild);

		Visit(root);

	}

}



template<class T>

void BTree<T>::LevelOrder(BTreeNode<T> *root)//按层次周游二叉树或其子树

{

	using std::queue;

	queue<BTreeNode<T> *> aQueue;//使用STL的队列

	BTreeNode<T> *pointer = root;//保存输入参数

	if(pointer)

		aQueue.push(pointer);

	while(aQueue.empty())

	{
		pointer = aQueue.front();//取队列首结点

		Visit(pointer->value());//访问当前结点

		aQueue.pop();

		if(pointer->leftchild())

			aQueue.push(pointer->leftchild());//左子树进队列

		if(pointer->rightchild())

			aQueue.push(pointer->rightchild());//右子树进队列

	}

}


template<class T>

void BTree<T>::DeleteBTree(BTreeNode<T> *root)

{//以后序周游方式删除二叉树或其子树

	if (root)

	{

		DeleteBTree(root->left);//递归删除左子树

		DeleteBTree(root->right);//递归删除右子树

		delete root;//删除根结点
	}
}