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

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

圖中樹的結構如下，以變量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: {
                  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
          }
      }
  }
}

設計函數，傳入的參數為樹的根root，從根節點出發，遍歷所有節點

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

先遍歷節點的左子樹，再訪問節點，最后遍歷節點的右子樹。故當來到節點，發現其存在左子樹時，先遍歷其左子樹，前往的下個節點就是左子樹的根，即當前節點的左孩子，同時將當前節點保存，當其左子樹遍歷結束后，再訪問該節點，并遍歷該節點的右子樹。用棧保存經過的待訪問的節點，棧頂節點表示正在遍歷節點的左子樹。

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

當節點僅存在右子樹時，因為其無左子樹，所以直接訪問節點，并前往節點的右孩子，開始遍歷其右子樹。

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

當節點無子樹遍歷，直接訪問節點。同時，說明棧頂節點的左子樹遍歷結束。棧頂節點出棧，訪問節點，開始遍歷其右子樹。若節點無右子樹，說明棧中新的棧頂節點的左子樹遍歷結束。棧頂節點出棧，訪問節點，開始遍歷其右子樹。如此循環直至節點含右子樹。

function inOrderTraverse(root) {
  let current = root, // 從根節點出發
    stack = [] // 保存待訪問的節點
  while (current) { // 找到下個節點，若不存在，則跳出循環，遍歷結束
    let nextNode
    if (current.left) { // 當前節點存在左子樹
      stack.push(current) // 保存當前節點，當其左子樹遍歷結束后，再訪問該節點
      nextNode = current.left // 前往當前節點的左孩子，遍歷當前節點的左子樹
    } else if (!current.left && current.right) { // 僅存在右子樹
      console.log(current.value) // 無左子樹，直接訪問節點
      nextNode = current.right // 開始遍歷其右子樹
    } else { // 節點無子樹
      console.log(current.value) // 訪問節點
      let pop = stack.pop() // 棧頂節點的左子樹遍歷結束，棧頂節點出棧
      while (pop && !pop.right) { // 若出棧節點不含右子樹
        console.log(pop.value) // 訪問出棧的節點
        // 此時棧中新的棧頂節點的左子樹遍歷結束
        pop = stack.pop() // 棧頂節點出棧
      } // 直到棧空或彈出含右子樹的節點
      if (pop) { // 含右子樹的節點
        console.log(pop.value) // 訪問節點
        nextNode = pop.right // 前往其右孩子，開始遍歷其右子樹
      } else { // 棧空
        nextNode = null // 找不到下個節點，循環結束
      }
    }
    current = nextNode // 前往下個節點
  }
}

整理后代碼如下

/**
 * 中序遍歷二叉樹
 * 傳入的參數是二叉樹的根
 * @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

其實沒那么復雜，別人家代碼

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) // 訪問節點
      current = current ? current.right : null // 遍歷右子樹
    }
  }
}
inOrderTraverse(binaryTree.root)
// H K D B E A I F C G J