建立一棵用二叉链表方式存储的二叉树，并对其进行先序遍历，打印输出结果

Question

基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序）然后将遍历结果打印输出。要求用递归和非递归两种方法实现。
测试数据：ABC##DE#G##F###

Answer 1

#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;
}

程序如上，递归实现了先序遍历，非递归实现了中序遍历。
其他遍历类似。
程序是可以运行的。本回答被提问者采纳