非递归遍历问题540trav.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class BinaryTreeNode
{
	friend class BinaryTree;
public:
	int data;
	BinaryTreeNode  *LeftChild,*RightChild;
	BinaryTreeNode(){LeftChild=RightChild=0;}
	BinaryTreeNode(const int& e)
	{
		data=e;
		LeftChild=RightChild=0;
	}
	BinaryTreeNode(const int& e,BinaryTreeNode *l,BinaryTreeNode *r)
	{
		data=e;
		LeftChild=l;
		RightChild=r;
	}
};

class BinaryTree
{
public:
	BinaryTreeNode *root;
	void PreOrder(BinaryTreeNode *u);
	void InOrder(BinaryTreeNode *u);
	void PostOrder(BinaryTreeNode *u);
	int Height(BinaryTreeNode *t)const;
	BinaryTree(){root=0;};
	~BinaryTree(){};
	bool Empty()const
	{
		return ((root)?false:true);
	}
	bool Root(int &x);
	void BreakTree(int &element,BinaryTree& left,BinaryTree& right);
	int Height()
	{
		return Height(root);
	}
};
bool BinaryTree::Root(int &x)
{
	if(root)
	{
		x=root->data;
		return true;
	}
	else return false;
}
void BinaryTree::BreakTree(int &element,BinaryTree &left,BinaryTree &right)
{
	if(!root)
		cout<<"empty"<<endl;
	element=root->data;
	left.root=root->LeftChild;
	right.root=root->RightChild;
	delete root;
	root=0;
}
void BinaryTree::PreOrder(BinaryTreeNode *u)
{
	const int max=100000;
	BinaryTreeNode *s[max];
	int top=-1;
	BinaryTreeNode *p=u;
	while(top!=-1||p!=0)
	{
		while(p!=0)
		{
			out<<p->data<<' ';
			if(p->RightChild!=0)
			{
				top++;
				s[top]=p->RightChild;
			}
			p=p->LeftChild;
		}
		if(top!=-1)
		{
			p=s[top];
			top--;
		}
	}
}
void BinaryTree::InOrder(BinaryTreeNode *u)
{
	const int max=100000;
	BinaryTreeNode *s[max];
	int top=-1;
	BinaryTreeNode *p=u;
	while(top!=-1||p!=0)
	{
		while(p!=0)
		{
			top++;
			s[top]=p;
			p=p->LeftChild;
		}
		if(top!=-1)
		{
			p=s[top];
			top--;
			out<<p->data<<' ';
			p=p->RightChild;
		}
	}
}
void BinaryTree::PostOrder(BinaryTreeNode *u)
{
	const int max=100000;
	BinaryTreeNode *s[max];
	int top=-1;
	BinaryTreeNode *p=u;
	while(top!=-1||p!=0)
	{
		while(p!=0)
		{
			top++;
			s[top]=p;
			if(p->LeftChild)
				p=p->LeftChild;
			else
				p=p->RightChild;
		}
		p=s[top];
		top--;
		out<<p->data<<' ';
		while(top!=-1&&s[top]->RightChild==p)
		{
			p=s[top--];
			out<<p->data<<' ';
		}
		if(top!=-1)
			p=s[top]->RightChild;
		else
			p=0;
	}
}
int BinaryTree::Height(BinaryTreeNode *t)const
{
	if(!t)
		return 0;
	int hl=Height(t->LeftChild);
	int hr=Height(t->RightChild);
	if(hl>hr)
		return ++hl;
	else
		return ++hr;
}

int main()
{
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int n,h;
	in>>n;
	int *a=new int[3*n];
	for(int i=1;i<=3*n;i++)
		in>>a[i];
	BinaryTree *tree=new BinaryTree[n];
	for(i=1;i<=n;i++)
	{
		BinaryTreeNode *node=0;
		node=new BinaryTreeNode;
		tree[i].root=node;
		tree[i].root->data=i;
	}
	for(i=1;i<=n;i++)
	{
		if(a[3*i-1]==0)
			tree[a[3*i-2]].root->LeftChild=0;
		else
			tree[a[3*i-2]].root->LeftChild=tree[a[3*i-1]].root;
		if(a[3*i]==0)
			tree[a[3*i-2]].root->RightChild=0;
		else
			tree[a[3*i-2]].root->RightChild=tree[a[3*i]].root;
	}
	h=tree[a[1]].Height();
	out<<h<<endl;
	tree[a[1]].PreOrder(tree[a[1]].root);
	out<<endl;
	tree[a[1]].InOrder(tree[a[1]].root);
	out<<endl;
	tree[a[1]].PostOrder(tree[a[1]].root);
	out<<endl;
	return 1;
}