正文描述:《先序遍历的非递归算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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
显示全部收起