摘要：中序遍歷概念中序遍歷指先遍歷節(jié)點(diǎn)的左子樹，再訪問節(jié)點(diǎn)，最后遍歷節(jié)點(diǎn)的右子樹，按照這種規(guī)則不重復(fù)地訪問樹中所有節(jié)點(diǎn)的過程。用棧保存經(jīng)過的待訪問的節(jié)點(diǎn)，棧頂節(jié)點(diǎn)表示正在遍歷節(jié)點(diǎn)的左子樹。同時，說明棧頂節(jié)點(diǎn)的左子樹遍歷結(jié)束。

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

圖中樹的結(jié)構(gòu)如下，以變量root保存

// 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
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: {
                  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
          }
      }
  }
}

設(shè)計(jì)函數(shù)，傳入的參數(shù)為樹的根root，從根節(jié)點(diǎn)出發(fā)，遍歷所有節(jié)點(diǎn)

/**
 * 中序遍歷二叉樹
 * 傳入的參數(shù)是二叉樹的根
 * @param {Node} root 
 */
function inOrderTraverse(root) {
  let current = root // 從根節(jié)點(diǎn)出發(fā)
  while (current) { // 找到下個節(jié)點(diǎn)，若不存在，則跳出循環(huán)，遍歷結(jié)束
    let nextNode
    // 尋找下個節(jié)點(diǎn)
    current = nextNode // 前往下個節(jié)點(diǎn)
  }
}

先遍歷節(jié)點(diǎn)的左子樹，再訪問節(jié)點(diǎn)，最后遍歷節(jié)點(diǎn)的右子樹。故當(dāng)來到節(jié)點(diǎn)，發(fā)現(xiàn)其存在左子樹時，先遍歷其左子樹，前往的下個節(jié)點(diǎn)就是左子樹的根，即當(dāng)前節(jié)點(diǎn)的左孩子，同時將當(dāng)前節(jié)點(diǎn)保存，當(dāng)其左子樹遍歷結(jié)束后，再訪問該節(jié)點(diǎn)，并遍歷該節(jié)點(diǎn)的右子樹。用棧保存經(jīng)過的待訪問的節(jié)點(diǎn)，棧頂節(jié)點(diǎn)表示正在遍歷節(jié)點(diǎn)的左子樹。

function inOrderTraverse(root) {
  let current = root, // 從根節(jié)點(diǎn)出發(fā)
    stack = [] // 保存待訪問的節(jié)點(diǎn)
  while (current) { // 找到下個節(jié)點(diǎn)，若不存在，則跳出循環(huán)，遍歷結(jié)束
    let nextNode
    if (current.left) { // 當(dāng)前節(jié)點(diǎn)存在左子樹
      stack.push(current) // 保存當(dāng)前節(jié)點(diǎn)，當(dāng)其左子樹遍歷結(jié)束后，再訪問該節(jié)點(diǎn)
      nextNode = current.left // 前往當(dāng)前節(jié)點(diǎn)的左孩子，遍歷當(dāng)前節(jié)點(diǎn)的左子樹
    }
    // 未完待續(xù)
    current = nextNode // 前往下個節(jié)點(diǎn)
  }
}

當(dāng)節(jié)點(diǎn)僅存在右子樹時，因?yàn)槠錈o左子樹，所以直接訪問節(jié)點(diǎn)，并前往節(jié)點(diǎn)的右孩子，開始遍歷其右子樹。

function inOrderTraverse(root) {
  let current = root, // 從根節(jié)點(diǎn)出發(fā)
    stack = [] // 保存待訪問的節(jié)點(diǎn)
  while (current) { // 找到下個節(jié)點(diǎn)，若不存在，則跳出循環(huán)，遍歷結(jié)束
    let nextNode
    if (current.left) { // 當(dāng)前節(jié)點(diǎn)存在左子樹
      stack.push(current) // 保存當(dāng)前節(jié)點(diǎn)，當(dāng)其左子樹遍歷結(jié)束后，再訪問該節(jié)點(diǎn)
      nextNode = current.left // 前往當(dāng)前節(jié)點(diǎn)的左孩子，遍歷當(dāng)前節(jié)點(diǎn)的左子樹
    } else if (!current.left && current.right) { // 僅存在右子樹
      console.log(current.value) // 無左子樹，直接訪問節(jié)點(diǎn)
      nextNode = current.right // 開始遍歷其右子樹
    }
    // 未完待續(xù)
    current = nextNode // 前往下個節(jié)點(diǎn)
  }
}

