后序遍历二叉树用栈--gdb调试错误

软件和网站开发以及相关技术探讨
回复
been!!!
帖子: 16
注册时间: 2013-07-28 21:19
系统: Ubuntu 13.04

后序遍历二叉树用栈--gdb调试错误

#1

帖子 been!!! » 2014-04-01 22:09

我参照别人的代码,写了一个二叉树的后序遍历算法。思路是
1.Push根结点到第一个栈s中。
2.从第一个栈s中Pop出一个结点,并将其Push到第二个栈output中。
3.然后Push结点的左孩子和右孩子到第一个栈s中。
重复过程2和3直到栈s为空。
4.访问栈k的元素

gdb错误提示如下
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400fa3 in PostOrder_stack (T=0x603010) at Bitree.cpp:221
221 push(s,p->lch);


代码: 全选

void PostOrder_stack(BiTree T)
{
  sqstack s,k;
  Initstack(s);
  Initstack(k);
  BiTree p=T;
  BiTree r;
  push(s,p);
  while(!StackEmpty(s))
    {
      Gettop(s,r);
 pop(s,p);
      push(k,p);
      if(p->lch);
      push(s,p->lch);
      if(p->rch)
	push(s,p->rch);
    }
  while(!StackEmpty(k))
    {
      pop(k,p);
      printf("%c",p->data);
    }
}
下面是整个源代码以及一些基本的信息
Bitree.cpp
GDB 7.6.1-ubuntu
gcc编译没有问题

代码: 全选

#include<stdio.h>
#include<malloc.h>
#include<iostream>
 
//定义节点
 struct BiNode{

      char data;

      struct BiNode *lch;

      struct BiNode *rch;

}BiNode;
  typedef struct BiNode *BiTree;
 
  struct PMT{
      struct BiNode *ptr;
      int mark;
  };
typedef struct PMT PMType;

//先序拓展序列建立二叉树
void Create(BiTree &T)
{
/*   定义函数参数为Bitree指针类型,并取其地址 */


/*     malloc函数分配一个空间,使指针T指向这个空间 */
       

    char ch;

      printf("Enter the data \n");

      scanf(" %c",&ch);

      if(ch=='#') T = NULL;

      else{
	    T = (BiTree) malloc (sizeof(BiNode));

	    T->data=ch;
              Create(T->lch);

              Create(T->rch);

      }

}
 




//三种递归遍历二叉树函数
//先序遍历 (递归)/*{{{*/
void Preorder (BiTree T)
{                   

 if (T) {

    printf(" %c",T->data);             // 访问根结点

     

    Preorder(T->lch); // 遍历左子树

    Preorder(T->rch);// 遍历右子树

 }

}
 
//中序遍历 (递归)
void Inorder (BiTree T)
{

   if(T) {

     Inorder(T->lch);

      

     printf(" %c",T->data);

      

     Inorder(T->rch);   

       }
}
 
//后序遍历 (递归)
void Postorder (BiTree T)
{

   if(T) {

     Postorder(T->lch);

     Postorder(T->rch);

      

     printf(" %c",T->data);

     }
}/*}}}*/

//递归判断二叉树是否相似
int Sim_Bitree(BiTree b1,BiTree b2)
{
  if(!b1&&!b2)
    return 1;
  else
    if(b1&&b2&&Sim_Bitree(b1->lch,b2->lch)&&Sim_Bitree(b1->rch,b2->rch))
      return 1;
    else return 0;
}
 
