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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述過程中節(jié)點的數(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á)一個節(jié)點，先訪問節(jié)點（打印節(jié)點的值），然后尋找下一個節(jié)點并前往，直至所有節(jié)點都被訪問完成，且初始的節(jié)點為樹的根節(jié)點（root）。草寫代碼如下

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

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

翻譯成代碼就是

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

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

翻譯成代碼就是

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

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

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

翻譯成代碼就是

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

整理最終代碼如下

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