成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

ethernet / 2881人閱讀

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

相關(guān)概念

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

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

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

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

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

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

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

前序遍歷

上圖展現(xiàn)了前序遍歷的整個(gè)過程，其中樹的結(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è)計(jì)一個(gè)函數(shù)，用于遍歷二叉樹，傳入的參數(shù)是二叉樹的根節(jié)點(diǎn)，函數(shù)會先訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值），再遍歷節(jié)點(diǎn)的左子樹，最后遍歷節(jié)點(diǎn)的右子樹。
上述代碼翻譯成代碼片段就是

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

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

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

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

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

中序遍歷

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

后序遍歷

const postOrderTraverse = root => {
  root.left && postOrderTraverse(root.left) // 若節(jié)點(diǎn)的左子樹存在，則遍歷節(jié)點(diǎn)的左子樹
  root.right && postOrderTraverse(root.right) // 若節(jié)點(diǎn)的右子樹存在，則遍歷節(jié)點(diǎn)的右子樹
  console.log(root.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
}
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://systransis.cn/yun/89148.html

相關(guān)文章

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

    摘要：樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹，在編譯器底層很有用后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。 樹的簡介 棧、隊(duì)列、鏈表等數(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)題加是因?yàn)樗蚜讼潞蟾杏X網(wǎng)上用來描述這概念的不多，簡單地說遞歸就是函數(shù)調(diào)用自己的過程。 貌似大部分語言中的遞歸都差不多， 之所以在標(biāo)題加JS是因?yàn)樗蚜讼潞蟾杏X網(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)的實(shí)現(xiàn)+相關(guān)

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

    BigNerdCoding 評論0 收藏0

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

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

    Martin91 評論0 收藏0

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

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

    muddyway 評論0 收藏0

發(fā)表評論

0條評論

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