输入带结束符号的先序序列，非递归算法建立二叉树！网上暂时没有发布！我自己写了一个！请大家指点！(0分)

这个问题么，不知道有多少人想过！也不知道有多少人去尝试着写过!我在网络上找了一下相关的代码.奇怪的是,提出这个问题的人倒是有几个!很少!但是都是没人解答的!可惜可惜!有意思了阿!可不可以实现都是一个迷题!(书上也没有提到能不能建立这个问题！连清华大学的那个严老师的讲座里面也没有提到过这个问题！)
经过几天的研究！郁闷阿！哭！
今天终于让我给写出来了！高兴啊！代码很简单！下面有注释的！
#include <stdio.h>
#include <stdlib.h>
typedef struct Tree
{
char data;
Tree *lchild,*rchild;
int left,right;
}Tree;
typedef struct Stack
{
Tree *data;
Stack *next;
Stack *top;
}Stack;
void Push(Tree *p,Stack *L) //压栈
{
Stack *t;
t=(Stack *)malloc(sizeof(Stack));
t->data=p;
t->next=L->top;
L->top=t;
}
Tree *Pop(Stack *L)//出栈
{
Tree *p;
Stack *q;
if (L->top->next==NULL) return NULL;
else
{
q=L->top;
p=q->data;
L->top=q->next;
free(q);
}
return p;
}
Tree *GetTop(Stack *L)//获取栈顶元素
{
return L->top->data;
}
void PrintTreePre(Tree *t)//打印先序序列
{
if (t!=NULL)
{
printf(&quot;%c &quot;,t->data);
PrintTreePre(t->lchild);
PrintTreePre(t->rchild);
}
}
Tree * PreCreate(char *s) //s为一个字符串，
{//输入带结束符号的先序序列,非递归建立二叉树,结束符号为#,函数返回根节点的指针
Tree *p,*root,*q;//定义一些节点,p用来表示移动根节点,root用来表示树的根节点,q表示当前申请的节点
Stack *L;//定义一个栈
int i=0;//这个是字符串的下标
L=(Stack *)malloc(sizeof(Stack));//申请栈的节点空间
L->next=NULL;//该头节点的next域为空
L->top=L;//栈顶指向该节点
if (s=='0'||s=='#')
{
root=NULL;//如果第一个字符为空，那么就直接返回空
return root;
}
else
//如果第一个字符不为空
{
p=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
p->data=s;//设置节点数据域为这个自符
p->lchild=NULL;//节点左孩子为空
p->rchild=NULL;//节点右孩子为空
root=p;//这个就是根节点了
Push(p,L);//把这个节点入栈
}
i++;//下标加1
while (s!='#')//如果不是结束符号，就循环
{
while (s!='0'&&s!='#')//如果不是0或者结束符号
{
q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
q->data=s;//设置节点数据域为这个自符
q->lchild=NULL;//节点左孩子为空
q->rchild=NULL;//节点右孩子为空
p=GetTop(L);//获取栈顶的元素
p->lchild=q;//左孩子赋值
Push(q,L);//把这个节点压栈
i++;//下标加1
}
if(L->top->next!=NULL&&s!='#')
{
p=GetTop(L);//把栈顶元素给p
i++;//下标加1
if (s=='#') break;//看看是不是结束符号,是的话,就退出循环
if(s!='0')//如果不是0的话
{
q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
q->data=s;//设置节点数据域为这个自符
q->lchild=NULL;//节点左孩子为空
q->rchild=NULL;//节点右孩子为空
p->rchild=q;//右孩子赋值
Pop(L);//出栈
Push(q,L);//把这个节点压栈
}
i++;//下标加1
}
}
return root;
}
void main()
{
Tree *T1,*T2,*T3,*T4,*T5,*T6,*T7;
char *s1,*s2,*s3,*s4,*s5,*s6,*s7;
s1=&quot;ABC00D0E00f00#&quot;;
s2=&quot;DBA00C00E00#&quot;;
s3=&quot;ABC0000#&quot;;
s4=&quot;a0b0c00#&quot;;
s5=&quot;dbac000e00fg000#&quot;;
s6=&quot;abd00e00cf00g00#&quot;;
s7=&quot;ABC00DG000EF000#&quot;;
T1=PreCreate(s1);
PrintTreePre(T1);
printf(&quot;/n&quot;
T2=PreCreate(s2);
PrintTreePre(T2);
printf(&quot;/n&quot;
T3=PreCreate(s3);
PrintTreePre(T3);
printf(&quot;/n&quot;
T4=PreCreate(s4);
PrintTreePre(T4);
printf(&quot;/n&quot;
T5=PreCreate(s5);
PrintTreePre(T5);
printf(&quot;/n&quot;
T6=PreCreate(s6);
PrintTreePre(T6);
printf(&quot;/n&quot;
T7=PreCreate(s7);
PrintTreePre(T7);
printf(&quot;/n&quot;
}
//代码中提供了几组测试数据！可供测试！希望大家指点！
如果把先序带结束符号的输入改为中序带结束符号的输入，
那么建立的树是不唯一的！
不需要考虑
如果把先序带结束符号的输入改为后序带结束符号的输入，
能否建立一个唯一的二叉树，我不知道！望大家一起讨论下！理论上说是可以的！

建栈解决与递归没什么区别，而且代码非常复杂，不简洁。

这段代码的栈完全可以用数组代替!很多的代码都是测试代码
关键代码就这一段
Tree * PreCreate(char *s) //s为一个字符串，
{//输入带结束符号的先序序列,非递归建立二叉树,结束符号为#,函数返回根节点的指针
Tree *p,*root,*q;//定义一些节点,p用来表示移动根节点,root用来表示树的根节点,q表示当前申请的节点
Stack *L;//定义一个栈
int i=0;//这个是字符串的下标
L=(Stack *)malloc(sizeof(Stack));//申请栈的节点空间
L->next=NULL;//该头节点的next域为空
L->top=L;//栈顶指向该节点
if (s=='0'||s=='#')
{
root=NULL;//如果第一个字符为空，那么就直接返回空
return root;
}
else
//如果第一个字符不为空
{
p=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
p->data=s;//设置节点数据域为这个自符
p->lchild=NULL;//节点左孩子为空
p->rchild=NULL;//节点右孩子为空
root=p;//这个就是根节点了
Push(p,L);//把这个节点入栈
}
i++;//下标加1
while (s!='#')//如果不是结束符号，就循环
{
while (s!='0'&&s!='#')//如果不是0或者结束符号
{
q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
q->data=s;//设置节点数据域为这个自符
q->lchild=NULL;//节点左孩子为空
q->rchild=NULL;//节点右孩子为空
p=GetTop(L);//获取栈顶的元素
p->lchild=q;//左孩子赋值
Push(q,L);//把这个节点压栈
i++;//下标加1
}
if(L->top->next!=NULL&&s!='#')
{
p=GetTop(L);//把栈顶元素给p
i++;//下标加1
if (s=='#') break;//看看是不是结束符号,是的话,就退出循环
if(s!='0')//如果不是0的话
{
q=(Tree *)malloc(sizeof(Tree));//直接申请节点空间
q->data=s;//设置节点数据域为这个自符
q->lchild=NULL;//节点左孩子为空
q->rchild=NULL;//节点右孩子为空
p->rchild=q;//右孩子赋值
Pop(L);//出栈
Push(q,L);//把这个节点压栈
}
i++;//下标加1
}
}
return root;
}