回 帖 发 新 帖 刷新版面

主题:[讨论]跪求原因啊,二叉树遍历问题

#define stack_init_size 100
#define stackincrement 10
#define ok 1
#define error 0
#define N 100
#define null 0
typedef int status;
typedef struct bitnode
{ char data;
  struct bitnode *lchild,*rchild;
}bitnode,*bitree;

typedef struct{
bitree *base;
bitree *top;
int stacksize;
}sqstack;

void initstack(sqstack *s)
{
s->base=(bitree*)malloc(stack_init_size*sizeof(bitree));
if(!s->base) exit(1);
s->top=s->base;
s->stacksize=stack_init_size;
}

push(sqstack *s,bitree e)
{
 if(s->top-s->base>=s->stacksize)
 {
  s->base=(bitree*)realloc(s->base,(s->stacksize+stackincrement)*sizeof(bitree));
  if(!s->base) exit(1);
  s->top=s->base+s->stacksize;
  s->stacksize+=stackincrement;
 }
 *s->top++=e;
 return ok;
}

pop(sqstack *s,bitree *e)
{
 if(s->top==s->base) return error;
 *e=*--s->top;
 return ok;
}

bitree gettop(sqstack *s)
{ bitree *e ;
 if(s->top==s->base) return error;
 *e=*s->top-1;
 return *e;
}

bitree creatree()
{int i;
char a[N];
sqstack s;
bitree ht,q,p;
scanf("%s",a);
ht=(bitree*)malloc(sizeof(bitnode));
ht->data=a[0];
p=ht;
initstack(&s);
push(&s,ht);
i=1;
while(a[i]!='\0')
 {if(a[i]!='#')
   {q=(bitree*)malloc(sizeof(bitnode));
    q->data=a[i];
   if(p==gettop(&s))
      p->lchild=q;
   else p->rchild=q;
   p=q;
   push(&s,p);
   i++;
   }
  else {if(p==gettop(&s))
        p->lchild=null;
        else p->rchild=null;
        pop(&s,&p);
        i++;
        }
  }
  return ht;
}

stackempty(sqstack *s)
{
 if(s->top==s->base) return ok;
 else return error;
}

status visit(char e)
{printf("%c",e);
return ok;
}

inorder(bitree t)
{sqstack s;
 bitree p;
 initstack(&s);
 p=t;
 while(p||!stackempty(&s))
 {if(p)
    {push(&s,p);
     p=p->lchild;
    }
  else{pop(&s,&p);
       if(!visit(p->data)) return error;
       p=p->rchild;
       }
 }
 return ok;
}

main()
{bitree t;
t=null;
t=creatree();
inorder(t);
getch();
}
哪位高手可以帮忙看看,到底哪错了啊,为什么总是遍历不成功啊
我在这里先谢谢了啊

回复列表 (共3个回复)

沙发

[quote]
inorder(bitree t)
{sqstack s;
 bitree p;
 initstack(&s);
 p=t;
 while(p||!stackempty(&s))
 {if(p)
    {push(&s,p);
     p=p->lchild;
    }
  else{pop(&s,&p);
       if(!visit(p->data)) return error;
       p=p->rchild;
       }
 }
 return ok;
}
[/quote]
我不知道你的initstack(&s);是怎么实现的,但是中序遍历的时候是先把根节点压入栈中,然后才有while循环的,你可以去找找非递归中序遍历的程序来对照一下。

板凳


我好像就是先把根节点压入栈里了啊

3 楼

void travlevel(bitree *t)                         /*层次遍历二叉树*/
{
    bitree *qu[maxsize];
    int front,rear;
    front=rear=0;
    if(t!=NULL)
        printf("%c",t->data);
    rear++;
    qu[rear]=t;
    while(rear!=front)
    {   front=(front+1)%maxsize;
        t=qu[front];
        if(t->lchild!=NULL)
        {   printf("%c",t->lchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=t->lchild;
        }
        if(t->rchild!=NULL)
        {   printf("%c",t->rchild->data);
            rear=(rear+1)%maxsize;
            qu[rear]=t->rchild;
        }
    }
    printf("\n");
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册