问题描述

为什么二叉树的中序非递归算法无法实现

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

#include "stdafx.h"
#include
using namespace std;
#define true 1
#define false 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{//二叉树的存储结构
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量

}SqStack;
Status InitStack(SqStack &S)
{//构造一个空栈S
S.base=new SElemType[MAXSIZE];
if(!S.base ) exit(OVERFLOW);
S.top =S.base ;
S.stacksize=MAXSIZE;
return OK;
}
Status Push(SqStack &S,SElemType e)
{//
if (S.top-S.base==S.stacksize ) return ERROR;

    *S.top++=e;
return OK;

}
Status Pop(SqStack &S,SElemType e)
{//
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
SElemType GetTop(SqStack S)
{//
if(S.top!=S.base )
return *(S.top-1);
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else ERROR;
}
void CreatBiTree(BiTree &T)
{//先序遍历的顺序建立二叉链表
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{
T=new BiTNode;
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}

}
void PreOrderTraverse(BiTree T)
{//前序遍历递归算法
if(T)
{
cout<data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
Status InOrderTraverse(BiTree T)
{//中序遍历递归算法
if(T)
{
InOrderTraverse(T->lchild);
cout<data;
InOrderTraverse(T->rchild);
}
return OK;
}
void InOrderTraverse_non(BiTree &T)
{//中序遍历非递归算法
SqStack S;
InitStack(S);
BiTree p,q;
p=T;
q=new BiTNode;
while (p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}
else
{
Pop(S,q);
cout<data;
p=q->rchild;
}
}
}
void PostOrderTraverse(BiTree T)
{//后序遍历递归算法
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<data;
}

}

int Depth(BiTree T)
{//计算二叉树的深度
int m,n;
if(T==NULL) return 0;
else
{
m=Depth(T->lchild );
n=Depth(T->rchild );
if(m>n) return (m+1);
else return (n+1);
}
}
int NodeCount(BiTree T)
{//统计二叉树中的结点个数
if(T==NULL) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
Status LeafCount(BiTree &T,int m)
{//统计二叉树的叶结点个数
if(T)
{
if(!T->lchild&&!T->rchild) m++;
else m=LeafCount(T->lchild,m)+LeafCount(T->rchild,m);
}
return m;
}
Status CountTNode_1(BiTree &T,int m)
{//统计二叉树中度为1的结点个数
if(T)
{
if(!T->lchild&&T->rchild) m++ ;
if(!T->rchild&&T->lchild) m++;
else m=CountTNode_1(T->lchild,m)+CountTNode_1(T->rchild,m);
}
return m;
}
Status Exchangechild(BiTree&T)
{//交换二叉树每个结点的左孩子和右孩子
BiTree t;
if(T)
{
t=T->lchild;
T->lchild=T->rchild;
T->rchild=t;
Exchangechild(T->lchild);
Exchangechild(T->rchild);
}
return OK;
}
//void Allpath(BiTree &T,LinkStack &S)
//{
//char e;
//if(T)
// {
// Push(S,T->data);
// if(!T->lchild &&!T->rchild ) printStack(S);
//else
//{
// Allpath(T->lchild ,S);
// Allpath(T->rchild ,S);
// }
// Pop(S,e);
//}
//}
int main()
{
int choose,d,n_leaf,n_1,n_node;
int m,m_1;
m=m_1=0;
BiTree T;
cout<<"1.先序遍历递归建立二叉链表"<
cout
cout
cout
cout
cout
cout
cout
cout
cout
cout
choose=-1;
while(choose!=0)
{
cout
cin>>choose;
switch(choose)
{case 1:
cout<<"建立二叉树，请输入元素"<<endl;
CreatBiTree(T);
break;
case 2:
cout<<"元素按照前序输出为"<<endl;
PreOrderTraverse( T);
cout<<endl;
break;
case 3:
cout<<"元素按照中序递归输出为"<<endl;
InOrderTraverse(T);
break;
case 4:
cout<<"元素按照中序非递归输出为"<<endl;
InOrderTraverse_non(T);
cout<<endl;
break;
case 5:
cout<<"元素按照后序递归输出为"<<endl;
PostOrderTraverse(T);
cout<<endl;
break;
case 6:
cout<<"二叉树的深度为"<<endl;
d=Depth( T);
cout<<d<<endl;
break;
case 7:
cout<<"二叉树中的结点个数为："<<endl;
n_node=NodeCount( T);
cout<<n_node<<endl;
break;
case 8:
cout<<"二叉树中的叶子结点个数为："<<endl;
n_leaf=LeafCount(T,m);
cout<<n_leaf;
break;
case 9:
cout<<"二叉树中度为一的结点个数为："<<endl;
n_1=CountTNode_1(T,m_1);
cout<<n_1<<endl;
break;
case 10:
if(Exchangechild(T))
cout<<"左孩子右孩子交换成功"<<endl;
else cout<<"左孩子右孩子交换失败"<<endl;
break;
}
}
return 0;

}

这段代码中的中序遍历非递归算法无法实现，，为什么啊，，求大神解答

解决方案

http://www.docin.com/p-337312261.html
http://blog.csdn.net/fduan/article/details/7833653