[转]非递归算法建立二叉树！
[i=s] 本帖最后由 冷酷鲨鱼 于 2010-4-12 19:07 编辑 [/i]输入带结束符号的先序序列，非递归算法建立二叉树！网上暂时没有发布！我自己写了一个！请大家指点！
这个问题么，不知道有多少人想过！也不知道有多少人去尝试着写过!我在网络上找了一下相关的代码.奇怪的是,提出这个问题的人倒是有几个!很少!但是都是没人解答的!可惜可惜!有意思了阿!可不可以实现都是一个迷题!(书上也没有提到能不能建立这个问题！连清华大学的那个严老师的讲座里面也没有提到过这个问题！)
经过几天的研究！郁闷阿！哭！
今天终于让我给写出来了！高兴啊！代码很简单！下面有注释的！
#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("%c ",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="ABC00D0E00f00#";
s2="DBA00C00E00#";
s3="ABC0000#";
s4="a0b0c00#";
s5="dbac000e00fg000#";
s6="abd00e00cf00g00#";
s7="ABC00DG000EF000#";
T1=PreCreate(s1);
PrintTreePre(T1);
printf("\n");
T2=PreCreate(s2);
PrintTreePre(T2);
printf("\n");
T3=PreCreate(s3);
PrintTreePre(T3);
printf("\n");
T4=PreCreate(s4);
PrintTreePre(T4);
printf("\n");
T5=PreCreate(s5);
PrintTreePre(T5);
printf("\n");
T6=PreCreate(s6);
PrintTreePre(T6);
printf("\n");
T7=PreCreate(s7);
PrintTreePre(T7);
printf("\n");
}
//代码中提供了几组测试数据！可供测试！希望大家指点！
如果把先序带结束符号的输入改为中序带结束符号的输入，
那么建立的树是不唯一的！
不需要考虑
如果把先序带结束符号的输入改为后序带结束符号的输入，
能否建立一个唯一的二叉树，我不知道！望大家一起讨论下！理论上说是可以的！ 怎么说呢，你没发现在你的程序里char *s,s是个指针变量么，在你的判断语句中都是拿s和字符比较的，难道不应该是*s和他们比较么，刚才修改后编译了一下，通过了，但运行结果不允许任何输入，也没有任何输出。有兴趣的话咱们可以交流一下，留下qq：932164057
页:
[1]