二叉樹的非遞歸前序遍歷

ybak 發(fā)布于2019-08-21 17:07 / 805人閱讀

摘要：當(dāng)其左子樹遍歷完成時(shí)觸發(fā)的時(shí)機(jī)是到達(dá)葉節(jié)點(diǎn)，前往其右子樹的根，開始遍歷其右子樹。例如，到節(jié)點(diǎn)時(shí)，將其右子樹的根節(jié)點(diǎn)保存起來，當(dāng)左子樹遍歷結(jié)束時(shí)，才取出節(jié)點(diǎn)開始遍歷右子樹。

前序遍歷

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

模擬過程

過程中，用「打印節(jié)點(diǎn)值」表示對(duì)節(jié)點(diǎn)的訪問，「訪問結(jié)束」表示該節(jié)點(diǎn)完成了訪問節(jié)點(diǎn)，遍歷節(jié)點(diǎn)的左子樹，遍歷節(jié)點(diǎn)的右子樹的所有過程。

到達(dá)節(jié)點(diǎn)A，訪問節(jié)點(diǎn)A（打印節(jié)點(diǎn)值），開始遍歷A的左子樹

到達(dá)節(jié)點(diǎn)B，訪問節(jié)點(diǎn)B（打印節(jié)點(diǎn)值），開始遍歷B的左子樹

到達(dá)節(jié)點(diǎn)D，訪問節(jié)點(diǎn)D（打印節(jié)點(diǎn)值），開始遍歷D的左子樹

到達(dá)節(jié)點(diǎn)H，訪問節(jié)點(diǎn)H（打印節(jié)點(diǎn)值），H僅有右子樹，開始遍歷H的右子樹

到達(dá)節(jié)點(diǎn)K，訪問節(jié)點(diǎn)K（打印節(jié)點(diǎn)值），K無子樹，節(jié)點(diǎn)K的訪問結(jié)束

節(jié)點(diǎn)K的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)H的右子樹遍歷結(jié)束，且節(jié)點(diǎn)H僅有右子樹，節(jié)點(diǎn)H的訪問結(jié)束

節(jié)點(diǎn)H的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)D的左子樹遍歷結(jié)束，且節(jié)點(diǎn)D僅有左子樹，節(jié)點(diǎn)D的訪問結(jié)束

節(jié)點(diǎn)D的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)B的左子樹遍歷結(jié)束，開始遍歷節(jié)點(diǎn)B的右子樹

到達(dá)節(jié)點(diǎn)E，訪問節(jié)點(diǎn)E（打印節(jié)點(diǎn)值），E無子樹，節(jié)點(diǎn)E的訪問結(jié)束

節(jié)點(diǎn)E的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)B的右子樹遍歷結(jié)束，且節(jié)點(diǎn)B的左子樹也遍歷結(jié)束，節(jié)點(diǎn)B的訪問結(jié)束

節(jié)點(diǎn)B的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)A的左子樹遍歷結(jié)束，開始遍歷節(jié)點(diǎn)A的右子樹

到達(dá)節(jié)點(diǎn)C，訪問節(jié)點(diǎn)C（打印節(jié)點(diǎn)值），開始遍歷C的左子樹

到達(dá)節(jié)點(diǎn)F，訪問節(jié)點(diǎn)F（打印節(jié)點(diǎn)值），開始遍歷F的左子樹

到達(dá)節(jié)點(diǎn)I，訪問節(jié)點(diǎn)I（打印節(jié)點(diǎn)值），I無子樹，節(jié)點(diǎn)I的訪問結(jié)束

節(jié)點(diǎn)I的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)F的左子樹遍歷結(jié)束，且節(jié)點(diǎn)F僅有左子樹，節(jié)點(diǎn)F的訪問結(jié)束

節(jié)點(diǎn)F的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)C的左子樹遍歷結(jié)束，開始遍歷節(jié)點(diǎn)C的右子樹

到達(dá)節(jié)點(diǎn)G，訪問節(jié)點(diǎn)G（打印節(jié)點(diǎn)值），G僅有右子樹，開始遍歷G的右子樹

到達(dá)節(jié)點(diǎn)J，訪問節(jié)點(diǎn)J（打印節(jié)點(diǎn)值），J無子樹，節(jié)點(diǎn)J的訪問結(jié)束

節(jié)點(diǎn)J的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)G的右子樹遍歷結(jié)束，且節(jié)點(diǎn)G僅有右子樹，節(jié)點(diǎn)G的訪問結(jié)束

節(jié)點(diǎn)G的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)C的右子樹遍歷結(jié)束，且節(jié)點(diǎn)C的左子樹也遍歷結(jié)束，節(jié)點(diǎn)C的訪問結(jié)束

節(jié)點(diǎn)C的訪問結(jié)束同時(shí)意味著節(jié)點(diǎn)A的右子樹遍歷結(jié)束，且節(jié)點(diǎn)A的左子樹也遍歷結(jié)束，節(jié)點(diǎn)A的訪問結(jié)束

