java非遞歸實(shí)現(xiàn)之二叉樹的前中后序遍歷詳解

更新時(shí)間：2021年09月16日 10:44:45 作者：小玄ｋｓ

樹的遍歷順序大體分為三種：前序遍歷（先根遍歷、先序遍歷），中序遍歷（中根遍歷），后序遍歷（后根遍歷），本文將給大家詳細(xì)的介紹，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值

二叉樹的前中后序遍歷

核心思想：用棧來(lái)實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的存儲(chǔ)。一邊遍歷，一邊將節(jié)點(diǎn)入棧，在需要時(shí)將節(jié)點(diǎn)從棧中取出來(lái)并遍歷該節(jié)點(diǎn)的左子樹或者右子樹，重復(fù)上述過(guò)程，當(dāng)棧為空時(shí)，遍歷完成。

前序遍歷

//非遞歸
//根 左 右
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //用數(shù)組來(lái)存儲(chǔ)前序遍歷結(jié)果
        List<Integer> list = new ArrayList<>();
        if(root==null)  return list;
        
        //創(chuàng)建一個(gè)棧
        Stack<TreeNode> st = new Stack<>();
        //cur指向根節(jié)點(diǎn)
        TreeNode cur = root;
        
        while(!st.isEmpty()||cur!=null){
        
            //一邊向左遍歷，一邊將遍歷到的節(jié)點(diǎn)入棧，節(jié)點(diǎn)值入數(shù)組
            while(cur!=null){
                list.add(cur.val);
                st.push(cur);	//根
                cur=cur.left;	//左
            }
            
            //指針指向棧頂節(jié)點(diǎn)（即上一個(gè)節(jié)點(diǎn)），并將棧頂節(jié)點(diǎn)出棧
            cur = st.pop();
            //指針指向該節(jié)點(diǎn)的右子樹，開始下一輪的遍歷
            cur = cur.right;	//右
        }
        return list;
    }
}

中序遍歷

//非遞歸
//左 根 右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        
      List<Integer> list = new ArrayList<>();
      if(root==null)    return list;
        
      Stack<TreeNode> st = new Stack<>();
       TreeNode cur = root;
      while(!st.isEmpty()||cur!=null){
      //一邊向左遍歷，一邊將遍歷到的節(jié)點(diǎn)入棧
          while(cur!=null){
              st.push(cur);
              cur = cur.left;	//左
          }
          cur = st.pop();
          //存儲(chǔ)遍歷結(jié)果
          list.add(cur.val);	//根
          cur = cur.right;		//右
      }
      return list;
    }
}

前序遍歷和中序遍歷的代碼基本相同，但是后序遍歷與它們不太一樣

后序遍歷

//非遞歸
//左 右 根
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     if(root==null) return list;
     TreeNode cur = root;
     
     //關(guān)鍵在于定義一個(gè)cur的前驅(qū)節(jié)點(diǎn)
     TreeNode pre = null;
     Stack<TreeNode> st = new Stack<>();
     while(cur!=null||!st.isEmpty()){
     
     	//一邊向左遍歷，一邊將遍歷到的節(jié)點(diǎn)入棧
         while(cur!=null){
             st.push(cur);
            cur = cur.left;
         }
         cur = st.pop();
         //若該節(jié)點(diǎn)的右節(jié)點(diǎn)為空，或者右節(jié)點(diǎn)被遍歷過(guò)，數(shù)組才能存儲(chǔ)該節(jié)點(diǎn)的數(shù)值（也就是我們最后才遍歷的根）
         if(cur.right==null||cur.right==pre){
             list.add(cur.val);
             pre = cur;
             cur=null;
         }else{//如果不滿足，說(shuō)明該節(jié)點(diǎn)的右節(jié)點(diǎn)還沒(méi)有被遍歷過(guò)，那么接著向右子節(jié)點(diǎn)遍歷
             st.push(cur);
             cur=cur.right;
         }
     }
     return list;
    }
}

到此這篇關(guān)于java非遞歸實(shí)現(xiàn)之二叉樹的前中后序遍歷詳解的文章就介紹到這了,更多相關(guān)Java 二叉樹遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: