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

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

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

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

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

// 創(chuàng)建節(jié)點
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

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

思路：判斷插入的節(jié)點和當(dāng)前節(jié)點，若大于當(dāng)前節(jié)點，去右子樹插入，否則左子樹插入。

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

調(diào)用形式

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)是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。

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

用途：用于復(fù)制一顆二叉樹

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

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

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

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

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

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

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

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

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

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

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

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

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

思路：根據(jù)傳入的 key 與當(dāng)前節(jié)點比較，如果大于當(dāng)前 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 小于當(dāng)前節(jié)點，去左子樹種查找，否則去右子樹查找。找到節(jié)點后，判斷是否存在子節(jié)點，若不存在，直接刪除，若只存在左節(jié)點或者右節(jié)點，將當(dāng)前節(jié)點替換為它的子節(jié)點。若左右節(jié)點都存在，將右節(jié)點中的最小值（左子樹）移除并替換為刪除的節(jié)點位置（為了滿足二叉樹的左子樹小于右子樹）

remove (key) {
  // 用于查找最小節(jié)點
  const findMinNode = node => {
    if (node) {
      // 如果node的左孩子存在
      while (node && node.left !== null) {
        // 將node設(shè)為node的左孩子再次進(jìn)入循環(huán)
        node = node.left
      }
      // 直到返回沒有左孩子的node
      return node
    }
  }
  const removeNode = (node, key) => {
    if (node === null) {
      return false
    }
    if (key < node.key) {
      // 當(dāng)前node大于刪除key，去左孩子中查找
      node.left = removeNode(node.left, key)
      return node
    } else if (key > node.key) {
      // 當(dāng)前node小于刪除key，去右孩子中查找
      node.right = removeNode(node.right, key)
    } else {
      // key和當(dāng)前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)
}