tree.cpp

非递归先序

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxSize 30

typedef struct node
{
	char data;  //数据元素
	struct node *lchild;  //指向左孩子
	struct node *rchild;  //指向右孩子
}BTNode;

//根据二叉树广义表的字符串a创建二叉树
void CreateBTNode(BTNode *&b,char *a)
{
	BTNode *s[MaxSize]; //s数组作为存储二叉树中根结点指针的栈
	int top=-1; //用top作为s栈的栈顶指针并初始化
	int k;  //用k作为处理左子树或右子树的标记，k=1处理左子树，k=2处理右子树
	b=NULL;  //初始时二叉树为空
	BTNode *p=NULL; //定义p为指向二叉树结点的指针

	int i=0; //用i扫描数组a中存储的二叉树广义表字符串   
	while(a[i]!='\0')  //a未扫描完时循环
	{
		switch(a[i])
		{
			case'(':
				top++; s[top]=p;k=1; //为左结点
				break; 
			case')':
				if(top==-1){
					cout<<"二叉树广义表字符串出错!"<<endl;
					exit(1);
				}
				top--;break;
			case',':
				k=2;  //为右结点
				break;  
			default:
				p=(BTNode *)malloc(sizeof(BTNode));
				p->data=a[i]; p->lchild=p->rchild=NULL;
				if(b==NULL)  b=p;  //p指向二叉树的根结点
				else
				{
					if(k==1) s[top]->lchild=p;
					else s[top]->rchild=p;
				}
		}
		i++;  //为扫描下一字符修改i的值
	}
}

void PreOrder(BTNode *b) //先序遍历二叉树的非递归算法
{
	BTNode *s[MaxSize],*p;
	int top=-1;
	if(b!=NULL)
	{
		top++;
		s[top]=b;  //根结点入栈
		while(top>-1)  //栈不空时循环
		{
			p=s[top];  //退栈并访问该结点
			top--;
			cout<<p->data<<' ';
			if(p->rchild!=NULL)  //右孩子入栈
			{
				top++; s[top]=p->rchild;
			}
			if(p->lchild!=NULL)  //左孩子入栈
			{
				top++; s[top]=p->lchild;
			}
		}
		cout<<endl;		
	}
}

void InOrder(BTNode *b)  //中序遍历二叉树的非递归算法
{
	BTNode *s[MaxSize],*p;
	int top=-1;
	if(b!=NULL)  //二叉树不为空
	{
		p=b;  //p指向树根结点
		while(top>-1||p!=NULL)
		{
			while(p!=NULL)//当p非空时进栈接着指向左孩子
			{
				top++;	s[top]=p;
				p=p->lchild;
			}
			if(top>-1)//栈非空时，退栈，输出结点值，接着指向右孩子
			{
				p=s[top];  top--;
				cout<<p->data<<' ';			
				p=p->rchild;
			}
		}
	    cout<<endl;	
	}
}

void PostOrder(BTNode *b) //后序遍历二叉树的非递归算法
{
	BTNode *s[MaxSize],*p;
	int top=-1;
	int flag;
	if(b!=NULL)
	{
		do{
			while(b!=NULL)  //将b所有左子树入栈
			{
				top++; s[top]=b;
				b=b->lchild;
			}
			p=NULL;  //p指向当前结点的前一个已访问的结点
			flag=1;  //设置b的访问标记为已访问过
			while(top!=-1&&flag)
			{
				b=s[top];  //取出当前栈顶元素
				if(b->rchild==p) //右子树不存在或已被访问，访问之
				{
					cout<<b->data<<' ';
					top--; 
					p=b;  //p指向刚被访问的结点
				}
				else
				{
					b=b->rchild;  //b指向右子树
					flag=0;  //设置未被访问的标记
				}
			}
		}while(top!=-1);
		cout<<endl;
	}
}

void main()
{
	BTNode *b;
	cout<<"二叉树为：A(B(,D),C(E,)) "<<endl;
	CreateBTNode(b,"A(B(,D),C(E,))");
	cout<<endl;

	cout<<"先序非递归遍历序列为："<<endl;
	PreOrder(b);
	cout<<endl;

	cout<<"中序非递归遍历序列为："<<endl;
	InOrder(b);
	cout<<endl;

	cout<<"后序非递归遍历序列为："<<endl;
	PostOrder(b);
	cout<<endl;

	system("PAUSE");
	
}