pre.txt

以先序之方法遍历二叉树

// bitree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
#include<string>

using namespace std;

const int Max_size=100;//二叉树,栈最大容量

//建立一个栈类

 //建立树的节点
class TreeNode
{	
	public:
		TreeNode *lchild;
		TreeNode *rchild;
		char data;
		TreeNode(void);
};

TreeNode::TreeNode(void){}

class Stack 
{
	private:
		TreeNode* stack_c[Max_size];
		int top;
	public:
		 Stack(void);//类的构造函数
		TreeNode* Pop(void) ;//出栈
		void Push(TreeNode* item);//进栈
		void Clear(void);//清空
		int Size(void);//返回栈的实际大小
		bool IsEmptyStack(void);//判断栈是否为空
};

 Stack::Stack(void)
{
	top=-1;
}

 void Stack::Push(TreeNode* item)
 {
	 if(top==Max_size-1)
	 {
		cout<<"栈已满！"<<endl;
		exit(1);
	 }
	 top++;
	 
	 stack_c[top]=item;
}
 TreeNode* Stack::Pop(void)
 {
	if(top==-1)
	{
		cout<<"栈已空！"<<endl;
		exit(1);
	}
	TreeNode* ch;
	ch=stack_c[top];
	top--;
	return ch;
 }
 void Stack::Clear(void)
 {
	 top=-1;
 }

 int Stack::Size(void)
 {
	 return top;
 }

 bool Stack::IsEmptyStack(void)
 {
	 if(top==-1)
		 return true;
	 else
		 return false;
 }


//建立创建二叉树的类
class Bitree
{
	private:
	TreeNode *q_node[Max_size];
	TreeNode *root;
	TreeNode *node;
	int front,rear;
	public:
		int size;
		Bitree();
		TreeNode *	Copy(TreeNode *T);//复制二叉树
		TreeNode * Create_Tree();
};

Bitree::Bitree()
{
	root=NULL;
	front=1;
	rear=0;
	size=0;
}


TreeNode * Bitree::Create_Tree()
{
	char ch;
	
	cout<<"请输入数据（以#结束）：";
	cin>>ch;
	while(ch!='#')
	{
		node=NULL;
		if(ch!='*'&&ch!=' ')//以*表示虚节点，以空格表示输入间隔
		{
			node=new TreeNode;
			node->data=ch;
			node->lchild=NULL;
			node->rchild=NULL;
			if(ch!='*')
			size++;
		}
		
		if(ch!=' ')
		{
			rear++;
			q_node[rear]=node;
		}

		if(rear==1)
			root=node;
		else
		{
			if((node!=NULL)&&q_node[front]!=NULL)
			{
				if(rear%2==0)
					q_node[front]->lchild=node;
				else
					q_node[front]->rchild=node;
			}
			if(rear%2==1)
				front++;
		}
		cin>>ch;

	}
	return root;
}

TreeNode *Bitree::Copy(TreeNode *T)//以先序遍历，边遍历边复制
{
	Stack s1,s2;
	TreeNode * N,*p,*q;
	
	N=new TreeNode;
	q=N;
	p=T;
	
	while(!s1.IsEmptyStack()||p)
	{
		if(p)
		{
			s1.Push(p);
			q->data=p->data;
			s2.Push(q);
			p=p->lchild;
			if(p)
			{
				q->lchild=new TreeNode;
				q=q->lchild;
			}
			else
				q->lchild=NULL;
		}
		else
		{
			p=s1.Pop();
			q=s2.Pop();
			p=p->rchild;
			if(p)
			{
				q->rchild=new TreeNode;
				q=q->rchild;
			}
			else
				q=q->rchild=NULL;
				
		}
	}
return N;	
}

class TraverTree
{
	public:
		TraverTree();
		bool Visit(TreeNode *node);//访问数据
		//递归遍历
		void PreOrder1(TreeNode *T);
		void InOrder1(TreeNode *T);
		void PostOrder1(TreeNode *T);
		//非递归遍历
		void PreOrder2(TreeNode *T);
		void InOrder2(TreeNode *T);
		void PostOrder2(TreeNode *T);
};

TraverTree::TraverTree(){}

//递归算法
bool TraverTree::Visit(TreeNode *node)
{
	if(node)
	{
		cout<< node->data;
		cout<<' ';
		return true;
	}
	else
	{
		return false;
	}
}

void TraverTree::PreOrder1(TreeNode *T)
{
	 if(T)
	 {
		 if(Visit(T))
		 {
		 	PreOrder1(T->lchild);
			PreOrder1(T->rchild);
		 }
	 }







//非递归算法
void TraverTree::PreOrder2(TreeNode *T)
{
	TreeNode *p;
	Stack stack;
	p=T;
	while(p||!stack.IsEmptyStack())
	{
		if(p)
		{
			Visit(p);
			stack.Push(p);
			p=p->lchild;
		}
		else
		{
			if(!stack.IsEmptyStack())
			{
				p=stack.Pop();
				p=p->rchild;
			}
		}
	}

}
	}

}