今天在百度知道，回答别人的问题，写的。

特此记录

#include<iostream>
using namespace std;
class tree
{
public:
tree(){lchild=NULL;rchild=NULL;}
char data;
class tree *lchild;
class tree *rchild;
};
void build(tree *&t)//先序建树
{
char c;
cin>>c;
if(c=='#')
{
t=NULL;
}
else
{
t=new tree;
t->data=c;
build(t->lchild);
build(t->rchild);
}
}

void preorder(tree *root)//这是递归实现
{
if (root!=NULL)
{
preorder(root->lchild);
cout<<root->data;
preorder(root->rchild);
}

}
class stack
{
public:
tree *top,*base;
};
void init (stack *s)//初始化栈
{
s->base=new tree[100];
s->top=s->base;
}
void push(stack *s,tree *t)//入栈
{
*(s->top++)=*t;
}
void pop(stack *s,tree &t)//取栈顶元素
{
t=*(--(s->top));
}
void inorder(tree *t)//这是非递归实现
{
stack *s=new stack;
tree *p;
init(s);
p=t;
tree temp=*t;
while(p||s->top!=s->base)
{
while(p)
{
   push(s,p);
   p=p->lchild;
}
if(s->top!=s->base)
{
   pop(s,temp);
   cout<<temp.data;
   p=temp.rchild;
}
}
}
int main()
{
tree *t;
build(t);
preorder(t);
cout<<"非递归中序遍历"<<endl;
inorder(t);
cout<<endl;
return 0;
}

如下输入

234##5#6##7##回车
就可以看到结果。

树的图形对应为