至此，樹中所有節(jié)點(diǎn)都被訪問

分析過程

上述過程中節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下

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

上述過程中樹的結(jié)構(gòu)如下，被當(dāng)作變量root保存

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

分析過程：每到達(dá)一個(gè)節(jié)點(diǎn)，先訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值），然后尋找下一個(gè)節(jié)點(diǎn)并前往，直至所有節(jié)點(diǎn)都被訪問完成，且初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)（root）。草寫代碼如下

const preOrderTraverse = root => {
  let node = root // 初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    ...nextNode // 尋找下一個(gè)前往的節(jié)點(diǎn)
    node = nextNode || null // 前往下一個(gè)節(jié)點(diǎn)，若找不到下一個(gè)節(jié)點(diǎn)，則所有節(jié)點(diǎn)都被訪問完成
  }
}

尋找下一個(gè)節(jié)點(diǎn)并前往，前往下一個(gè)節(jié)點(diǎn)的方式有多種，其中一種是若節(jié)點(diǎn)存在左子樹，則下一個(gè)節(jié)點(diǎn)就是該左子樹的根，如上述過程中 A->B, B->D, D->H, C->F, F->I

翻譯成代碼就是

const preOrderTraverse = root => {
  let node = root // 初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    let nextNode
    if(node.left){ // 若節(jié)點(diǎn)存在左子樹
      nextNode = node.left // 則下一個(gè)節(jié)點(diǎn)就是該左子樹的根
    }
    ... // 未完待續(xù)
    node = nextNode || null // 前往下一個(gè)節(jié)點(diǎn)，若找不到下一個(gè)節(jié)點(diǎn)，則所有節(jié)點(diǎn)都被訪問完成
  }
}

尋找下一個(gè)節(jié)點(diǎn)并前往，前往下一個(gè)節(jié)點(diǎn)的另一種方式是，若節(jié)點(diǎn)僅存在右子樹，則下一個(gè)節(jié)點(diǎn)就是該右子樹的根，如上述過程中 H->K, G->J

翻譯成代碼就是

const preOrderTraverse = root => {
  let node = root // 初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    let nextNode
    if(node.left){ // 若節(jié)點(diǎn)存在左子樹
      nextNode = node.left // 則下一個(gè)節(jié)點(diǎn)就是該左子樹的根
    }else if(!node.left&&node.right){ // 若節(jié)點(diǎn)僅存在右子樹
      nextNode = node.right // 則下一個(gè)節(jié)點(diǎn)就是該右子樹的根
    }
    ... // 未完待續(xù)
    node = nextNode || null // 前往下一個(gè)節(jié)點(diǎn)，若找不到下一個(gè)節(jié)點(diǎn)，則所有節(jié)點(diǎn)都被訪問完成
  }
}

前面提到的尋找下一個(gè)節(jié)點(diǎn)并前往的方式中，其下一個(gè)節(jié)點(diǎn)都是當(dāng)前節(jié)點(diǎn)的左孩子或右孩子，分析前序遍歷的過程，發(fā)現(xiàn)還有一種前往的下一個(gè)節(jié)點(diǎn)并不是當(dāng)前節(jié)點(diǎn)的孩子的情況，如上述過程中 K->E, E->C, I->J

當(dāng)節(jié)點(diǎn)僅含一顆子樹時(shí)，就遍歷該子樹，當(dāng)節(jié)點(diǎn)含左右子樹時(shí)，先遍歷其左子樹，而將其右子樹的根保存。當(dāng)其左子樹遍歷完成時(shí)（觸發(fā)的時(shí)機(jī)是到達(dá)葉節(jié)點(diǎn)），前往其右子樹的根，開始遍歷其右子樹。
例如，到節(jié)點(diǎn)A時(shí)，將其右子樹的根節(jié)點(diǎn)C保存起來，當(dāng)左子樹遍歷結(jié)束時(shí)，才取出節(jié)點(diǎn)C開始遍歷右子樹。到達(dá)節(jié)點(diǎn)B，將其右子樹的根節(jié)點(diǎn)E保存起來。當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)K，節(jié)點(diǎn)B的左子樹遍歷結(jié)束，取出節(jié)點(diǎn)E開始遍歷右子樹。將節(jié)點(diǎn)E彈出，此時(shí)僅剩節(jié)點(diǎn)A的右子樹待遍歷。節(jié)點(diǎn)C先于節(jié)點(diǎn)E保存，但后于節(jié)點(diǎn)E取出，故采用棧保存待遍歷的右子樹的根。

翻譯成代碼就是

