标题: [转]非递归算法建立二叉树！ [打印本页]

---

作者: 冷酷鲨鱼    时间: 2010-4-12 19:04     标题: [转]非递归算法建立二叉树！

本帖最后由 冷酷鲨鱼 于 2010-4-12 19:07 编辑

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

这个问题么，不知道有多少人想过！也不知道有多少人去尝试着写过!我在网络上找了一下相关的代码.奇怪的是,提出这个问题的人倒是有几个!很少!但是都是没人解答的!可惜可惜!有意思了阿!可不可以实现都是一个迷题!(书上也没有提到能不能建立这个问题！连清华大学的那个严老师的讲座里面也没有提到过这个问题！)
经过几天的研究！郁闷阿！哭！
今天终于让我给写出来了！高兴啊！代码很简单！下面有注释的！

#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");
}
//代码中提供了几组测试数据！可供测试！希望大家指点！
如果把先序带结束符号的输入改为中序带结束符号的输入，
那么建立的树是不唯一的！
不需要考虑
如果把先序带结束符号的输入改为后序带结束符号的输入，
能否建立一个唯一的二叉树，我不知道！望大家一起讨论下！理论上说是可以的！

---

作者: semiconductor3    时间: 2010-6-9 23:08

怎么说呢，你没发现在你的程序里char *s,s是个指针变量么，在你的判断语句中都是拿s和字符比较的，难道不应该是*s和他们比较么，刚才修改后编译了一下，通过了，但运行结果不允许任何输入，也没有任何输出。有兴趣的话咱们可以交流一下，留下qq：932164057

---

欢迎光临 【3.A.S.T】网络安全爱好者 (http://3ast.com/)

Powered by Discuz! 7.2