head.h

定义一个二叉树的类

#include <iostream>
#include <strstream>
#include <iomanip>
#include <stack>

using namespace std;


//定义二叉树节点类型
template<class T>class BinaryTree;
template<class T>struct BTreeNode
{
	 private:
		 BTreeNode<T>*left;   //左子树指针
		 BTreeNode<T>*right;  //右子树指针
	 public:
		 T data;  //数据域
		 //构造函数
		 BTreeNode():left(NULL),right(NULL){}
		 BTreeNode(T item,BTreeNode<T>*left1=NULL,BTreeNode<T>*right1=NULL):data(item),left(left1),right(right1){}
		 BTreeNode<T>*&Left(){return left;}
		 BTreeNode<T>*&Right(){return right;}
		 friend class BinaryTree<T>;//二叉树类为二叉树结点类的友元类
};
//二叉树类定义
template<class T>class BinaryTree
{
	private:
		BTreeNode<T>* root;
	public:
		//构造函数,初始化二叉树为空
		BinaryTree(){root=NULL;}
		//根据字符数组a的二叉树广义表建立对应的二叉树存储结构
		void CreateBTree(char* a);
		//判断二叉树是否为空
		bool BTreeEmpty() {return root==NULL;}
		//按中序遍历输出二叉树中的所有结点
		void TraverseBTree();
		//用于遍历的递归函数
		void Traverse(BTreeNode<T>*&BT);
		//用于中序遍历的非递归函数
		//void InOrder(BTreeNode<T>*&p);
		void InOrder();


};

//根据字符数组a的二叉树广义表建立对应的二叉树存储结构
template<class T>
void BinaryTree<T>::CreateBTree(char *a)
{
	BTreeNode<T> *s[80];  //S数组作为存储二叉树中根结点指针的栈
	int top=-1;          //top作为s栈的栈顶指针
	root=NULL;           //给树根指针置空
	BTreeNode<T> *p=NULL;//定义P为指向二叉树结点的指针
//用K作为处理结点的左子树和右子树的标记,K=1处理左子树,K=2处理右子树
	int k;
	istrstream ins(a);//把字符串a定义为输入字符串流对象ins
	char ch;
	ins>>ch;//从ins流对象顺序读入一个字符
	while (ch!='@')
	{    //每循环一次处理一个读入的字符,直到扫描到'@'字符为止
		switch(ch)
		{
		case'(':top++; s[top]=p;k=1;break;
		case')':top--;break;
		//case',':top++;k=2;break;
		case ',':k=2;break;
	    default:p=new BTreeNode<T>;
		//default:p=new  BTreeNode<char> (ch);
			p->data=ch;
			p->left=p->right=NULL;
			cout<<setw(2)<<p->data;
			if (root==NULL) root=p;
			else
			{
				if(k==1) 
					s[top]->left=p;
				else 
					s[top]->right=p;
			}
		}
		ins>>ch;
	}

}

//按中序遍历输出二叉树中的所有结点
template<class T>
void BinaryTree<T>::TraverseBTree()
{
	Traverse(root);
}
//用于中序遍历的递归函数

template<class T>
void BinaryTree<T>::Traverse(BTreeNode<T> *&BT)
{
if (BT!=NULL)
{
	//cout<<BT->data<<' ';
	Traverse(BT->left);
	cout<<BT->data<<" ";
	Traverse(BT->right);
}
};

//中序遍历的非递归函数
template<class T>
//void BinaryTree<T>::InOrder(BTreeNode<T> *&p)
void BinaryTree<T>::InOrder()
{
	stack<BTreeNode<T>*> s;
	BTreeNode<T> *p=root;
	do{
		while (p!=NULL){
		s.push(p);
		p=p->left;
		}
		if(!s.empty()){
		p=s.top();
		cout<<p->data<<" ";
		s.pop();
		p=p->right;
		}
	}while(p!=NULL||!s.empty());
}