definetree.cpp

根据前序中序判断一棵树,从键盘上读取两列字符串,判断出这颗树的构造,然后遍历出

#include<iostream.h>
class treeNode
{
public:
	char data;
	treeNode *lNode,*rNode;
	treeNode():lNode(NULL),rNode(NULL){data=0;}
	treeNode(char &el,treeNode *l=NULL,treeNode *r=NULL)
	{
		data=el;lNode=l;rNode=r;
	}
};

class binary_tree
{
public:
	binary_tree(){root=NULL;}
	treeNode *getRoot(){return root;}
	void set(treeNode *p){root=p;}
	bool isEmpty(){return root==NULL?true:false;}
	void destroy(treeNode *p);
	treeNode *define_tree(char * Pre, char * Mid, int arraySize);
	void preorder(treeNode *p){
		if(p!=NULL)
		{	cout<<p->data;
			preorder(p->lNode);
			preorder(p->rNode);
		}
	}
	void inorder(treeNode *p)
	{
		if (p)
		{
			inorder(p->lNode);
			cout<<p->data;
			inorder(p->rNode);
		}
	}
	~binary_tree();
private:
	treeNode *root;
};
void binary_tree::destroy(treeNode *p)
{
	if(p->lNode!=NULL&&p->rNode!=NULL)
	{
		destroy(p->lNode);
		destroy(p->rNode);
		delete p;
	}
}
binary_tree::~binary_tree()
{
	destroy(root);
}
/////////////////////////////////////////////////////////////////////
treeNode *binary_tree::define_tree(char *Pre, char * Mid, int arraySize)
{
        
    if(arraySize==0)       
     return NULL;       
    if(arraySize==1)
	{
		treeNode *p=new treeNode(Pre[0]);
     return p;
	}
          
    for(int n=0;n<arraySize;++n)       
    {       
       if(Mid[n]==Pre[0])       
        break;       
    }       
     if(n==arraySize)       
     return NULL; 
	 treeNode *q=new treeNode(*Pre,define_tree(Pre+1, Mid,n),
		 define_tree(Pre+n+1,Mid+n+1,arraySize-n-1));       
	 root=q;
     return root; 
}
/////////////////////////////////////////////////////
void main()
{
	binary_tree a;
a.define_tree("abecdfghij","ebcdafhigj",10);
	
	a.preorder(a.getRoot());
	cout<<endl;
	a.inorder(a.getRoot());
	cout<<endl;
}