先序遍历的非递归算法

ID:9811613

大小:41.50 KB

页数:6页

时间:2018-05-10

先序遍历的非递归算法_第1页
先序遍历的非递归算法_第2页
先序遍历的非递归算法_第3页
先序遍历的非递归算法_第4页
先序遍历的非递归算法_第5页
资源描述:

《先序遍历的非递归算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、121、先序遍历的非递归算法。用c语言写。voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null

2、

3、!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p->data);push(s,p);p=p->lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}//PreOrd

4、erUnrec/////////////////////////////////#include"stdio.h"#include"stdlib.h"#include"string.h"#definenull0structnode{chardata;structnode*lchild;structnode*rchild;};//先序,中序建树structnode*create(char*pre,char*ord,intn){structnode*head;intordsit;head=null;if(n<=0){returnnull

5、;}else{head=(structnode*)malloc(sizeof(structnode));head->data=*pre;head->lchild=head->rchild=null;ordsit=0;while(ord[ordsit]!=*pre){ordsit++;}head->lchild=create(pre+1,ord,ordsit);head->rchild=create(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);returnhead;}}//中序递归遍历voidinord

6、er(structnode*head){if(!head)return;else{inorder(head->lchild);printf("%c",head->data);inorder(head->rchild);}}//中序非递归遍历voidinorder1(structnode*head){structnode*p;structnode*stack[20];inttop=0;p=head;while(p

7、

8、top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];

9、printf("%c",p->data);p=p->rchild;}}///////////////////////////////////////////////////////////////////////////////////////二叉树前序、中序、后序三种遍历的非递归算法1.先序遍历非递归算法voidPreOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

10、

11、!StackEmpty(s)){while(p!=NULL)//遍历左子树{vis

12、ite(p->data);push(s,p);p=p->lchild;}if(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}2.中序遍历非递归算法voidInOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

13、

14、!StackEmpty(s)){while(p!=NULL)//遍历左子树{push(s,p);p=p->lchild;}if(

15、!StackEmpty(s)){p=pop(s);visite(p->data);//访问根结点p=p->rchild;//通过下一次循环实现右子树遍历}//endif}//endwhile}3.后序遍历非递归算法typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;voidPostOrderUnrec(Bitreet){SqStacks;st

16、acknodex;StackInit(s);p=t;do{while(p!=null)//遍历左子树{x.ptr=p;x.tag=L;//标记为左子树push(s,x);p=p->lchild;}while(!StackEmpty(s

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《先序遍历的非递归算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、121、先序遍历的非递归算法。用c语言写。voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null

2、

3、!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p->data);push(s,p);p=p->lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}//PreOrd

4、erUnrec/////////////////////////////////#include"stdio.h"#include"stdlib.h"#include"string.h"#definenull0structnode{chardata;structnode*lchild;structnode*rchild;};//先序,中序建树structnode*create(char*pre,char*ord,intn){structnode*head;intordsit;head=null;if(n<=0){returnnull

5、;}else{head=(structnode*)malloc(sizeof(structnode));head->data=*pre;head->lchild=head->rchild=null;ordsit=0;while(ord[ordsit]!=*pre){ordsit++;}head->lchild=create(pre+1,ord,ordsit);head->rchild=create(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);returnhead;}}//中序递归遍历voidinord

6、er(structnode*head){if(!head)return;else{inorder(head->lchild);printf("%c",head->data);inorder(head->rchild);}}//中序非递归遍历voidinorder1(structnode*head){structnode*p;structnode*stack[20];inttop=0;p=head;while(p

7、

8、top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];

9、printf("%c",p->data);p=p->rchild;}}///////////////////////////////////////////////////////////////////////////////////////二叉树前序、中序、后序三种遍历的非递归算法1.先序遍历非递归算法voidPreOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

10、

11、!StackEmpty(s)){while(p!=NULL)//遍历左子树{vis

12、ite(p->data);push(s,p);p=p->lchild;}if(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p->rchild;}//endif}//endwhile}2.中序遍历非递归算法voidInOrderUnrec(Bitree*t){Stacks;StackInit(s);Bitree*p=t;while(p!=NULL

13、

14、!StackEmpty(s)){while(p!=NULL)//遍历左子树{push(s,p);p=p->lchild;}if(

15、!StackEmpty(s)){p=pop(s);visite(p->data);//访问根结点p=p->rchild;//通过下一次循环实现右子树遍历}//endif}//endwhile}3.后序遍历非递归算法typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;voidPostOrderUnrec(Bitreet){SqStacks;st

16、acknodex;StackInit(s);p=t;do{while(p!=null)//遍历左子树{x.ptr=p;x.tag=L;//标记为左子树push(s,x);p=p->lchild;}while(!StackEmpty(s

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