二叉树的非递归遍历二叉树的非递归遍历
#include
#include
#include
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status;
typedef int TRlemType;
typedef struct BiTNode{
TRlemType data;
struct BiTNode *lchild,*r...
二叉树的非递归遍历
#include
#include
#include
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status;
typedef int TRlemType;
typedef struct BiTNode{
TRlemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType; typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S) {
SElemType *p;
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
p=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S) {
if(S.top==S.base )return 1;//是==,而不是=;
else return 0;
}
Status CreateBiTree(BiTree &T) {
char ch;
scanf("%c",&ch);
if(ch==' ')T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data =ch;
CreateBiTree(T->lchild );
CreateBiTree(T->rchild );
}
return OK;
}
Status InOrderTraverse(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);
printf(" %c",p->data);
p=p->rchild;
}
}
return OK;
}
int main()
{
BiTree T;
printf("请输入一个二叉树:\n");
CreateBiTree(T);
printf("按中序输入的二叉树为:\n");
InOrderTraverse(T);
printf("\n***************************牛逼的人。。。牛逼的程序*****************************\n");
return 0;
}
本文档为【二叉树的非递归遍历】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483