摘要：概念二叉樹是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹即二叉樹中不存在度大于的結點，并且，二叉樹的子樹有左右之分其次序不能任意顛倒。查找最大值查找最小值思路傳入二叉樹，尋找左子樹，直到找到不存在左子樹的節點。

二叉樹（Binary Tree）是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于 2 的結點），并且，二叉樹的子樹有左右之分（其次序不能任意顛倒。）

二叉樹的第 i 層上最多有 2 的(i-1)方個節點。（i>=1）

深度為 k 的樹最多有 2 的 k 次方-1 個節點。（k>=1）

對任何一棵二叉樹 T，如果其終端結點數為 n0，度為 2 的結點數為 n2，則 n0 = n2 + 1;
_ 一棵深度為 k 且有 2 的 k 次方-1 個結點的二叉樹稱為滿二叉樹。
_ 深度為 k 的，有 n 個結點的二叉樹，當且僅當其每一個結點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結點一一對應時，稱之為完全二叉樹。

// 創建節點
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

// 創建二叉樹格式
class BinaryTree {
  constructor(...args) {
    this.root = null
    // 初始化依次插入數據
    args.forEach(key => {
      this.insert(key)
    })
  }
  // 實例化
  static create(args) {
    return new BinaryTree(...args)
  }
}

思路：判斷插入的節點和當前節點，若大于當前節點，去右子樹插入，否則左子樹插入。

insert(key) {
  const newNode = new Node(key);
  const insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
      // 如果新節點的值小于老節點的值
      if (node.left === null) {
        // 如果老節點沒有左孩子
        node.left = newNode;
      } else {
        // 如果老節點有左孩子，那么講數據插入到老節點的左孩子
        insertNode(node.left, newNode);
      }
    } else {
      // 如果新節點的值大于老節點
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  };
  if (this.root === null) {
    // 如果root不存在，將newNode設為根節點
    this.root = newNode
  } else {
    insertNode(this.root, newNode)
  }
}

調用形式

const nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
const binaryTree = BinaryTree.create(nodes)
binaryTree.insert(55)
console.log(binaryTree.root)

二叉樹的遍歷(traversing binary tree)是指從根結點出發，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。

首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。

用途：用于復制一顆二叉樹

算法思路
若二叉樹為空，則遍歷結束；否則 1. 訪問根結點 2. 先序遍歷左子樹(遞歸調用本算法) 3. 先序遍歷右子樹(遞歸調用本算法)

// 前序遍歷
preOrderTraverse () {
    const preOrderTraverse = node => {
      if (node !== null) {
        console.log(node.key)
        preOrderTraverse(node.left)
        preOrderTraverse(node.right)
      }
    }
    preOrderTraverse(this.root)
}

首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。簡記左-根-右。

用途：用于從小到大排序二叉樹

算法思路
若二叉樹為空，則遍歷結束；否則 1. 中序遍歷左子樹(遞歸調用本算法) 2. 訪問根結點 3. 中序遍歷右子樹(遞歸調用本算法)

//使用遞歸方式實現中序遍歷
inOrderTraverse () {
    const inOrderTraverseNode = node => {
      if (node !== null) {
        // 如果當前節點非空，則訪問左子樹
        inOrderTraverseNode(node.left)
        // 直到訪問到最底部的左子樹才進入callback，每個節點都會有callback
        console.log(node.key)
        // 此時已經是最底部的左子樹
        inOrderTraverseNode(node.right)
      }
      // 解釋：首先進入8，發現左邊有3，執行左邊遍歷，遍歷完后執行3的回調，在執行3的右邊的回調，
    }
    inOrderTraverseNode(this.root)
}

首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。簡記左-右-根。

算法思路
若二叉樹為空，則遍歷結束；否則 1. 后序遍歷左子樹(遞歸調用本算法)； 2. 后序遍歷右子樹(遞歸調用本算法) ； 3. 訪問根結點 。

postOrderTraverse () {
    const postOrderTraverse = node => {
      if (node !== null) {
        postOrderTraverse(node.left)
        postOrderTraverse(node.right)
        console.log(node.key)
      }
    }
    postOrderTraverse(this.root)
  }

思路：傳入二叉樹，尋找右子樹，直到找到不存在右子樹的節點。

// 查找最大值
max () {
    const maxNode = node => {
      if (node !== null) {
        if (node.right) {
          return maxNode(node.right)
        } else {
          return node.key
        }
      }
    }
    return maxNode(this.root)
}

思路：傳入二叉樹，尋找左子樹，直到找到不存在左子樹的節點。

// 查找最小值
min () {
    const minNode = node => {
      if (node !== null) {
        if (node.left) {
          return minNode(node.left)
        } else {
          return node.key
        }
      }
    }
    return minNode(this.root)
}

思路：根據傳入的 key 與當前節點比較，如果大于當前 key 則去右子樹查找，否則去左子樹查找。

// 查找指定值
search (key) {
  const searchNode = function(node, key) {
    if (node === null) {
      return false
    }
    if (key < node.key) {
      return searchNode(node.left, key)
    } else if (key > node.key) {
      return searchNode(node.right, key)
    } else {
      return true
    }
  }
  return searchNode(this.root, key)
}

思路：如果刪除的 key 小于當前節點，去左子樹種查找，否則去右子樹查找。找到節點后，判斷是否存在子節點，若不存在，直接刪除，若只存在左節點或者右節點，將當前節點替換為它的子節點。若左右節點都存在，將右節點中的最小值（左子樹）移除并替換為刪除的節點位置（為了滿足二叉樹的左子樹小于右子樹）

remove (key) {
  // 用于查找最小節點
  const findMinNode = node => {
    if (node) {
      // 如果node的左孩子存在
      while (node && node.left !== null) {
        // 將node設為node的左孩子再次進入循環
        node = node.left
      }
      // 直到返回沒有左孩子的node
      return node
    }
  }
  const removeNode = (node, key) => {
    if (node === null) {
      return false
    }
    if (key < node.key) {
      // 當前node大于刪除key，去左孩子中查找
      node.left = removeNode(node.left, key)
      return node
    } else if (key > node.key) {
      // 當前node小于刪除key，去右孩子中查找
      node.right = removeNode(node.right, key)
    } else {
      // key和當前node相等
      if (node.left === null && node.right === null) {
        node = null
        return node
      }
      // 任意一邊沒有值，取另一邊
      if (node.left === null) {
        node = node.right
        return node
      } else if (node.right === null) {
        node = node.left
        return node
      }
      // 同時存在左孩子和右孩子
      // 找出右邊的最小值
      const aux = findMinNode(node.right)
      // 將最小值替換為刪除的key
      node.key = aux.key
      // 在右孩子中刪除最小值
      node.right = removeNode(node.right, aux.key)
      return node
    }
  }
  const result = removeNode(this.root, key)
  console.log(result)
}