《先序遍历的非递归算法》由会员分享，可在线阅读，更多相关《先序遍历的非递归算法（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构1、先序遍历的非递归算法。用 c 语言写。 void PreOrderUnrec(Bitree t)SqStack s;StackInit(s);p=t;while (p!=null | !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 /PreOrderUnrec/#include stdio.h#includ
2、e stdlib.h#include string.h#define null 0struct node char data;struct node *lchild;struct node *rchild;/先序，中序 建树struct node *create(char *pre,char *ord,int n)struct node * head;int ordsit; head=null;if(ndata=*pre;head-lchild=head-rchild=null;ordsit=0;while(ordordsit!=*pre)ordsit+;head-lchild=create(
3、pre+1,ord,ordsit);head-rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);return head;/中序递归遍历void inorder(struct node *head)if(!head)return;elseinorder(head-lchild );printf(%c,head-data );inorder(head-rchild );/中序非递归遍历void inorder1(struct node *head) struct node *p;struct node *stack20;int top=0;p
4、=head;while(p|top!=0)while (p)stacktop+=p;p=p-lchild ;p=stack-top;printf(%c ,p-data );p=p-rchild ;/二叉树前序、中序、后序三种遍历的非递归算法1.先序遍历非递归算法void PreOrderUnrec(Bitree *t)Stack s;StackInit(s);Bitree *p=t;while (p!=NULL | !StackEmpty(s)while (p!=NULL) /遍历左子树visite(p-data);push(s,p);p=p-lchild; if (!StackEmpty(s
5、) /通过下一次循环中的内嵌 while 实现右子树遍历p=pop(s);p=p-rchild; /endif /endwhile 2.中序遍历非递归算法void InOrderUnrec(Bitree *t)Stack s;StackInit(s);Bitree *p=t;while (p!=NULL | !StackEmpty(s)while (p!=NULL) /遍历左子树push(s,p);p=p-lchild;if (!StackEmpty(s)p=pop(s);visite(p-data); /访问根结点p=p-rchild; /通过下一次循环实现右子树遍历/endif /endw
6、hile3.后序遍历非递归算法typedef enumL,R tagtype;typedef struct Bitree ptr;tagtype tag;stacknode;typedef structstacknode Elemmaxsize;int top;SqStack;void PostOrderUnrec(Bitree t)SqStack s;stacknode x;StackInit(s);p=t;do while (p!=null) /遍历左子树x.ptr = p; x.tag = L; /标记为左子树push(s,x);p=p-lchild;while (!StackEmpty
7、(s) & s.Elems.top.tag=R) x = pop(s);p = x.ptr;visite(p-data); /tag 为 R，表示右子树访问完毕，故访问根结点 if (!StackEmpty(s)s.Elems.top.tag =R; /遍历右子树p=s.Elems.top.ptr-rchild; while (!StackEmpty(s);/PostOrderUnrec 二。前序最简洁算法void PreOrderUnrec(Bitree *t)Bitree *p;Stack s;s.push(t);while (!s.IsEmpty()s.pop(p);visit(p-da
8、ta);if (p-rchild != NULL) s.push(p-rchild);if (p-lchild != NULL) s.push(p-lchild);三。后序算法之二void BT_PostOrderNoRec(pTreeT root) stack s; pTreeT pre=NULL;while (NULL != root) | !s.empty() if (NULL != root) s.push(root); root = root-left; else root = s.top(); if (root-right!=NULL & pre!=root-right) root=root-right; else root=pre=s.top(); visit(root); s.pop(); root=NULL;