當(dāng)節(jié)點(diǎn)無子樹遍歷，直接訪問節(jié)點(diǎn)。同時，說明棧頂節(jié)點(diǎn)的左子樹遍歷結(jié)束。棧頂節(jié)點(diǎn)出棧，訪問節(jié)點(diǎn)，開始遍歷其右子樹。若節(jié)點(diǎn)無右子樹，說明棧中新的棧頂節(jié)點(diǎn)的左子樹遍歷結(jié)束。棧頂節(jié)點(diǎn)出棧，訪問節(jié)點(diǎn)，開始遍歷其右子樹。如此循環(huán)直至節(jié)點(diǎn)含右子樹。

function inOrderTraverse(root) {
  let current = root, // 從根節(jié)點(diǎn)出發(fā)
    stack = [] // 保存待訪問的節(jié)點(diǎn)
  while (current) { // 找到下個節(jié)點(diǎn)，若不存在，則跳出循環(huán)，遍歷結(jié)束
    let nextNode
    if (current.left) { // 當(dāng)前節(jié)點(diǎn)存在左子樹
      stack.push(current) // 保存當(dāng)前節(jié)點(diǎn)，當(dāng)其左子樹遍歷結(jié)束后，再訪問該節(jié)點(diǎn)
      nextNode = current.left // 前往當(dāng)前節(jié)點(diǎn)的左孩子，遍歷當(dāng)前節(jié)點(diǎn)的左子樹
    } else if (!current.left && current.right) { // 僅存在右子樹
      console.log(current.value) // 無左子樹，直接訪問節(jié)點(diǎn)
      nextNode = current.right // 開始遍歷其右子樹
    } else { // 節(jié)點(diǎn)無子樹
      console.log(current.value) // 訪問節(jié)點(diǎn)
      let pop = stack.pop() // 棧頂節(jié)點(diǎn)的左子樹遍歷結(jié)束，棧頂節(jié)點(diǎn)出棧
      while (pop && !pop.right) { // 若出棧節(jié)點(diǎn)不含右子樹
        console.log(pop.value) // 訪問出棧的節(jié)點(diǎn)
        // 此時棧中新的棧頂節(jié)點(diǎn)的左子樹遍歷結(jié)束
        pop = stack.pop() // 棧頂節(jié)點(diǎn)出棧
      } // 直到?？栈驈棾龊易訕涞墓?jié)點(diǎn)
      if (pop) { // 含右子樹的節(jié)點(diǎn)
        console.log(pop.value) // 訪問節(jié)點(diǎn)
        nextNode = pop.right // 前往其右孩子，開始遍歷其右子樹
      } else { // ?？?        nextNode = null // 找不到下個節(jié)點(diǎn)，循環(huán)結(jié)束
      }
    }
    current = nextNode // 前往下個節(jié)點(diǎn)
  }
}

整理后代碼如下

/**
 * 中序遍歷二叉樹
 * 傳入的參數(shù)是二叉樹的根
 * @param {Node} root 
 */
const inOrderTraverse = root => {
  let current = root,
    stack = []
  while (current) {
    if (current.left) {
      stack.push(current)
      current = current.left
    } else if (!current.left && current.right) {
      console.log(current.value)
      current = current.right
    } else {
      console.log(current.value)
      let pop = stack.pop()
      while (pop && !pop.right) {
        console.log(pop.value)
        pop = stack.pop()
      }
      pop && console.log(pop.value)
      current = pop ? pop.right : null
    }
  }
}
inOrderTraverse(binaryTree.root)
// H K D B E A I F C G J

其實(shí)沒那么復(fù)雜，別人家代碼

const inOrderTraverse = root => {
  let current = root,
    stack = []
  while (current || stack.length !== 0) {
    if (current) {
      stack.push(current)
      current = current.left // 遍歷左子樹
    } else {
      current = stack.pop()
      current && console.log(current.value) // 訪問節(jié)點(diǎn)
      current = current ? current.right : null // 遍歷右子樹
    }
  }
}
inOrderTraverse(binaryTree.root)
// H K D B E A I F C G J