学步园

1.先序遍历非递归<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> #define maxsize 100<br /> typedef struct<br /> {<br /> Bitree Elem[maxsize];<br /> int top;<br /> }SqStack;<br /> void PreOrderUnrec(Bitree t)<br /> {<br /> SqStack s;<br /> StackInit(s);<br /> p=t;</p> <p> while (p!=null || !StackEmpty(s))<br /> {<br /> while (p!=null) //遍历左子树<br /> {<br /> visite(p->data);<br /> push(s,p);<br /> p=p->lchild;<br /> }//endwhile</p> <p> if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历<br /> {<br /> p=pop(s);<br /> p=p->rchild;<br /> }//endif</p> <p> }//endwhile </p> <p>}//PreOrderUnrec<br /> 2.中序遍历非递归算法<br /> #define maxsize 100<br /> typedef struct<br /> {<br /> Bitree Elem[maxsize];<br /> int top;<br /> }SqStack;<br /> void InOrderUnrec(Bitree t)<br /> {<br /> SqStack s;<br /> StackInit(s);<br /> p=t;<br /> while (p!=null || !StackEmpty(s))<br /> {<br /> while (p!=null) //遍历左子树<br /> {<br /> push(s,p);<br /> p=p->lchild;<br /> }//endwhile</p> <p> if (!StackEmpty(s))<br /> {<br /> p=pop(s);<br /> visite(p->data); //访问根结点<br /> p=p->rchild; //通过下一次循环实现右子树遍历<br /> }//endif </p> <p> }//endwhile<br /> }//InOrderUnrec</p> <p>3.后序遍历非递归算法<br /> #define maxsize 100<br /> typedef enum{L,R} tagtype;<br /> typedef struct<br /> {<br /> Bitree ptr;<br /> tagtype tag;<br /> }stacknode;<br /> typedef struct<br /> {<br /> stacknode Elem[maxsize];<br /> int top;<br /> }SqStack;<br /> void PostOrderUnrec(Bitree t)<br /> {<br /> SqStack s;<br /> stacknode x;<br /> StackInit(s);<br /> p=t;</p> <p> do<br /> {<br /> while (p!=null) //遍历左子树<br /> {<br /> x.ptr = p;<br /> x.tag = L; //标记为左子树<br /> push(s,x);<br /> p=p->lchild;<br /> }</p> <p> while (!StackEmpty(s) && s.Elem[s.top].tag==R)<br /> {<br /> x = pop(s);<br /> p = x.ptr;<br /> visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点<br /> }</p> <p> if (!StackEmpty(s))<br /> {<br /> s.Elem[s.top].tag =R; //遍历右子树<br /> p=s.Elem[s.top].ptr->rchild;<br /> }<br /> }while (!StackEmpty(s));<br /> }//PostOrderUnrec 

转自http://www.kaoyan365.com/Article/jisuanji/200601/20060104151407.html