include
#include
typedef int ElemType;
typedef int Status;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;
typedef BiTree pElemType;
typedef struct Snode
{
pElemType data;
struct Snode *next;
}Snode,*LinkStack;
Status CreateBiTree(BiTNode *T)
{
int ch;
scanf("%d",&ch);
if(ch==132) T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(0);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
void Init_StackL(LinkStack *S)
{
*S=NULL;
}
Status Push_L(LinkStack *S,pElemType x)
{
LinkStack p;
p=(LinkStack)malloc(sizeof(Snode));
p->data=x;
p->next=*S;
*S=p;
return 1;
}
Status Pop_L(LinkStack *S,pElemType *temp_)
{
LinkStack p;
pElemType temp;
if(*S==NULL) return 0;
temp=(*S)->data;
p=*S;
*S=p->next;
free(p);
*temp_=temp;
return 1;
}
Status StackEmpty(LinkStack *S)
{
if(*S==NULL) return 0;
else
return 1;
}
Status InOrderTraverse(BiTNode *T)
{
LinkStack S;
BiTNode *p;
p=T;
Init_StackL(&S);
while(p||StackEmpty(&S)){
if(p){Push_L(&S,p);p=p->lchild; printf("%d",p->data);
}
else{
Pop_L(&S,&p);
if(p->data) return 0;
p=p->rchild;
}
}
return 1;
}
void main()
{
BiTNode T;
CreateBiTree(&T);
InOrderTraverse(&T);
system("pause");
}
问题1:
你的CreateBiTree有问题,传一级指针是没有用的,根本没法改变指针的指向,操作的只是指针的拷贝
要传二级指针或者一级指针的引用才行
问题2:InOrderTraverse函数内p=p->lchild; printf("%d",p->data);这两句需要交换位置
不然如果p->lchild等于NULL了,你直接访问p->data会崩
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;
typedef BiTree pElemType;
typedef struct Snode
{
pElemType data;
struct Snode *next;
}Snode,*LinkStack;
Status CreateBiTree(BiTNode **T)
{
int ch;
scanf("%d",&ch);
if(ch==132) *T=NULL;
else{
if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))exit(0);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 1;
}
void Init_StackL(LinkStack *S)
{
*S=NULL;
}
Status Push_L(LinkStack *S,pElemType x)
{
LinkStack p;
p=(LinkStack)malloc(sizeof(Snode));
p->data=x;
p->next=*S;
*S=p;
return 1;
}
Status Pop_L(LinkStack *S,pElemType *temp_)
{
LinkStack p;
pElemType temp;
if(*S==NULL) return 0;
temp=(*S)->data;
p=*S;
*S=p->next;
free(p);
*temp_=temp;
return 1;
}
Status StackEmpty(LinkStack *S)
{
if(*S==NULL) return 0;
else
return 1;
}
Status InOrderTraverse(BiTNode *T)
{
LinkStack S;
BiTNode *p;
p=T;
Init_StackL(&S);
while(p||StackEmpty(&S)){
if(p){
Push_L(&S,p);
printf("%d",p->data);
p=p->lchild;
}
else{
Pop_L(&S,&p);
if(p->data) return 0;
p=p->rchild;
}
}
return 1;
}
void main()
{
BiTNode *T;
CreateBiTree(&T);
InOrderTraverse(T);
system("pause");
}