先序遍历的非递归算法.doc

数据结构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#include 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(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; else inorder(head-lchild ); printf(%c,head-data ); inorder(head-rchild ); /中序非递归遍历void inorder1(struct node *head) struct node *p; struct node *stack20; int top=0; p=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) /通过下一次循环中的内嵌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 /endwhile3.后序遍历非递归算法typedef enumL,R tagtype;typedef struct Bitree ptr; tagtype tag;stacknode;typedef struct stacknode 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(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-data); 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 roo