二叉樹的深度優先遍歷和廣度優先遍歷

二叉樹是一種很重要的數據結構，對於二叉樹的遍歷，有深度優先遍歷和廣度優先遍歷，深度優先遍歷又有先序、中序、後續遍歷，廣度優先遍歷就是按層遍歷。

1. 深度優先遍歷

深度優先遍歷，也就是先序、中序、後續遍歷，我之前有一篇隨筆已經說的很清楚了，在這裡我只貼下代碼就好了。

傳送門：詳細教你實現BST(二叉排序樹)

在這裡我依然用之前建立好的Node、Stack、BST結構來實現代碼。

class Node {
  constructor(data, leftNode, rightNode) {
    this.data = data
    this.leftNode = leftNode
    this.rightNode = rightNode
  }
  print () {
    return this.data
  }
}

class Stack {
  constructor() {
    this.arr = []
  }
  pop () {
    return this.arr.shift()
  }
  push (data) {
    this.arr.unshift(data)
  }
  isEmpty () {
    return this.arr.length == 0
  }
}

class BST {
  constructor() {
    this.root = null
  }
  insert (data) {...}
  preOrder () {...}
  inOrder () {...}
  postOrder () {...}
  ...
}

先是先序、中序、後序遍歷的遞歸實現，很簡單。

// 遞歸先序
function preOrderFn (node) {
  if (node) {
    console.log(node.print())
    preOrderFn(node.leftNode)
    preOrderFn(node.rightNode)
  }
}

// 遞歸中序
function inOrderFn (node) {
  if (node) {
    inOrderFn(node.leftNode)
    console.log(node.print())
    inOrderFn(node.rightNode)
  }
}

// 遞歸後續
function postOrderFn (node) {
  if (node) {
    postOrderFn (node.leftNode)
    postOrderFn (node.rightNode)
    console.log(node.print())
  }
}

然後就是先序、中序、後續遍歷的非遞歸實現了。詳細的解釋和說明，點擊上面的傳送門就有了，這裡不過多贅述。

// 非遞歸先序
function PreOrderWithoutRecursion (root) {
  if (!root)
    return

  var parentNode = root
  var stack = new Stack()

  while (parentNode || !stack.isEmpty()) {

    // 一直遍歷到左子樹的最下麵，一邊列印data,將一路遍歷過的節點push進棧中
    if (parentNode) {
      console.log(parentNode.data)
      stack.push(parentNode)
      parentNode = parentNode.leftNode
    }
    // 當parentNode為空時，說明已經達到了左子樹的最下麵，可以出棧操作了
    else {
      parentNode = stack.pop()
      // 進入右子樹，開始新一輪迴圈
      parentNode = parentNode.rightNode
    }
  }
}

// 非遞歸中序
function inOrderWithoutRecursion (root) {
  if (!root)
    return

  var parentNode = root
  var stack = new Stack()

  while (parentNode || !stack.isEmpty()) {

    // 一直遍歷到左子樹的最下麵，將一路遍歷過的節點push進棧中
    if (parentNode) {
      stack.push(parentNode)
      parentNode = parentNode.leftNode
    }
    // 當parentNode為空時，說明已經達到了左子樹的最下麵，可以出棧操作了
    else {
      parentNode = stack.pop()
      console.log(parentNode.data)
      // 進入右子樹，開始新一輪迴圈
      parentNode = parentNode.rightNode
    }
  }
}

// 非遞歸後續
function PostOrderWithoutRecursion (root) {
  if (!root)
    return

  var parentNode = root
  var stack = new Stack()
  var lastVisitNode = null

  while (parentNode || !stack.isEmpty()) {
    if (parentNode) {
      stack.push(parentNode)
      parentNode = parentNode.leftNode
    }
    else {
      parentNode = stack.pop()
      // 如果當前節點沒有右節點或者是右節點被訪問過，則訪問當前節點
      if (!parentNode.rightNode || parentNode.rightNode.data == lastVisitNode.data) {
        console.log(parentNode.data)
        lastVisitNode = parentNode
      }
      // 訪問右節點
      else {
        stack.push(parentNode)
        parentNode = parentNode.rightNode
        while (parentNode) {
          parentNode = parentNode.leftNode
        }
      }
    }
  }
}

2. 廣度優先遍歷

其實這片隨筆有點打醬油了，只說了兩個遍歷，還有一個是在以前實現過的。

廣度優先遍歷，顧名思義，就是橫向先遍歷，也就是按層次遍歷，從根節點往下，對每一層依此訪問，在每一層中從左到右（也可以從右到左）遍歷，遍歷完一層就進入下一層，直到沒有節點。

之前講深度優先非遞歸遍歷的時候，我們用到了一個棧的數據結構，到了廣度優先遍歷的時候，我們就要用到隊列這個數據結構。

為什麼上一次用棧，這一次就要用到隊列了呢？

拿非遞歸中序遍歷舉例，我們每遍歷到一個節點就要進行入棧操作，遍歷完左節點之後，還需要找到根節點，再通過根節點找到右節點，所以我們需要最後遍歷到的節點在這個數據結構的最頂端，這不就是棧嗎？

先把我們的隊列的數據結構先建立起來再說。依然用數組模擬隊列的操作。

class Queue {
  constructor () {
    this.arr = []
  }
  enqueue (data) {
    return this.arr.push(data)
  }
  dequeue () {
    return this.arr.shift()
  }
  isEmpty () {
    return this.arr.length == 0
  }
}

為什麼要用隊列呢，我們按層次遍歷，首先遍歷根節點，然後左子樹，右子樹，然後左子樹的左子樹，左子樹的右子樹，右子樹的左子樹，依此類推。每遍歷到一個節點，就將它存在一個數據結構里，先把它的前面的節點遍歷完，才能遍歷它，也就是一個先進先出（FIFO）的遍歷方式，這不就是隊列嗎？

說下思路：首先現將根節點做入隊操作，隊列里的節點表示我們要遍歷的節點，所以隊列為空的時候也就是沒有節點可以遍歷了，即隊列不為空的時候迴圈遍歷整個隊列。首先我們取出隊列的第一個節點，也就是對這個隊列做出隊操作，訪問這個節點的值，如果這個節點存在左子樹，那麼將它的左子樹放在隊列的末尾，也就是對左子樹做入隊操作，右子樹同理。

思路很簡單，實現起來不難：

class BST {
  constructor() {
    this.root = null
  }
  // 廣度優先遍歷
  levelOrderTraversal () {
    levelOrderTraversalFn(this.root)
  }
  insert (data) {...}
  preOrder () {...}
  inOrder () {...}
  postOrder () {...}
  find (data) {..}
  getMax () {...}
  getMin () {...}
  deleteNode (data) {...}
  depth () {...}
  nodeCount () {...}
}

// 廣度優先遍歷
function levelOrderTraversalFn (node) {
  if(!node) {
    return
  }

  var que = new Queue()
  que.enqueue(node)
  while(!que.isEmpty()) {
    node = que.dequeue()
    console.log(node.data)
    if(node.leftNode) que.enqueue(node.leftNode)
    if(node.rightNode) que.enqueue(node.rightNode)
  }
}

我們試一下：

沒錯，那我們的廣度優先遍歷也就寫完了。