非递归遍历问题847trav.cpp

设计一个算法

#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<stdio.h>
class BinaryTree;            
class BinaryTreeNode;
	ofstream outfile("output.txt");
class BinaryTreeNode
{
public:
	BinaryTreeNode(){LeftChild=RightChild=0;}
	BinaryTreeNode(const int &e,BinaryTreeNode *l,BinaryTreeNode *r)
	{data=e;LeftChild=l;RightChild=r;}
	int getdata(){return data;}
    friend class BinaryTree;
private:
	int data;
	BinaryTreeNode *LeftChild,*RightChild;
};
class BinaryTree
{
public:
	BinaryTree(){root=0;}
	void BreakTree(int & element,BinaryTree& left, BinaryTree & right );
	int BinaryTreeHeight(BinaryTreeNode *t)const;
	void Preorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack);
	void Inorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack);
	void Postorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack);
	void MakeTree(const int &element,BinaryTree &left,BinaryTree &right);
	BinaryTreeNode *getroot(){return root;}
    friend class BinaryTreeNode;
private:
	BinaryTreeNode *root;
};	
void BinaryTree::BreakTree(int & element,BinaryTree & left, BinaryTree & right)
{
	if(! root) exit(1);
	element = root -> data;
	left.root = root -> LeftChild;
	right.root = root -> RightChild;
	delete root;
	root = 0;
}
void BinaryTree::Preorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack)
{		
    BinaryTreeNode *p;
	int top=0;
	p=t;
	do
	{
		while(p!=NULL)
		{
			outfile<<p->data<<" ";
			top++;
			Stack[top]=p;			
			p=p->LeftChild;
		}
		if(top>0)
		{
			p=Stack[top];
			top--;
			p=p->RightChild;
		}
	}while(p!=NULL||top!=0);     
}
void BinaryTree::Inorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack)
{		
	BinaryTreeNode	*p;
	int top=0;
	p=t;
	do
	{
		while(p!=NULL)
		{			
			top++;
			Stack[top]=p;	
			p=p->LeftChild;
		}
		if(top>0)
		{
			p=Stack[top];
			top--;
			outfile<<p->data<<" ";
			p=p->RightChild;
		}
	}while(p!=NULL||top!=0);     
}
void BinaryTree::Postorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack)
{		
	BinaryTreeNode *p,*q;
	int top=0,b;
	p=t;
	do
	{
		while(p!=NULL)
		{
			top++;
			Stack[top]=p;
			p=p->LeftChild;
		}
		b=1;
		q=NULL;
		while(top!=0&&b==1)
		{
			p=Stack[top];
			if(p->RightChild==q)
			{
				top--;
				outfile<<p->data<<" ";
				if(p==t) return;
				q=p;
			}
			else
			{
				p=p->RightChild;
				b=0;
			}
		}
	}while(p!=NULL||top!=0);    
}
int BinaryTree::BinaryTreeHeight(BinaryTreeNode *t)const
{
	if(!t) return 0;
	int hl=BinaryTreeHeight(t->LeftChild);
	int hr=BinaryTreeHeight(t->RightChild);
	if(hl>hr) return ++hl;
	else return ++hr;
}
void BinaryTree::MakeTree(const int &element,BinaryTree &left,BinaryTree &right)
{
	root=new BinaryTreeNode(element,left.root,right.root);	
}
void main()
{
	fstream infile;
	infile.open("input.txt",ios::in);
	if(!infile)
	{
		cout<<"input.txt can't open";
		exit(1);
	}
	int n,i,j,r,l,m;
	infile>>n;
	if(n==0)return;
	int** a=new int*[n];
	for(i=0;i<n;i++)
	{
		a[i]=new int[3];
	}
    for(i=0;i<n;i++)
		for(j=0;j<3;j++)
			infile>>a[i][j];
	BinaryTree *x=new BinaryTree[n];
	BinaryTreeNode **S=new BinaryTreeNode*[n];
	for( i=n-1; i>=0; i--)
	{
		x[a[i][0]].MakeTree(a[i][0], x[a[i][1]], x[a[i][2]]);
	} 
	j=a[0][0];
	BinaryTreeNode *rot=x[j].getroot();
    outfile<<x[j].BinaryTreeHeight(rot)<<endl;
	x[j].Preorder(rot,n,S);
	outfile<<endl;
	x[j].Inorder(rot,n,S);
	outfile<<endl;
	x[j].Postorder(rot,n,S);
	outfile.close();
	infile.close();
	for( i=0; i<n; i++)
	{
		x[a[i][0]].BreakTree(a[i][0], x[a[i][1]], x[a[i][2]]);
	} 
	return;
}