二叉樹的遞歸遍歷（JS實現）

ethernet 發布于2019-08-21 17:07 / 2867人閱讀

摘要：本文討論二叉樹的遍歷，對節點的訪問通過打印節點的值體現出來。從二叉樹的根節點出發，遍歷可分為三個環節訪問節點打印節點的值遍歷節點的左子樹遍歷節點的右子樹不同環節執行的先后順序產生了不同的遍歷方式。至于二叉樹的非遞歸遍歷，且聽下回分解。

相關概念

「樹的遍歷」指按照一定規則不重復地訪問樹中所有節點的過程。
「訪問」指針對節點的操作，如打印節點的值，更新節點的值等。

本文討論二叉樹的遍歷，對節點的訪問通過打印節點的值體現出來。
從二叉樹的根節點出發，遍歷可分為三個環節：

訪問節點（打印節點的值）

遍歷節點的左子樹

遍歷節點的右子樹

不同環節執行的先后順序產生了不同的遍歷方式。

「前序遍歷」指先訪問節點，再遍歷節點的左子樹，最后遍歷節點的右子樹，按照這種規則不重復地訪問樹中所有節點的過程。
「中序遍歷」指先遍歷節點的左子樹，再訪問節點，最后遍歷節點的右子樹，按照這種規則不重復地訪問樹中所有節點的過程。
「后序遍歷」指先遍歷節點的左子樹，再遍歷節點的右子樹，最后訪問節點，按照這種規則不重復地訪問樹中所有節點的過程。

前序遍歷

上圖展現了前序遍歷的整個過程，其中樹的結構用代碼表示如下（存儲為變量root)

function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

root {
  value: "A",
  left: {
      value: "B",
      left: {
          value: "D",
          left: {
              value: "H",
              left: null,
              right: null
          },
          right: {
              value: "I",
              left: null,
              right: null
          }
      },
      right: {
          value: "E",
          left: null,
          right: null
      }
  },
  right: {
      value: "C",
      left: {
          value: "F",
          left: null,
          right: null
      },
      right: {
          value: "G",
          left: null,
          right: null
      }
  }
}

設計一個函數，用于遍歷二叉樹，傳入的參數是二叉樹的根節點，函數會先訪問節點（打印節點的值），再遍歷節點的左子樹，最后遍歷節點的右子樹。
上述代碼翻譯成代碼片段就是

/**
 * 函數的作用是遍歷二叉樹
 * 傳入的參數是二叉樹的根節點
 * @param {object} root 
 */
function preOrderTraverse(root){
  console.log(root.value) // 訪問節點（打印節點的值）
  ... // 遍歷節點的左子樹
  ... // 遍歷節點的右子樹
}

... 處應該是遍歷節點的左，右子二叉樹的代碼。遍歷二叉樹不正是這個函數的作用嗎？故想到了遞歸

function preOrderTraverse(root){
  console.log(root.value) // 訪問節點（打印節點的值）
  preOrderTraverse(root.left) // 遍歷節點的左子樹
  preOrderTraverse(root.right) // 遍歷節點的右子樹
}

添加遞歸的終止條件，即訪問到葉節點就停止調用函數

const preOrderTraverse = root => {
  console.log(root.value) // 訪問節點（打印節點的值）
  root.left && preOrderTraverse(root.left) // 若節點的左子樹存在，則遍歷節點的左子樹
  root.right && preOrderTraverse(root.right) // 若節點的右子樹存在，則遍歷節點的右子樹
}
preOrderTraverse(root)
// A B D H I E C F G

舉一反三

中序遍歷

const inOrderTraverse = root => {
  root.left && inOrderTraverse(root.left) // 若節點的左子樹存在，則遍歷節點的左子樹
  console.log(root.value) // 訪問節點（打印節點的值）
  root.right && inOrderTraverse(root.right) // 若節點的右子樹存在，則遍歷節點的右子樹
}
inOrderTraverse(root)
// H D I B E A F C G

后序遍歷

const postOrderTraverse = root => {
  root.left && postOrderTraverse(root.left) // 若節點的左子樹存在，則遍歷節點的左子樹
  root.right && postOrderTraverse(root.right) // 若節點的右子樹存在，則遍歷節點的右子樹
  console.log(root.value) // 訪問節點（打印節點的值）
}
postOrderTraverse(root)
// H I D E B F G C A

非遞歸遍歷

隨著被調用次數的增加，遞歸函數會線性地增加棧空間的使用。
至于二叉樹的非遞歸遍歷，且聽下回分解。

云服務器 GPU云服務器二叉樹的遍歷非遞歸二叉樹遍歷 JS二叉樹遍歷二叉樹的存儲

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89148.html

js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與非遞歸實現)

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹，在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數據結構，都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0
JS遞歸與二叉樹的遍歷

摘要：貌似大部分語言中的遞歸都差不多，之所以在標題加是因為搜了下后感覺網上用來描述這概念的不多，簡單地說遞歸就是函數調用自己的過程。貌似大部分語言中的遞歸都差不多，之所以在標題加JS是因為搜了下后感覺網上用js來描述這概念的不多，簡單地說遞歸就是函數調用自己的過程。下面的栗子可以很直觀地展示遞歸的執行過程： function rec(x){ if(x!==1){ console....

church 2019-08-21 10:48 評論0 收藏0
【數據結構初階】第八篇——二叉樹的鏈式結構（二叉樹的前、中和后序遍歷+層序遍歷+鏈式結構的實現+相關

摘要：代碼實現如下二叉樹的創建與銷毀二叉樹的創建問題通過前序遍歷的數組給定一串字符串，代表的是空樹，其他的都是節點。 ??本篇博客我要來和大家一起聊一聊數據結構中的二...

BigNerdCoding 2021-11-18 10:02 評論0 收藏0
【數據結構初階之二叉樹】：二叉樹相關的性質和經典的習題（用C語言實現，附圖詳解）

摘要：當集合為空時，稱該二叉樹為空二叉樹。也就是說，如果一個二叉樹的層數為，且結點總數是，則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。 ...

Martin91 2021-11-24 09:39 評論0 收藏0
Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0