| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 715 人关注过本帖
标题:真心求教,刚刚自己写了个二叉树中序遍历非递归的算法,但总是显示栈满!!!现 ...
只看楼主 加入收藏
笑傲
Rank: 8Rank: 8
来 自:迪拜
等 级:蝙蝠侠
威 望:5
帖 子:223
专家分:856
注 册:2013-3-9
结帖率:100%
收藏
 问题点数:0 回复次数:2 
真心求教,刚刚自己写了个二叉树中序遍历非递归的算法,但总是显示栈满!!!现在实在是不知道错在哪了?
#include<stdio.h>
#include<stdlib.h>

#define max_size 100
#define overflow -1
typedef char datatype;

typedef struct node
{
    struct node *lchild,*rchild;
     datatype data;
}ptree;

typedef struct
{
    int top,base;
     struct node *data[max_size];
}stack1;

stack1 s;

ptree *create()
{
  int front=1,rear=0;
  ptree *root=NULL,*s,*queue[max_size];
  char ch;
  ch=getchar();
  while(ch!='#')
  {
     s=NULL;
     if(ch!='@')
     {
         if(!(s=(ptree *)malloc(sizeof(ptree))))
             exit(0);
         s->lchild=NULL;
         s->rchild=NULL;
         s->data=ch;
     }
     rear++;
     queue[rear]=s;
     if(rear==1)   root=s;
     else
         if(s&&queue[front])
            if(rear%2==0)   queue[front]->lchild=s;
             if(rear%2==1)
                 queue[front++]->lchild=s;   
             ch=getchar();
  }
  fflush(stdin);
  return root;
}

void initstack()                             //初始化栈:
{
    s.top=s.base=0;
}

void Enstack(ptree *k)                       //进栈函数;
{
    if((s.top-s.base)>=max_size)            //判断是否栈已满:
    {
        printf("栈已满!\n");
        exit(0);
    }
  s.data[s.top++]=k;                            //未满就将此节点的地址入栈;
}

ptree *Destack()
{
    if(s.top<=0)
    {
        printf("栈空!\n");
        exit(0);
    }
    s.top--;
    printf("%c ",s.data[s.top+1]);
    return s.data[s.top+1];
}

void inorder(ptree *k)                  //非递归遍历,
{
   if(k==NULL)                          //假如根结点为空,则为一棵空树:
   {
       printf("树为空!\n");
       exit(0);
   }
   initstack();                             //栈初始化;  
   while(1)
   {
       if(k)                                       //当结点不为空时,进行以下操作;
       {
           if(k->lchild)                          //假如左孩子存在,
           {
               Enstack(k);                        //将父节点入栈
               k=k->lchild;
           }
           else if(k->rchild)
           {
               Enstack(k);                            //将此指针指向的地址入栈;
               k=k->rchild;
           }
           else
           {
               printf("%c ",k->data);                        
               k=Destack()->rchild;                       //出栈并返回一个地址;
           }

       }
   }
}

int main()
{
    ptree *k;
    printf("请输入元素创建二叉树(@表示虚节点,#表示结束符):\n");
    k=create();
    printf("中序遍历结果为:\n");
    inorder(k);
    free(k);
    return 0;
}
inorder()函数中栈初始化时,top为0;当进栈时每次top就变为了100
搜索更多相关主题的帖子: 真心 include create 二叉树 
2013-04-10 16:17
笑傲
Rank: 8Rank: 8
来 自:迪拜
等 级:蝙蝠侠
威 望:5
帖 子:223
专家分:856
注 册:2013-3-9
收藏
得分:0 
由于是我自己想的算法,所以有可能算法也是错的,我只是希望知道我错在哪了!
希望知道的回答一下,谢谢!

练就一身本领,只为笑傲江湖!
2013-04-10 16:26
笑傲
Rank: 8Rank: 8
来 自:迪拜
等 级:蝙蝠侠
威 望:5
帖 子:223
专家分:856
注 册:2013-3-9
收藏
得分:0 
我自己已经想出来了;

练就一身本领,只为笑傲江湖!
2013-04-11 17:30
快速回复:真心求教,刚刚自己写了个二叉树中序遍历非递归的算法,但总是显示栈满 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016941 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved