亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

二叉樹的遞歸遍歷（JS實現(xiàn)）

ethernet / 2944人閱讀

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

相關(guān)概念

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

本文討論二叉樹的遍歷，對節(jié)點的訪問通過打印節(jié)點的值體現(xiàn)出來。
從二叉樹的根節(jié)點出發(fā)，遍歷可分為三個環(huán)節(jié)：

訪問節(jié)點（打印節(jié)點的值）

遍歷節(jié)點的左子樹

遍歷節(jié)點的右子樹

不同環(huán)節(jié)執(zhí)行的先后順序產(chǎn)生了不同的遍歷方式。

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

前序遍歷

上圖展現(xiàn)了前序遍歷的整個過程，其中樹的結(jié)構(gòu)用代碼表示如下（存儲為變量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
      }
  }
}

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

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

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

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

添加遞歸的終止條件，即訪問到葉節(jié)點就停止調(diào)用函數(shù)

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

中序遍歷

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

后序遍歷

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

隨著被調(diào)用次數(shù)的增加，遞歸函數(shù)會線性地增加?？臻g的使用。
至于二叉樹的非遞歸遍歷，且聽下回分解。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/89148.html

相關(guān)文章

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

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

    Yuanf 評論0 收藏0

  • JS遞歸與二叉樹的遍歷

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

    church 評論0 收藏0

  • 【數(shù)據(jù)結(jié)構(gòu)初階】第八篇——二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)（二叉樹的前、中和后序遍歷+層序遍歷+鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn)+相關(guān)

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

    BigNerdCoding 評論0 收藏0

  • 【數(shù)據(jù)結(jié)構(gòu)初階之二叉樹】：二叉樹相關(guān)的性質(zhì)和經(jīng)典的習(xí)題（用C語言實現(xiàn)，附圖詳解）

    摘要：當(dāng)集合為空時，稱該二叉樹為空二叉樹。也就是說，如果一個二叉樹的層數(shù)為，且結(jié)點總數(shù)是，則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。 ...

    Martin91 評論0 收藏0

  • Java數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹及操作(包括二叉樹遍歷)

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

    muddyway 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<