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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述過(guò)程中樹(shù)的結(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
          }
      }
  }
}

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

const preOrderTraverse = root => {
  let node = root // 初始的節(jié)點(diǎn)為樹(shù)的根節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問(wèn)節(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)都被訪問(wèn)完成
  }
}

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

翻譯成代碼就是

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

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

翻譯成代碼就是

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

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

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

翻譯成代碼就是

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

整理最終代碼如下

const preOrderTraverse = root => {
  let node = root, // 初始的節(jié)點(diǎn)為樹(shù)的根節(jié)點(diǎn)
    stack = [] // 用棧保存待前往的節(jié)點(diǎn)
  while (node) { // 若不存在下一個(gè)節(jié)點(diǎn)，循環(huán)終止
    console.log(node.value) // 訪問(wèn)節(jié)點(diǎn)（打印節(jié)點(diǎn)的值）
    if (node.left) { // 若節(jié)點(diǎn)存在左子樹(shù)
      node.right && stack.push(node.right) // 若是含左右子樹(shù)的節(jié)點(diǎn)，將其右孩子保存
      node = node.left // 則下一個(gè)節(jié)點(diǎn)就是該左子樹(shù)的根
    } else if (!node.left && node.right) { // 若節(jié)點(diǎn)僅存在右子樹(shù)
      node = node.right // 則下一個(gè)節(jié)點(diǎn)就是該右子樹(shù)的根
    } else { // 葉節(jié)點(diǎn)，說(shuō)明最近的含有左右子樹(shù)的節(jié)點(diǎn)的左子樹(shù)遍歷結(jié)束，開(kāi)始遍歷含有左右子樹(shù)的節(jié)點(diǎn)的右子樹(shù)
      node = stack.pop() // 前往那個(gè)右子樹(shù)的根，被存于棧中，若棧空，說(shuō)明沒(méi)有右子樹(shù)待遍歷，遍歷結(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) // 訪問(wèn)節(jié)點(diǎn)
      stack.push(current)
      current = current.left // 遍歷左子樹(shù)
    } else {
      current = stack.pop()
      current = current ? current.right : null // 遍歷右子樹(shù)
    }
  }
}
preOrderTraverse(binaryTree.root)