🧑‍💻JavaScript算法與數據結構-HowieCong

務必要熟悉JavaScript使用再來學！

一、遍歷的方式

• 按照順序規則的不同，遍歷方式有如下四種：

  • 先序遍歷
  • 中序遍歷
  • 後序遍歷
  • 層次遍歷

• 按照實現方式的不同，遍歷方式又可以分為以下兩種：

  • 遞歸遍歷（先，中，後序遍歷）
  • 迭代遍歷（層次遍歷）

二、遞歸遍歷

編程語言中，函數Func(Type a,......)直接或間接調用函數本身，則該函數稱為遞歸函數

簡單來説，當我們看到一個函數反覆調用它自己的時候，遞歸就發生了。遞歸 => 反覆

• 遞歸式的定義：

  • 可以沒有根結點，作為一顆空樹存在
  • 如果不是空樹，那必須由根節點、左子樹和右子樹組成，且左右子樹都是二叉樹
  • 反覆地執行“創建一個由數據域、左右子樹組成地結點”這個動作，直到數據被分配完為止

  

• Eg：在保證“左子樹一定先於右子樹遍歷”，那麼遍歷的情況就這三種

  • 根結點 => 左子樹 => 右子樹
  • 左子樹 => 根結點 => 右子樹
  • 左子樹 => 右子樹 => 根結點

這三種情況，分別對應二叉樹的先序遍歷，中序遍歷和後序遍歷

根結點的遍歷分別被安排在了首要位置，中間位置和後序遍歷

所謂的先序、中序和後序，其實就是根結點的遍歷時機

三、遍歷

（1）先序遍歷

• 遍歷路線如數字所示：

• 如果有N多個子樹，那麼我們在每一棵樹內部，都要重複這個旅行路線：

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val："D"，
        }，
        right：{
            val: "E"
        }
    },
    right:{
        val:"C",
        right:{
            val:"F"
        }
    }    
};       

遞歸函數的編寫要點：

• 遞歸式：每一次重複的內容是什麼，這裏要做先序遍歷，那麼每次重複的是就是根結點 -> 左子樹 -> 右子樹 這個路線
• 遞歸邊界：什麼時候停下來，在遍歷的場景下，當我們發現遍歷的目標樹為空的時候，就意味着旅途已經達到終點了，在編碼實現裏對應着一個return語句

• 第一個遞歸遍歷函數（先序遍歷）

// 所有遍歷函數的入參都是樹的根結點對象
function preorder(root){
    if(!root){
        return
    }
    
    // 輸出當前遍歷的結點值
    console.log('當前遍歷的結點值為：'，root.val)
    
    // 遞歸遍歷左子樹
    preorder(root.left)
    
    // 遞歸遍歷右子樹
    preorder(root.right)
}

• 圖解先序遍歷過程

  1. 調用preorder(root),這裏root就是A，它非空，所以進入遞歸式，輸出A值，接着優先遍歷左子樹preorder(root.left)；此事為preorder(B)

  

  2. 進入preorder(B):入參為結點B，非空，進入遞歸式，輸出B值。接着優先遍歷B的左子樹，preorder(root.left),此時為preorder(D):

  

  3. 進入preorder(D)：入參為結點D，非空，進入遞歸式，輸出D值，接着優先遍歷D的左子樹，preorder(root.legt),此時為preorder(null):

  

  4. 進入preoder(null)，發現抵達了遞歸邊界，直接return，然後是preorder(D)的邏輯往下走，走到了preorder(root.right):

  

  5. 再次進入preorder(null)，發現抵達了遞歸邊界，直接return掉，回到preorder(D)裏，接着preoder(D)的邏輯往下走，發現preorder(D)已經執行完，於是返回，回到preorder(B),接着preorder(B)往下走，進入preorder(root.right)，也就是preorder(E)

  

  6. E不為空，進入遞歸式，輸出E值，接着優先遍歷E的左子樹，preorder(root.left),此時為preorder(null)，抵達遞歸邊界，直接返回preorder(E)；繼續preorder(E)執行下去，是preorder(root.right),這裏E的right同樣是null，直接返回。如此，preorder(E)就執行完了，回到preorder(B)裏去，發現preorder(B)也執行完了，於是回到preorder（A）；執行preorder(A)中的preorder(root.right)去了
  7. root是A，root.right就是C，進入preorder(C)的邏輯：

  

  8. C不為空，進入遞歸式，輸出C值，接着優先遍歷C的左子樹，preorder(root.left),此時為preorder(null)，觸碰遞歸邊界，直接返回，繼續preorder(C)執行下去，就是preorder(root.right),這裏是C的right是F：

  

  9. 進入preorder(F)的邏輯，F不為空，進入遞歸式，輸出F值，接着優先遍歷F的左子樹，preorder(root.left),此時為preorder(null),觸碰遞歸邊界，直接返回preorder(F);繼續執行preorder(F)，是preorder(root.right),這裏是F的right同樣是null，故直接返回preorder(F),此時preorder(F)已經執行完了，返回preorder(C),此時preorder(C)也執行完了，返回preorder(A)；發現preorder(A)作為遞歸入口，它的邏輯也已經執行完了，於是我們的遞歸活動就到這介結束了
  10. 結點值為：A => B => D => E => C => F

（2）中序遍歷

• 理解了先序遍歷的過程，中序遍歷的過程區別只是把遍歷順序調換了
• 左子樹 => 根結點 => 右子樹

• 若有多個子樹，遍歷路線如下：

• 遞歸邊界照舊，唯一發生變化的是遞歸式裏調用遞歸函數的順序——左子樹的訪問優先於根結點

// 所有遍歷函數的入參都是樹的根結點對象
function inorder(root){
    // 遞歸邊界，root為空
    if(!root){
        return
    }
    
    // 遞歸遍歷左子樹
    inorder(root.left)
    
    // 輸出當前遍歷的結點值
    console.log('當前遍歷的結點值為'，root.val)
    
    // 遞歸遍歷右子樹
    inorder(root.right)
}

• 輸出順序：D => B => E => A => C => F

（3）後序遍歷

• 遍歷順序：左子樹 => 右子樹 => 根結點

• 如果有多個子樹，遍歷路線如下：

• 編碼實現時，遞歸邊界照舊，唯一發生變化的仍然是遞歸式裏調用遞歸函數的順序：

function postorder(root)[
    // 遞歸邊界，root為空
    if(!root){
        return
    }
    
    // 遞歸遍歷左子樹
    postorder(root.left)
    
    // 遞歸遍歷右子樹
    postorder(root.right)
    
    // 輸出當前遍歷的結點值
    consoloe.log('當前遍歷的結點值為',root.val)
}

• 輸出順序：D => E => B => F => C => A

四、總結

對於二叉樹的先中後遍歷，只要掌握到一種思路，舉一反三，順手推導其他三種思路就好啦。一起加油！一起努力！

❓其他

1. 疑問與作者HowieCong聲明

• 如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
• 若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
• 聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！

2. 作者社交媒體/郵箱-HowieCong

• HowieCong Social Meida : Wechat|Instagram|Feishu|Juejin|Segmentfault...
• HowieCong Mail : mailto:howiecong@163.com