二叉樹(shù)的非遞歸遍歷

1、前序遍歷的非遞歸實(shí)現(xiàn)

為了便于理解，這里以下圖的二叉樹(shù)為例，分析二叉樹(shù)的三種遍歷方式的實(shí)現(xiàn)過(guò)程。

根據(jù)先序遍歷的順序，先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，后訪問(wèn)右子樹(shù)，而對(duì)于每個(gè)子樹(shù)來(lái)說(shuō)，又按照同樣的訪問(wèn)順序進(jìn)行遍歷，上圖的先序遍歷順序?yàn)椋篈BDECF。非遞歸的實(shí)現(xiàn)思路如下：

對(duì)于任一節(jié)點(diǎn)Node，

  1. 輸出節(jié)點(diǎn)Node，然后將其入棧，再看Node的左孩子是否為空；
  2. 若Node的左孩子不為空，則置Node的左孩子為當(dāng)前節(jié)點(diǎn)，重復(fù)的操作；
  3. 若Node的左孩子為空，則將棧頂節(jié)點(diǎn)出棧，但不輸出，并將出棧節(jié)點(diǎn)的右孩子置為當(dāng)前節(jié)點(diǎn)，看其是否為空；
  4. 若不為空，則循環(huán)至1操作；
  5. 如果為空，則繼續(xù)出棧，但不輸出，同時(shí)將出棧節(jié)點(diǎn)的右孩子置為當(dāng)前節(jié)點(diǎn)，看其是否為空，重復(fù)3和5操作；
  6. 直到當(dāng)前節(jié)點(diǎn)P為NULL并且棧空，遍歷結(jié)束。

下面以上圖為例詳細(xì)分析其先序遍歷的非遞歸實(shí)現(xiàn)過(guò)程：

首先，從根節(jié)點(diǎn)A開(kāi)始，根據(jù)操作1，輸出A，并將其入棧，由于A的左孩子不為空，根據(jù)操作2，將B置為當(dāng)前節(jié)點(diǎn)，再根據(jù)操作1，將B輸出，并將其入棧，由于B的左孩子也不為空，根據(jù)操作2，將D置為當(dāng)前節(jié)點(diǎn)，再根據(jù)操作1，輸出D，并將其入棧，此時(shí)輸出序列為ABD；

由于D的左孩子為空，根據(jù)操作3，將棧頂節(jié)點(diǎn)D出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

由于D的右孩子為空，根據(jù)操作5，繼續(xù)將棧頂節(jié)點(diǎn)B出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

由于B的右孩子E不為空，根據(jù)操作1，輸出E，并將其入棧，此時(shí)輸出序列為：ABDE；

由于E的左孩子為空，根據(jù)操作3，將棧頂節(jié)點(diǎn)E出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

由于E的右孩子為空，根據(jù)操作5，繼續(xù)將棧頂節(jié)點(diǎn)A出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

由于A的右孩子C不為空，根據(jù)操作1，輸出C，并將其入棧，此時(shí)輸出序列為：ABDEC；

由于A的左孩子F不為空，根據(jù)操作2，則將F置為當(dāng)前節(jié)點(diǎn)，再根據(jù)操作1，輸出F，并將其入棧，此時(shí)輸出序列為：ABDECF；

由于F的左孩子為空，根據(jù)操作3，將棧頂節(jié)點(diǎn)F出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

由于F的右孩子為空，根據(jù)操作5，繼續(xù)將棧頂元素C出棧，但不輸出，并將其右孩子置為當(dāng)前節(jié)點(diǎn)；

此時(shí)?？眨褻的右孩子為NULL，因此遍歷結(jié)束。

//根據(jù)以上思路，前序遍歷的非遞歸實(shí)現(xiàn)代碼如下：
  void pre_traverse(BTree pTree)  
  {  
      PSTACK stack = create_stack();  //創(chuàng)建一個(gè)空棧  
      BTree node_pop;                 //用來(lái)保存出棧節(jié)點(diǎn)
      BTree pCur = pTree;             //定義用來(lái)指向當(dāng)前訪問(wèn)的節(jié)點(diǎn)的指針  
    
      //直到當(dāng)前節(jié)點(diǎn)pCur為NULL且?？諘r(shí)，循環(huán)結(jié)束  
      while(pCur || !is_empty(stack))  
      {  
         //從根節(jié)點(diǎn)開(kāi)始，輸出當(dāng)前節(jié)點(diǎn)，并將其入棧，  
         //同時(shí)置其左孩子為當(dāng)前節(jié)點(diǎn)，直至其沒(méi)有左孩子，及當(dāng)前節(jié)點(diǎn)為NULL  
         printf("%c ", pCur->data);  
         push_stack(stack,pCur);  
         pCur = pCur->pLchild;  
         //如果當(dāng)前節(jié)點(diǎn)pCur為NULL且棧不空，則將棧頂節(jié)點(diǎn)出棧，  
         //同時(shí)置其右孩子為當(dāng)前節(jié)點(diǎn),循環(huán)判斷，直至pCur不為空  
         while(!pCur && !is_empty(stack))  
         {  
             pCur = getTop(stack);  
             pop_stack(stack,&node_pop);  
             pCur = pCur->pRchild;              
         }  
     }  
 }

2、中序遍歷的非遞歸實(shí)現(xiàn)

根據(jù)中序遍歷的順序，先訪問(wèn)左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，后訪問(wèn)右子樹(shù)，而對(duì)于每個(gè)子樹(shù)來(lái)說(shuō)，又按照同樣的訪問(wèn)順序進(jìn)行遍歷，上圖的中序遍歷順序?yàn)椋篋BEAFC。非遞歸的實(shí)現(xiàn)思路如下

對(duì)于任一節(jié)點(diǎn)P，

1.若P的左孩子不為空，則將P入棧并將P的左孩子置為當(dāng)前節(jié)點(diǎn)，然后再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行相同的處理；
2.若P的左孩子為空，則輸出P節(jié)點(diǎn)，而后將P的右孩子置為當(dāng)前節(jié)點(diǎn)，看其是否為空；
3.若不為空，則重復(fù) 1 和 2 的操作；
4.若為空，則執(zhí)行出棧操作，輸出棧頂節(jié)點(diǎn)，并將出棧的節(jié)點(diǎn)的右孩子置為當(dāng)前節(jié)點(diǎn)，看起是否為空，重復(fù) 3 和 4 的操作；
5.直到當(dāng)前節(jié)點(diǎn)P為NULL并且棧為空，則遍歷結(jié)束。

下面以上圖為例詳細(xì)分析其中序遍歷的非遞歸實(shí)現(xiàn)過(guò)程：

首先，從根節(jié)點(diǎn)A開(kāi)始，A的左孩子不為空，根據(jù)操作1將A入棧，接著將B置為當(dāng)前節(jié)點(diǎn)，B的左孩子也不為空，根據(jù)操作1，將B也入棧，接著將D置為當(dāng)前節(jié)點(diǎn)，由于D的左子樹(shù)為空，根據(jù)操作2，輸出D；

由于D的右孩子也為空，根據(jù)操作4，執(zhí)行出棧操作，將棧頂結(jié)點(diǎn)B出棧，并將B置為當(dāng)前節(jié)點(diǎn)，此時(shí)輸出序列為DB；

由于B的右孩子不為空，根據(jù)操作3，將其右孩子E置為當(dāng)前節(jié)點(diǎn)，由于E的左孩子為空，根據(jù)操作1，輸出E，此時(shí)輸出序列為DBE；

由于E的右孩子為空，根據(jù)操作4，執(zhí)行出棧操作，將棧頂節(jié)點(diǎn)A出棧，并將節(jié)點(diǎn)A置為當(dāng)前節(jié)點(diǎn)，此時(shí)輸出序列為DBEA；

此時(shí)棧為空，但當(dāng)前節(jié)點(diǎn)A的右孩子并不為NULL，繼續(xù)執(zhí)行，由于A的右孩子不為空，根據(jù)操作3，將其右孩子C置為當(dāng)前節(jié)點(diǎn)，由于C的左孩子不為空，根據(jù)操作1，將C入棧，將其左孩子F置為當(dāng)前節(jié)點(diǎn)，由于F的左孩子為空，根據(jù)操作2，輸出F，此時(shí)輸出序列為：DBEAF；

由于F的右孩子也為空，根據(jù)操作4，執(zhí)行出棧操作，將棧頂元素C出棧，并將其置為當(dāng)前節(jié)點(diǎn)，此時(shí)的輸出序列為：DBEAFC；

由于C的右孩子為NULL，且此時(shí)?？?，根據(jù)操作5，遍歷結(jié)束。

根據(jù)以上思路，中序遍歷的非遞歸實(shí)現(xiàn)代碼如下：

