在先序中序非递归算法中为什么使用栈？能不能借助其他数据结构来实现？

二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现
悬赏分：20 | 提问时间：2010-6-14 22:33 | 提问者：zjkgood
要求：遍历的内容应是千姿百态的。
树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
要求：遍历的内容应是千姿百态的。

推荐答案

#include <iostream>
using namespace std;//二叉树链式存储的头文件
typedef char datatype;//结点属性值类型
typedef struct node // 二叉树结点类型
{
datatype data;
struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;//指向二叉树结点指针
//下面是些栈的操作 为非递归实现做准备
typedef struct stack//栈结构定义
{
bintree data[100];//data元素类型为指针
int tag[100];//为栈中元素做的标记，，用于后续遍历
int top;//栈顶指针
}seqstack;
void push(seqstack *s,bintree t)//进栈
{
s->data[++s->top]=t;
}

bintree pop(seqstack *s) //出栈
{
if(s->top!=-1)
{s->top--;
return(s->data[s->top+1]);
}
else
return NULL;
}

//按照前序遍历顺序建立一棵给定的二叉树
void createbintree(bintree *t)
{
char ch;
if((ch=getchar())== '-')
*t=NULL;
else
{
*t=(bintnode*)malloc(sizeof(bintnode));//产生二叉树根结点
(*t)->data=ch;
createbintree(&(*t)->lchild);//递归实现左孩子的建立
createbintree(&(*t)->rchild);//递归实现右孩子的建立
}
}
//二叉树前序遍历递归实现
void preorder(bintree t)//t是指针变量，而不是结点结构体变量
{if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//二叉树前序遍历非递归实现
void preorder1(bintree t)
{
seqstack s;
s.top=-1;//top 的初始值为-1；
while((t)||(s.top!=-1))//当前处理的子树不为空或者栈不为空，则循环
{
while(t)
{
cout<<t->data<<" ";//访问当前子树根结点
s.top++;
s.data[s.top]=t;
t=t->lchild;
}
if(s.top>-1)
{
t=pop(&s);//当前子树根结点出栈
t=t->rchild;//访问其右孩子
}
}
}
//二叉树中序遍历递归算法
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
// 二叉树中序遍历非递归算法
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL)||(s.top!=-1))
{
while(t)
{
push(&s,t);
t=t->lchild;//子树跟结点全部进栈
}
if(s.top!=-1)
{
t=pop(&s);
cout<<t->data<<" ";//输出跟结点，其实也就是左孩子或者有孩子（没有孩子的结点是他父亲的左孩子或者有孩子）
t=t->rchild;//进入右孩子访问
}
}
}
//后续递归遍历二叉树
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
};
//后序遍历 非递归实现
void postorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t)||(s.top!=-1))
{
while(t)
{
s.top++;
s.data[s.top]=t;//子树根结点进栈
s.tag[s.top]=0;//设此根结点标志初始化为0，表示左右孩子都么有访问，当访问完左子树，tag变为1；
t=t->lchild;//进入左子树访问。（左子树根结点全部进栈）
}
while((s.top>-1)&&(s.tag[s.top]==1))
{
t=s.data[s.top];
cout<<t->data<<" ";//没有孩子的根结点，也就是它父亲的左孩子或者右孩子
s.top--;
}
if(s.top>-1)
{
t=s.data[s.top];
s.tag[s.top]=1;//进入右孩子前，标志tag变为1；
t=t->rchild;//进入右孩子
}
else
t=NULL;
}
}
int main()
{
bintree tree;
cout<<"输入根结点：" ;
createbintree(&tree);
cout<<"\n 前序递归遍历二叉树；";
preorder(tree);
cout<<"\n 前序非递归遍历二叉树：";
preorder1(tree);
cout<<"\n-------------------------------\n";
cout<<"\n 中序遍历递归二叉树；";
inorder(tree);
cout<<"\n 中序非递归遍历二叉树：";
inorder1(tree);
cout<<"\n----------------------------\n";
cout<<"\n 后序递归遍历二叉树：";
postorder(tree);
cout<<"\n 后序非递归遍历二叉树：";
postorder1(tree);
cout<<endl;

#include<iostream>
using namespace std;
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#define maxsize 20 //最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data;
int m; //结点的深度
struct node*lchild,*rchild;
}Bitree;
Bitree*Q[maxsize];
Bitree*creatree()
{
char ch;
int front,rear;
// int i=1;
Bitree *T,*s;
T=NULL;
front=1;
rear=0;
cout<<"请输入数据"<<endl;
cin>>ch;
while(ch!='#')
{
// cin>>ch;
s=NULL;
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree));
s->data =ch;
s->lchild =s->rchild =NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
T=s;
T->m=1; //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s;
Q[front]->lchild ->m =Q[front]->m+1;
}
else
{
Q[front]->rchild =s;
Q[front]->rchild ->m =Q[front]->m+1;
}

if(rear%2==1)
front++;
}
//i++;
cin>>ch;
}
return T;
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0);
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1);
else
return (countleaf(T->lchild)+countleaf(T->rchild));
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0);
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1);
else
return (treedepth(T->rchild )+1);
}
}
void output(Bitree*T) //输出打印二叉数
{
int i;
if(T!=NULL)
{
output(T->rchild ); //右根左遍历二叉数，结果从上到下显示
for(i=1;i<=M;i++)
{
if(i!=T->m)
cout<<" ";
else
cout<<T->data ;
}
cout<<endl;
//cout<<T->data ;
output(T->lchild );
}
}

int menu_select( )
{
int sn;
printf(" 打印二叉树问题\n");
printf("==================\n");
printf(" 1 二叉树的建立\n");
printf(" 2 打印二叉树\n");
printf(" 3 求二叉树叶子结点个数\n");
printf(" 4 求二叉树的深度\n");
printf(" 0 退出系统\n");
printf("==================\n");
printf(" 请 选 择0－4：\n");
for( ; ; )
{
scanf( "%d", &sn);
if( sn <0||sn>4)
printf("\n\t输入错误，重选0－4：\n");
else
break;
}
return sn;
}

int main( )
{
Bitree*T;
for(; ;)
{
switch(menu_select())
{
case 1: T=creatree();
printf("\n");
break;
case 2: cout<<"打印结果："<<endl;
output(T);
printf("\n");
break;
case 3: int i;
i=countleaf(T);
cout<<"所求二叉树叶子结点为"<<i;
cout<<endl;
break;
case 4: int j;
j=treedepth(T);
cout<<"所求二叉树深度为"<<j;
cout<<endl;
break;
case 0:printf("再见");
exit(0);
break;
}
}
return 0;
}

/*void main()
{
Bitree*T;
T=creatree();
cout<<"打印结果："<<endl;
output(T);
}*/