trav.cpp

非递归遍历问题 分别写出以非递归方式按前序、中序和后序遍历二叉树的算法。

#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;


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,ostream &out);
	void Inorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack,ostream &out);
	void Postorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack,ostream &out);
	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,ostream &out)
{
    BinaryTreeNode *p;
	int top=0;
	p=t;
	do
	{
		while(p!=NULL)
		{
			out<<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,ostream &out)
{	
	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--;
			out<<p->data<<" ";
			p=p->RightChild;
		}
	}while(p!=NULL||top!=0);     
}


void BinaryTree::Postorder(BinaryTreeNode *t,int &n,BinaryTreeNode **&Stack,ostream &out)
{
	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--;
				out<<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,outfile;
	infile.open("input.txt",ios::in);
	if(!infile)
	{
		cout<<"input.txt can't open"<<endl;
		exit(1);
	}
	outfile.open("output.txt",ios::out);


	int n,i,j;
	infile>>n;
	if(n==0)
	{
		outfile<<"error!"<<endl;
		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 b;
	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);
	outfile<<endl;
	x[j].Inorder(rot,n,S,outfile);
	outfile<<endl;
	x[j].Postorder(rot,n,S,outfile);
	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]]);
	}
	for(i=0;i<n;i++)
		delete []a[i];
	delete []a;
	a=0;
	return;
}