void in_traverse(BTree pTree)
{
    PSTACK stack = create_stack();  //創(chuàng)建一個(gè)空棧
    BTree node_pop;                 //用來(lái)保存出棧節(jié)點(diǎn)
    BTree pCur = pTree;             //定義指向當(dāng)前訪問(wèn)的節(jié)點(diǎn)的指針
 
    //直到當(dāng)前節(jié)點(diǎn)pCur為NULL且棧空時(shí)，循環(huán)結(jié)束
    while(pCur || !is_empty(stack))
    {
        if(pCur->pLchild)
        {
            //如果pCur的左孩子不為空，則將其入棧，并置其左孩子為當(dāng)前節(jié)點(diǎn)
            push_stack(stack,pCur);
            pCur = pCur->pLchild;
        }
        else
        {
            //如果pCur的左孩子為空，則輸出pCur節(jié)點(diǎn)，并將其右孩子設(shè)為當(dāng)前節(jié)點(diǎn)，看其是否為空
            printf("%c ", pCur->data);
            pCur = pCur->pRchild;
            //如果為空，且棧不空，則將棧頂節(jié)點(diǎn)出棧，并輸出該節(jié)點(diǎn)，
            //同時(shí)將它的右孩子設(shè)為當(dāng)前節(jié)點(diǎn)，繼續(xù)判斷，直到當(dāng)前節(jié)點(diǎn)不為空
            while(!pCur && !is_empty(stack))
            {
                pCur = getTop(stack);
                printf("%c ",pCur->data);   
                pop_stack(stack,&node_pop);
                pCur = pCur->pRchild;
            }
        }
    }
}

3、后序遍歷的非遞歸實(shí)現(xiàn)

根據(jù)后序遍歷的順序，先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，后訪問(wèn)根節(jié)點(diǎn)，而對(duì)于每個(gè)子樹(shù)來(lái)說(shuō)，又按照同樣的訪問(wèn)順序進(jìn)行遍歷，上圖的后序遍歷順序?yàn)椋篋EBFCA。后序遍歷的非遞歸的實(shí)現(xiàn)相對(duì)來(lái)說(shuō)要難一些，要保證根節(jié)點(diǎn)在左子樹(shù)和右子樹(shù)被訪問(wèn)后才能訪問(wèn)，思路如下：

對(duì)于任一節(jié)點(diǎn)P，

1.先將節(jié)點(diǎn)P入棧；
2.若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已經(jīng)被輸出，則可以直接輸出節(jié)點(diǎn)P，并將其出棧，將出棧節(jié)點(diǎn)P標(biāo)記為上一個(gè)輸出的節(jié)點(diǎn)，再將此時(shí)的棧頂結(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)；
3.若不滿足2中的條件，則將P的右孩子和左孩子依次入棧，當(dāng)前節(jié)點(diǎn)重新置為棧頂結(jié)點(diǎn)，之后重復(fù)操作2；
4.直到?？?，遍歷結(jié)束。

下面以上圖為例詳細(xì)分析其后序遍歷的非遞歸實(shí)現(xiàn)過(guò)程：

首先，設(shè)置兩個(gè)指針：Cur指針指向當(dāng)前訪問(wèn)的節(jié)點(diǎn)，它一直指向棧頂節(jié)點(diǎn)，每次出棧一個(gè)節(jié)點(diǎn)后，將其重新置為棧頂結(jié)點(diǎn)，Pre節(jié)點(diǎn)指向上一個(gè)訪問(wèn)的節(jié)點(diǎn)；

Cur首先指向根節(jié)點(diǎn)A，Pre先設(shè)為NULL，由于A存在左孩子和右孩子，根據(jù)操作3，先將右孩子C入棧，再將左孩子B入棧，Cur改為指向棧頂結(jié)點(diǎn)B；

由于B的也有左孩子和右孩子，根據(jù)操作3，將E、D依次入棧，Cur改為指向棧頂結(jié)點(diǎn)D；

由于D沒(méi)有左孩子，也沒(méi)有右孩子，根據(jù)操作2，直接輸出D，并將其出棧，將Pre指向D，Cur指向棧頂結(jié)點(diǎn)E，此時(shí)輸出序列為：D；

由于E也沒(méi)有左右孩子，根據(jù)操作2，輸出E，并將其出棧，將Pre指向E，Cur指向棧頂結(jié)點(diǎn)B，此時(shí)輸出序列為：DE；

