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"); */
}