二叉树先序遍历的非递归算法二叉树先序遍历的非递归算法
()
typedef char DataType;
typedef struct node{
DataType data;
struct node *lchild,*rchild;
}BinTNode;
typedef BinTNode *BinTree;
int count;
void CreateBinTree(BinTree *T);
void PreorderN(BinTree T);
#define StackSize 10 /*假定预分配的栈空间最多为1...
二叉树先序遍历的非递归算法
()
typedef char DataType;
typedef struct node{
DataType data;
struct node *lchild,*rchild;
}BinTNode;
typedef BinTNode *BinTree;
int count;
void CreateBinTree(BinTree *T);
void PreorderN(BinTree T);
#define StackSize 10 /*假定预分配的栈空间最多为10*/
typedef BinTree SDataType; /*栈的元素类型设为整型*/
#define Error printf
typedef struct{
SDataType data[StackSize];
int top;
}SeqStack;
void InitStack(SeqStack *S) /*初始栈*/
{
S->top=-1;
}
int StackEmpty(SeqStack *S) /*判栈空*/
{
return S->top==-1;
}
int StackFull(SeqStack *S) /*判栈满*/
{
return S->top==StackSize-1;
}
void Push(SeqStack *S, SDataType x) /*进栈*/
{
if(StackFull(S))
Error("栈已满\n"); /*上溢退出*/
else S->data[++S->top]=x; /*栈顶指针加1后将x进栈*/
}
SDataType Pop(SeqStack *S) /*出栈*/
{
if (StackEmpty(S))
Error("Stack underflow"); /*下溢退出*/
else return S->data[S->top--]; /*栈顶指针返回后将栈顶指针减1*/
}
SDataType StackTop(SeqStack *S) /*取栈顶元素*/
{
if (StackEmpty(S))
Error("栈已空\n");
return S->data[S->top];
}
main()
{
BinTree T;
char ch1,ch2;
printf("\n欢迎进入二叉树操作测试程序，请选择：\n");
ch1='y';
while(ch1=='y' || ch1=='Y')
{printf("\nA-------------------------二叉树建立");
printf("\nB-------------------------先序遍历(非递归)");
printf("\nC-------------------------退出\n");
scanf("\n%c",&ch2);
__page_break__
switch(ch2)
{case 'A':
case 'a':printf("按二叉树带空指针的先序次序输入结点:\n");
CreateBinTree(&T);
printf("二叉树建立成功\n");break;
case 'B':
case 'b':printf("遍历的结果为:\n");
PreorderN(T);break;
case 'C':
case 'c':ch1='n';break;
default:ch1='n';
}
}
}
void CreateBinTree(BinTree *T)
{
char ch;
scanf("\n%c",&ch);
if (ch=='0') *T=NULL;
else
{
*T=(BinTNode*)malloc(sizeof(BinTNode));
(*T)->data=ch;
CreateBinTree(&(*T)->lchild);
CreateBinTree(&(*T)->rchild);
}
}
void PreorderN(BinTree T)
{/*先序遍历二叉树T的非递归算法*/
SeqStack *S;
BinTree p;
InitStack(S);Push(S,T); /*根指针进栈*/
while(!StackEmpty(S))
{while(p=StackTop(S))
{ printf("%3c",p->data); /*访问入栈结点的数据域*/
Push(S,p->lchild); /*向左走到尽头*/
}
p=Pop(S); /*空指针退栈*/
if (!StackEmpty(S)) /*输出结点，向右一步*/
{p=Pop(S);
/* printf("%3c",p->data); */
Push(S,p->rchild);
}
}
}/*PreorderN */
本文档为【二叉树先序遍历的非递归算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483