const preOrderTraverse = root => {
  let node = root, // 初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)
      stack = [] // 用棧保存待遍歷的右子樹的根
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    let nextNode
    if(node.left){ // 若節(jié)點(diǎn)存在左子樹
      node.right && stack.push(node.right) // 若是含左右子樹的節(jié)點(diǎn)，遍歷左子樹，保存右子樹
      nextNode = node.left // 則下一個(gè)節(jié)點(diǎn)就是該左子樹的根
    }else if(!node.left&&node.right){ // 若節(jié)點(diǎn)僅存在右子樹
      nextNode = node.right // 則下一個(gè)節(jié)點(diǎn)就是該右子樹的根
    }else{ // 葉節(jié)點(diǎn)，說明最近的含有左右子樹的節(jié)點(diǎn)的左子樹遍歷結(jié)束，開始遍歷含有左右子樹的節(jié)點(diǎn)的右子樹
      nextNode = stack.pop() // 前往那個(gè)右子樹的根，被存于棧中，若?？?，說明沒有右子樹待遍歷，遍歷結(jié)束
    }
    node = nextNode // 前往下一個(gè)節(jié)點(diǎn)，若找不到下一個(gè)節(jié)點(diǎn)，則所有節(jié)點(diǎn)都被訪問完成
  }
}

整理最終代碼如下

const preOrderTraverse = root => {
  let node = root, // 初始的節(jié)點(diǎn)為樹的根節(jié)點(diǎn)
    stack = [] // 用棧保存待前往的節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    if (node.left) { // 若節(jié)點(diǎn)存在左子樹
      node.right && stack.push(node.right) // 若是含左右子樹的節(jié)點(diǎn)，將其右孩子保存
      node = node.left // 則下一個(gè)節(jié)點(diǎn)就是該左子樹的根
    } else if (!node.left && node.right) { // 若節(jié)點(diǎn)僅存在右子樹
      node = node.right // 則下一個(gè)節(jié)點(diǎn)就是該右子樹的根
    } else { // 葉節(jié)點(diǎn)，說明最近的含有左右子樹的節(jié)點(diǎn)的左子樹遍歷結(jié)束，開始遍歷含有左右子樹的節(jié)點(diǎn)的右子樹
      node = stack.pop() // 前往那個(gè)右子樹的根，被存于棧中，若?？?，說明沒有右子樹待遍歷，遍歷結(jié)束
    }
  }
}
preOrderTraverse(root)
// A B D H K C F I G J

為什么我總想的那么復(fù)雜

const preOrderTraverse = root => {
  let current = root,
    stack = []
  while (current || stack.length !== 0) {
    if (current) {
      console.log(current.value) // 訪問節(jié)點(diǎn)
      stack.push(current)
      current = current.left // 遍歷左子樹
    } else {
      current = stack.pop()
      current = current ? current.right : null // 遍歷右子樹
    }
  }
}
preOrderTraverse(binaryTree.root)

GPU云服務(wù)器云服務(wù)器二叉樹的遍歷非遞歸二叉樹遍歷二叉樹的存儲(chǔ) 二叉樹的存儲(chǔ)結(jié)構(gòu)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/89145.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

ybak

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

伏羲云：中秋鉅惠，全場(chǎng)75折，美國cn2gia月付18起

閱讀 2037·2021-09-13 10:23
Microsoft Exchange ProxyToken漏洞可以讓黑客竊取用戶的電子郵件

閱讀 2375·2021-09-02 09:47
華為云828企業(yè)上云節(jié)：1核2G內(nèi)存HECS云服務(wù)器￥69.15/年，2核4G ￥264.99/年，

閱讀 3831·2021-08-16 11:01
輕云互聯(lián)-618鉅惠秒殺，香港CN2大寬帶KVM架構(gòu)云服務(wù)器月付22元，美國圣何塞精品云月付19元爆

閱讀 1252·2021-07-25 21:37
vertical-align 和 line-height | 垂直居中

閱讀 1630·2019-08-30 15:56
CSS基礎(chǔ)篇--使用position:sticky 實(shí)現(xiàn)粘性布局

閱讀 561·2019-08-30 13:52
標(biāo)準(zhǔn)庫（四）包裝對(duì)象二number

閱讀 3154·2019-08-26 10:17
支持單圖片和多圖片上傳

閱讀 2470·2019-08-23 18:17

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

二叉樹的非遞歸前序遍歷

相關(guān)文章

【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)-二分搜索樹

【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實(shí)現(xiàn)-二分搜索樹

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

發(fā)表評(píng)論

0條評(píng)論

ybak

男|高級(jí)講師

TA的文章

伏羲云：中秋鉅惠，全場(chǎng)75折，美國cn2gia月付18起

Microsoft Exchange ProxyToken漏洞可以讓黑客竊取用戶的電子郵件

華為云828企業(yè)上云節(jié)：1核2G內(nèi)存HECS云服務(wù)器￥69.15/年，2核4G ￥264.99/年，

輕云互聯(lián)-618鉅惠秒殺，香港CN2大寬帶KVM架構(gòu)云服務(wù)器月付22元，美國圣何塞精品云月付19元爆

vertical-align 和 line-height | 垂直居中

CSS基礎(chǔ)篇--使用position:sticky 實(shí)現(xiàn)粘性布局

標(biāo)準(zhǔn)庫（四）包裝對(duì)象二number

支持單圖片和多圖片上傳

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

二叉樹的非遞歸前序遍歷

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！