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

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

二叉樹(shù)的第 i 層上最多有 2 的(i-1)方個(gè)節(jié)點(diǎn)。（i>=1）

深度為 k 的樹(shù)最多有 2 的 k 次方-1 個(gè)節(jié)點(diǎn)。（k>=1）

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

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

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

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

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

二叉樹(shù)的遍歷(traversing binary tree)是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。簡(jiǎn)記根-左-右。

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

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

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

首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。簡(jiǎn)記左-根-右。

用途：用于從小到大排序二叉樹(shù)

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

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

首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。簡(jiǎn)記左-右-根。

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

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

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

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

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

// 查找最小值
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é)點(diǎn)比較，如果大于當(dāng)前 key 則去右子樹(shù)查找，否則去左子樹(shù)查找。

// 查找指定值
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é)點(diǎn)，去左子樹(shù)種查找，否則去右子樹(shù)查找。找到節(jié)點(diǎn)后，判斷是否存在子節(jié)點(diǎn)，若不存在，直接刪除，若只存在左節(jié)點(diǎn)或者右節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)替換為它的子節(jié)點(diǎn)。若左右節(jié)點(diǎn)都存在，將右節(jié)點(diǎn)中的最小值（左子樹(shù)）移除并替換為刪除的節(jié)點(diǎn)位置（為了滿(mǎn)足二叉樹(shù)的左子樹(shù)小于右子樹(shù)）

remove (key) {
  // 用于查找最小節(jié)點(diǎn)
  const findMinNode = node => {
    if (node) {
      // 如果node的左孩子存在
      while (node && node.left !== null) {
        // 將node設(shè)為node的左孩子再次進(jìn)入循環(huán)
        node = node.left
      }
      // 直到返回沒(méi)有左孩子的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
      }
      // 任意一邊沒(méi)有值，取另一邊
      if (node.left === null) {
        node = node.right
        return node
      } else if (node.right === null) {
        node = node.left
        return node
      }
      // 同時(shí)存在左孩子和右孩子
      // 找出右邊的最小值
      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)
}