由于B的左右孩子已經(jīng)被輸出，即滿足條件Pre==Cur->lchild或Pre==Cur->rchild，根據(jù)操作2，輸出B，并將其出棧，將Pre指向B，Cur指向棧頂結(jié)點(diǎn)C，此時(shí)輸出序列為：DEB；

由于C有左孩子，根據(jù)操作3，將其入棧，Cur指向棧頂節(jié)點(diǎn)F；

由于F沒(méi)有左右孩子，根據(jù)操作2，輸出F，并將其出棧，將Pre指向F，Cur指向棧頂結(jié)點(diǎn)C，此時(shí)輸出序列為：DEBF；

由于C的左孩子已經(jīng)被輸出，即滿足Pre==Cur->lchild，根據(jù)操作2，輸出C，并將其出棧，將Pre指向C，Cur指向棧頂結(jié)點(diǎn)A，此時(shí)輸出序列為：DEBFC；

由于A的左右孩子已經(jīng)被輸出，根據(jù)操作2，輸出A，并將其出棧，此時(shí)輸出序列為：DEBFCA；

此時(shí)?？?，遍歷結(jié)束。

根據(jù)以上思路，后序遍歷的非遞歸實(shí)現(xiàn)代碼如下：

void beh_traverse(BTree pTree)
{
    PSTACK stack = create_stack();  //創(chuàng)建一個(gè)空棧
    BTree node_pop;          //用來(lái)保存出棧的節(jié)點(diǎn)
    BTree pCur;              //定義指針，指向當(dāng)前節(jié)點(diǎn)
    BTree pPre = NULL;       //定義指針，指向上一各訪問(wèn)的節(jié)點(diǎn)
 
    //先將樹(shù)的根節(jié)點(diǎn)入棧
    push_stack(stack,pTree);  
    //直到?？諘r(shí)，結(jié)束循環(huán)
    while(!is_empty(stack))
    {
        pCur = getTop(stack);   //當(dāng)前節(jié)點(diǎn)置為棧頂節(jié)點(diǎn)
        if((pCur->pLchild==NULL && pCur->pRchild==NULL) || 
            (pPre!=NULL && (pCur->pLchild==pPre || pCur->pRchild==pPre)))
        {
            //如果當(dāng)前節(jié)點(diǎn)沒(méi)有左右孩子，或者有左孩子或有孩子，但已經(jīng)被訪問(wèn)輸出，
            //則直接輸出該節(jié)點(diǎn)，將其出棧，將其設(shè)為上一個(gè)訪問(wèn)的節(jié)點(diǎn)
            printf("%c ", pCur->data);
            pop_stack(stack,&node_pop);
            pPre = pCur;
        }
        else
        {
            //如果不滿足上面兩種情況,則將其右孩子左孩子依次入棧
            if(pCur->pRchild != NULL)
                push_stack(stack,pCur->pRchild);
            if(pCur->pLchild != NULL)
                push_stack(stack,pCur->pLchild);
        }
    }
}

/**
     * 統(tǒng)一一下
     * @param root
     * @return
     */
    //前序
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
                TreeNode cur = stack.pop();
                list.add(Integer.valueOf(cur.val));
                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
        }

        return list;
    }

    //中序
   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }


    //后序遍歷，非遞歸 , 前序遍歷逆向
    public List<Integer> postorderTraversal(TreeNode root) {
       if(root==null)  return new ArrayList<Integer>();

        // 存儲(chǔ)："根右左"的遍歷順序
        Stack<Integer> reverseRes = new Stack<Integer>();

        Stack<TreeNode> s = new Stack<TreeNode>();//輔助棧，保存待遍歷的節(jié)點(diǎn)
        s.add(root);

        while (!s.isEmpty()) {
            TreeNode tem = s.pop();
            reverseRes.push(tem.val);//存儲(chǔ):"根右左"的遍歷順序,先入"根"節(jié)點(diǎn)

         // “右左”的遍歷順序，所以在棧(LIFO)中對(duì)應(yīng)的就是：先進(jìn)"左"，再進(jìn)"右"
            if (tem.left != null)
                s.push(tem.left);
            if (tem.right != null)
                s.push(tem.right);
        }

        ArrayList<Integer> res = new ArrayList<Integer>();//獲得“根左右”的遍歷序列
        while (!s.isEmpty()) {
            res.add(reverseRes.pop());
        }
        return res;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容