二叉樹前序遍歷的非遞歸算法

2020-01-26 15:35:25

字體：大中小

來源：轉載

供稿：網友

二叉樹的前序遍歷是先根節點，然后如果有左子樹則再先序遍歷左子樹，然后如果有右子樹則再先序遍歷其又子樹。
遞歸算法如下

 void   preorder(Betree *t)
{   if(t==null) return;visit(t);//訪問該節點preorder(t->lchild);preorder(t->rchild); }

當然遞歸算法是隱式使用了棧。我們仔細分析這個過程，先是取出了根節點進行了訪問，然后我們把根節點退棧，退棧后必然有節點進棧，怎么辦呢？根節點只能直接訪問到rchild和lchild，如果是左子樹的根節點進了棧，那么必然是后訪問之，所以必然是rchild先進棧，lchild后進棧。可以畫圖加深理解。
那么現在寫出先序遍歷二叉樹的算法。

復制代碼代碼如下:

void preorder(Betree *t)
{ //算法中我們使用一維數組來模擬一個順序棧
     if(t==null) return;//為空樹的話完全沒有必要進行下面的操作     
     Betree *stack[max];
     top=1;stack[top]=t;//根節點入棧
     while(top>0)
    {   nd=stack[top];//取出根節點  top=top-1;//退棧   visit(nd->data); //訪問根節點 if(nd->rchild!=null) { top=top+1;stack[top]=nd->rchild;} //根節點有右子樹，將其進棧，等到左子樹訪問完后再訪問之
if(nd->lchild!=null) { top=top+1;stack[top]=nd->lchild;}
   }
}