程序填空题：非递归中序遍历
非递归中序遍历。
```c++
#include
using namespace std;
typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct StackNode
{
BiTNode data;
struct StackNode *next;
}StackNode,*LinkStack;
void CreateBiTree(BiTree &T)
{
char ch;
cin >> ch;
if(ch=='#') T=NULL;
else{
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InitStack(LinkStack &S)
{
S=NULL;
}
bool StackEmpty(LinkStack S)
{
if(!S)
return true;
return false;
}
void Push(LinkStack &S,BiTree e)
{
StackNode *p=new StackNode;
p->data=*e;
p->next=S;
S=p;
}
void Pop(LinkStack &S,BiTree e)
{
if(S!=NULL)
{
*e=S->data;
StackNode *p=S;
S=S->next;
delete p;
}
}
void InOrderTraverse1(BiTree T)
{
LinkStack S; BiTree p;
BiTree q=new BiTNode;
InitStack(S); p=T;
while(p||!StackEmpty(S))
{
if(p)
{
@@[Push(S,p)](2);
@@[p=p->lchild](2);
}
else
{
@@[Pop(S,q)](2);
cout<data;
@@[p=q->rchild](2);
}
}
}
int main()
{
BiTree tree;
CreateBiTree(tree);
InOrderTraverse1(tree);
return 0;
}
```
答案：
第1空：Push(S,p)
第2空：p=p->lchild
第3空：Pop(S,q)
第4空：p=q->rchild
```c++
#include
using namespace std;
typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct StackNode
{
BiTNode data;
struct StackNode *next;
}StackNode,*LinkStack;
void CreateBiTree(BiTree &T)
{
char ch;
cin >> ch;
if(ch=='#') T=NULL;
else{
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InitStack(LinkStack &S)
{
S=NULL;
}
bool StackEmpty(LinkStack S)
{
if(!S)
return true;
return false;
}
void Push(LinkStack &S,BiTree e)
{
StackNode *p=new StackNode;
p->data=*e;
p->next=S;
S=p;
}
void Pop(LinkStack &S,BiTree e)
{
if(S!=NULL)
{
*e=S->data;
StackNode *p=S;
S=S->next;
delete p;
}
}
void InOrderTraverse1(BiTree T)
{
LinkStack S; BiTree p;
BiTree q=new BiTNode;
InitStack(S); p=T;
while(p||!StackEmpty(S))
{
if(p)
{
@@[Push(S,p)](2);
@@[p=p->lchild](2);
}
else
{
@@[Pop(S,q)](2);
cout<
@@[p=q->rchild](2);
}
}
}
int main()
{
BiTree tree;
CreateBiTree(tree);
InOrderTraverse1(tree);
return 0;
}
```
答案：
第1空：Push(S,p)
第2空：p=p->lchild
第3空：Pop(S,q)
第4空：p=q->rchild