//二叉树定义的堆栈结构
struct sqstack{
   BiTree *top;
    BiTree *base;
   int stacksize;
};
void Initstack(sqstack &S)
{
  S.base=(BiTree *)malloc(500*sizeof(BiTree));
  S.top=S.base;
  S.stacksize=500;
}
void Destorystack(sqstack &S)
{
  free(S.base);
  S.top=S.base=NULL;
  S.stacksize=0;
}
int Gettop(sqstack S,BiTree &e)
{
  if(S.top>S.base)
    {
      e=*(S.top-1);
      return 1;
    }
  else return 0;
}
void Clearstack(sqstack &S)
{
  S.top=S.base;
}
int StackEmpty(sqstack s)
{
  if(s.top==s.base)
    return 1;
  else return 0;
}
void push(sqstack &S,BiTree e)
{
  if(S.top-S.base==S.stacksize)
    {
      S.base=(BiTree *)realloc(S.base,(S.stacksize+5)*sizeof(BiTree));
      S.top=S.base+S.stacksize;
      S.stacksize+=5;
    }
  *S.top=e;
  S.top++;
}
int pop(sqstack &S,BiTree &e)
{
  if(S.top==S.base)
    return 0;
  e=*--S.top;
  return 1;
}


//先序遍历栈
void Preorder_nonrecurise(BiTree T)
{
  BiTree p=T;
  sqstack S;
  Initstack(S);
  push(S,T);
  while(StackEmpty(S))
    {
      while(Gettop(S,p)&&p)
	{
	  printf("%c",p->data);
	  push(S,p->lch);
	}
      pop(S,p);
      if(StackEmpty(S))
	{
	  pop(S,p);
	  push(S,p->rch);
	}
    }
}

//后续遍历用堆栈
void PostOrder_stack(BiTree T)
{//gdb还是提示有错误,问题不知道是出在那里,提示问题出在push函数但是
  // 我把这个函数注析到,问题就没有出现,那问题就不出现在定义的push函数中
  //   ,应该出现在调用这个push上面来--3.30
  //    把出栈和进栈的位置调转一下,错误提示出现在下面一个push
  //    中,难道p->lch有问题吗?
  sqstack s,k;
  Initstack(s);
  Initstack(k);
  BiTree p=T;
  BiTree r;
  push(s,p);
  while(!StackEmpty(s))
    {
      Gettop(s,r);
 pop(s,p);
      push(k,p);
      if(p->lch);
      push(s,p->lch);
      if(p->rch)
	push(s,p->rch);
    }
  while(!StackEmpty(k))
    {
      pop(k,p);
      printf("%c",p->data);
    }
}
int main()
{

  //建树
   printf("The fuction Create() is called.\n");

   BiTree T1;

   printf("creat the first tree:");
   Create(T1);
   Preorder(T1);
    PostOrder_stack(T1);
//   printf("creat the second tree:");
//   Create(T2);
//    
//    Preorder_nonrecurise(T1);
//
//   //三种遍历递归算法
//
//   printf("\n");   
//
//   printf("The fuction Preorder() is called.\n");
//
//   Preorder(T);
//
//
//
//   printf("\n");
//
//   printf("The fuction Inorder() is called.\n");
//
//   Inorder(T);
//
//
//
//   printf("\n");
//
//   printf("The fuction Postorder() is called.\n");
//
//  Postorder(T);
//
//


  printf("\n");

/*   system("pause"); */

 

}
been!!!
帖子: 16
注册时间: 2013-07-28 21:19
系统: Ubuntu 13.04

Re: 后序遍历二叉树用栈--gdb调试错误

#2

帖子 been!!! » 2014-04-01 22:20

我测试的数据是abd##e##c##
用gdb调试,当push(s.p),s.top-s.base=8,也就是说“a“进栈之后s.top自曾到8,( sizeof(BiTree)=8),但后面进栈”b","c",S.top 只是自曾了2.真的不明白了

不知道是栈还是二叉树的定义出了错误?
been!!!
帖子: 16
注册时间: 2013-07-28 21:19
系统: Ubuntu 13.04

Re: 后序遍历二叉树用栈--gdb调试错误

#3

帖子 been!!! » 2014-04-07 15:34

在stack overflow上发了帖!原来是这里出了问题!难怪遇到空指针都一直进栈

代码: 全选

if(p->lch);
ps:那时还不确定是栈的操作有问题还是创建二叉树有问题!现在终于搞明白了
回复