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

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

圖中樹的結構如下，以變量root保存

// 節(jié)點的數(shù)據(jù)結構
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ù)，傳入的參數(shù)為樹的根root，從根節(jié)點出發(fā)，遍歷所有節(jié)點

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

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

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

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

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

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

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

整理后代碼如下

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

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

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