binarytree.h

二叉树的数据结构的代码

using namespace std;

const int MAX_BINARYTREE_SIZE=100;
enum Inorder{RECURSIVEINORDER,NONRECURSIVEINORDER};//recursive inorder中序递归遍历,nonrecursive inorder中序非递归遍历

template <class T>
class BinaryTree;


template <class T>
class BinaryTreeNode
{
	friend class BinaryTree<T>;
	private:
		T data;
        BinaryTreeNode<T> *leftchild;
        BinaryTreeNode<T> *rightchild;
	public:
        BinaryTreeNode(const T& element=0,BinaryTreeNode<T> *l=NULL,BinaryTreeNode<T> *r=NULL):
		  data(element),leftchild(l),rightchild(r){}
};



template <class T>
class BinaryTree
{
	private:
		//私有数据成员：
		char *str_pre;//前序序列字符串
		int counter;//指示字符在字符串中的位置
		BinaryTreeNode<T> *root;

		//私有成员函数：
		//下面两个成员函数的参数包含了函数指针类型参数，这就需要做参数的函数声明为static
		void recursiveInorder(void(*Visit)(BinaryTreeNode<T> *node,Inorder select),BinaryTreeNode<T> *t);
        void nonrecursiveInorder(void(*Visit)(BinaryTreeNode<T> *node,Inorder select),BinaryTreeNode<T> *t);
		int searchchar(char c,char *order);
		BinaryTreeNode<T>* CreateTree(char *pre,char *in);
		static void Visit(BinaryTreeNode<T> *node,Inorder select);
		/*指向一个非静态成员函数的指针，需要和对象的地址绑定在一起，才能得到该函数的绝对地址。这里若未声明为static，将得不到它
		绝对地址，这样将函数指针做函数参数，将编译不过*/
		BinaryTreeNode<T> *MakeTree();
		void destroy(BinaryTreeNode<T> *current);

	public:
		//构造函数：
		BinaryTree(){root=NULL;}
		BinaryTree(char *s)//给定二叉树的前序遍历序列，用一个特殊字符表示无子结点，由此序列构造一棵二叉树
		{
			str_pre=s;
			counter=0;
			root=MakeTree();
		}
		BinaryTree(char *p, char *s)//使用先序序列字符串和中序序列字符串构造一棵二叉树
		{
			root=CreateTree(p,s);
		}
		//析构函数：
		~BinaryTree(){destroy(root);}

        void recursiveInorder();
		void nonrecursiveInorder();
		bool testTraverse();
        
};
#include"BinaryTree.template"