复习 树和二叉树

1. 树的定义

• 树是是由n（n >= 0）各结点构成的有限集合，是一种一对多的数据结构
• 当 n = 0 时，称为空树
• 当 n > 0 时，称为非空树，具备以下性质
  • 有且仅有一个特殊的结点，这个结点称为根节点
  • 其余结点可分为m（m >= 0）个互不相交的有限集合，其中每一个集合本身又是一颗树，并叫做树的子树

2. 树的基本术语

3. 二叉树(**)

1. 定义

• 由 n（n >= 0）个结点组成的有限集合

二叉树不是树的特殊情况，完全是两个概念。因为二叉树子树有左右之分而树没有，并且不可颠倒顺序

• 当n = 0时，空树
• 当n > 0时，就是由一个根节点和以及两颗互不相交的分别称为其左子树和右子树的二叉树构成

2. 特点

• 每个结点最多有两个孩子
• 子树有左右之分，不可颠倒顺序
• 第 i 层最大结点数为：2^(i-1)
• 深度为k的二叉树有最大节点树为：2^(k) - 1
• 对于任何非空的二叉树，若n表示叶子节点的个数，m表示度为2的非叶子结点个数，则 n = m + 1

3. 二叉树的五种形态

空二叉树，只有一个根节点，只有一个根节点和左子树，只有一个根节点和右子树，一个根节点和左右两个子树

4. 特殊的二叉树

• 完美二叉树：又叫满二叉树，除最下层叶子结点外，每层的每个结点都有两个子节点；或深度为k且有 2^(k) - 1个节点的二叉树称为满二叉树
• 完全二叉树：完美二叉树就是特殊的完全二叉树；除二叉树最后一层结点外，每层的节点数都达到最大值；且最后一层从左向右的节点连续存在，只缺右侧若干个结点；性质：具有 n各节点的完全二叉树的深度为 [log n] + 1
• 二叉搜索(排序)(查找)树(BST)：查找、删除、插入效率非常高，
  • 非空左子树所有键值小于根节点的键值
  • 非空右子树所有键值大于根节点的键值
  • 其左右子树也是一个二叉搜索树

5. 二叉树的存储

P82(1) p84(2)；常见的存储方式是顺序存储-----数组（不推荐）和链式存储------链表（推荐），一般我们使用的是用链表来存储二叉树，每个节点由三部分组成（二叉链表）：左子节点的引用，右子节点的引用，自己本身的数据

6. 二叉树的遍历

• 遍历

  • 常见的四种遍历方法

    1. 先序遍历

       • 访问根节点

       • 先序遍历其左子树

       • 先序遍历其右子树

    2. 中序遍历

       • 中序遍历其左子树

       • 访问根节点

       • 中序遍历其右子树

    3. 后序遍历

       • 后序遍历其左子树
       • 后序遍历其右子树
       • 访问根节点

    4. 层次遍历

  • 代码实现（使用递归）

  //  先序遍历
    BinarySearchTree.prototype.preOrderTraversal = (node, handle) => {
      if (node === null) return console.log('此二叉树为空')
      handle(node)
      if (node.leftChild) this.preOrderTraversal(node.leftChild, handle)
      if (node.rightChild) this.preOrderTraversal(node.rightChild, handle)
    }
  
  //  中序遍历
    BinarySearchTree.prototype.midOrderTraversal = (node, handle) => {
      if (node === null) return console.log('此二叉树为空')
      if (node.leftChild) this.midOrderTraversal(node.leftChild, handle)
      handle(node)
      if (node.rightChild) this.midOrderTraversal(node.rightChild, handle)
    }
  
  //  后序遍历
  
    BinarySearchTree.prototype.postOrderTraversal = (node, handle) => {
      if (node === null) return console.log('此二叉树为空')
      if (node.leftChild) this.postOrderTraversal(node.leftChild, handle)
      if (node.rightChild) this.postOrderTraversal(node.rightChild, handle)
      handle(node)
    }
  

  • 通过遍历的结果推出二叉树（先序和中序，中序和后序）
  • 遍历算法的应用
    1. 二叉树的建立
    2. 复制二叉树

7.二叉搜索树的封装

function BinarySearchTree() {
  // 1. 相关属性和方法

  /**
   * 根节点
   */
  this.root = null

  /**
   * @name: Node
   * @msg: 生成节点函数
   * @param {*} key 键值
   * @param {*} value 值
   * @return {*}
   */
  function Node(key, value) {
    this.key = key
    this.value = value
    /**
     * 左子节点
     */
    this.leftChild = null
    /**
     * 右子节点
     */
    this.rightChild = null
  }

  // 插入节点
  BinarySearchTree.prototype.insert = (key, value) => {
    const newNode = new Node(key, value)
    const insertNode = (newNode, oldNode) => {
      const {key, leftChild, rightChild} = oldNode
      if (newNode.key < key) {
        if (leftChild === null) {
          oldNode.leftChild = newNode
        } else {
          insertNode(newNode, oldNode.leftChild)
        }
      } else {
        if (rightChild === null) {
          oldNode.rightChild = newNode
        } else {
          insertNode(newNode, oldNode.rightChild)
        }
      }
    }
    if (this.root === null) {
      this.root = newNode
    } else {
      insertNode(newNode, this.root)
    }
  }


  // 获得节点和其父节点
  BinarySearchTree.prototype.getNode = key => {
    let parentNode = this.root
    const search = (key, node) => {
      if (node === null) return null
      if (node.key === key) return node
      parentNode = node
      if (key > node.key) return search(key, node.rightChild)
      if (key <= node.key) return search(key, node.leftChild)
    }
    return {
      currentNode: search(key, this.root),
      parentNode,
    }
  }

//查询二叉树是否有某个节点，这个函数多余，getNode函数可以替代这个函数，TODO: 尝试用while循环来做
  BinarySearchTree.prototype.hasNode = key => {
    const search = (key, node) => {
      if (node === null) return false
      if (node.key === key) return true
      if (key > node.key) return search(key, node.rightChild)
      if (key <= node.key) return search(key, node.leftChild)
    }
    return search(key, this.root)
  }

// 修改节点数据
  BinarySearchTree.prototype.updateNode = (key, value) => {
    const node = this.getNode(key)
    if (node === null) return false
    node.value = value
    return true
  }

  // 寻找被删除节点的后继
  BinarySearchTree.prototype.getSuccessor = (delNode) => {
    let successor = delNode.rightChild
    let successorParent = delNode
    while (successor.leftChild) {
      successorParent = successor
      successor = successor.leftChild
    }
    if (successor !== delNode.rightChild) {
      successorParent.leftChild = successor.rightChild
      successor.rightChild = delNode.rightChild
    }
    return successor
  }

//删除节点
  BinarySearchTree.prototype.remove = key => {
    if (!this.hasNode(key)) return false
    /**
     * currentNode：当前被删除节点
     * parentNode：当前被删除节点的父节点
     */
    const {currentNode, parentNode} = this.getNode(key)
    // 1. currentNode 是根节点，并且根节点没有左右子节点
    if (currentNode === this.root && !currentNode.leftChild && !currentNode.rightChild) {
      this.root = null
      return true
    }
    // 2.  leftChild === null   rightChild === null 则表明删除的是叶子结点
    if (!currentNode.leftChild && !currentNode.rightChild) {
      //  判断是currentNode 是 parentNode 的左子节点还是右子节点
      if (currentNode === parentNode.leftChild) {
        parentNode.leftChild = null
      } else {
        parentNode.rightChild = null
      }
    }
    //  3.  currentNode 具有左子节点，但没有右子节点
    else if (currentNode.leftChild && !currentNode.rightChild) {
      if (currentNode === this.root) { // 删除的节点是根节点，并且根节点只有左子节点
        this.root = currentNode.leftChild
      } else if (currentNode === parentNode.leftChild) { // 删除的节点是其父节点的左子节点
        parentNode.leftChild = currentNode.leftChild
      } else { // 删除的节点是其父节点的右子节点
        parentNode.rightChild = currentNode.leftChild
      }
    }
    //  4.  currentNode 具有右子节点，但没有左子节点
    else if (!currentNode.leftChild && currentNode.rightChild) {
      if (currentNode === this.root) { // 删除的节点是根节点，并且根节点只有右子节点
        this.root = currentNode.rightChild
      } else if (currentNode === parentNode.leftChild) { // 删除的节点是其父节点的左子节点
        parentNode.leftChild = currentNode.rightChild
      } else { // 删除的节点是其父节点的右子节点
        parentNode.rightChild = currentNode.rightChild
      }
    }
    // 5.  currentNode 具有左右节点(**)
    else {
      //  获取当前被删除节点的后继节点
      const successor = this.getSuccessor(currentNode)
      //  如果当前被删除节点是根节点
      if (currentNode === this.root) {
        this.root = successor
      }
      //  如果当前被删除节点是 其父节点的左子节点
      else if (currentNode === parentNode.leftChild) {
        parentNode.leftChild = successor
      }
      //  如果当前被删除节点是 其父节点的右子节点
      else {
        parentNode.rightChild = successor
      }
      successor.leftChild = currentNode.leftChild
    }
    return true
  }

// 遍历节点：先序遍历，中序遍历，后序遍历

//  先序遍历
  BinarySearchTree.prototype.preOrderTraversal = (node, handle) => {
    if (node === null) return console.log('此二叉树为空')
    handle(node)
    if (node.leftChild) this.preOrderTraversal(node.leftChild, handle)
    if (node.rightChild) this.preOrderTraversal(node.rightChild, handle)
  }


//  中序遍历
  BinarySearchTree.prototype.midOrderTraversal = (node, handle) => {
    if (node === null) return console.log('此二叉树为空')
    if (node.leftChild) this.midOrderTraversal(node.leftChild, handle)
    handle(node)
    if (node.rightChild) this.midOrderTraversal(node.rightChild, handle)
  }
//
//  后序遍历
  BinarySearchTree.prototype.postOrderTraversal = (node, handle) => {
    if (node === null) return console.log('此二叉树为空')
    if (node.leftChild) this.postOrderTraversal(node.leftChild, handle)
    if (node.rightChild) this.postOrderTraversal(node.rightChild, handle)
    handle(node)
  }

//  找最大值，最小值
  BinarySearchTree.prototype.getMax = () => {
    if (this.root === null) return null
    let currentNode = this.root
    while (currentNode.rightChild) {
      currentNode = currentNode.rightChild
    }
    return currentNode
  }

  BinarySearchTree.prototype.getMin = () => {
    if (this.root === null) return null
    let currentNode = this.root
    while (currentNode.leftChild) {
      currentNode = currentNode.leftChild
    }
    return currentNode
  }
}

// test
const tree = new BinarySearchTree()
tree.insert(10, 10)
tree.insert(11, 11)
tree.insert(3, 3)
tree.insert(5, 5)
tree.insert(12, 12)
tree.insert(16, 16)
tree.insert(2, 2)
tree.insert(4, 4)
tree.insert(13, 13)
tree.insert(9, 9)
tree.insert(18, 18)
tree.insert(1, 1)
// console.log(tree)
const {currentNode} = tree.getNode(12)
console.log(tree.getSuccessor(currentNode))

8. 红黑树

为什么会出现红黑树？

先看一下如下这颗二叉搜索树

左边有7个节点而右边只有一个节点，如果不看右边那一个节点，这颗二叉树基本上等同于就是一个链表了，查找效率变成了O(n)。我们知道二叉搜索树对于删除查找插入效率比较高，但是如果出现上图这种情况，二叉搜索树的优势根本就没有体现出来，所以需要对上图二叉搜索树作出改进

所以我们需要对上图的二叉搜索树作出改进，使得左右两颗子树的节点分布均匀，像这种左子树的子孙结点尽可能的等于右子树的子孙节点的二叉树称为平衡二叉树树。

红黑树就是一种平衡二叉树

一颗红黑树需要满足如下规则：

1. 节点的颜色是黑色或红色
2. 根节点是黑色
3. 每个叶子节点的都是黑色的空节点（在红黑树中，有数据的节点不会作为叶子结点）
4. 每个红色节点的两个子节点都是黑色（即从叶子节点到根节点的所有路径上不会出现2个连续的红色节点）
5. 任意一个节点到其每一个叶子节点的所有路径都包含相同数目的黑色节点

红黑树的平很规则就是：从根节点到叶子节点的最长路径不会超过最短路径的2倍长

如下图，这就是一颗红黑树，符合了如上规则

那么一颗红黑树在插入、删除节点是如何保持平衡的呢？

红黑树通常用的是变色和旋转两种操作

1. 变色：为了符合红黑树的规则，红色和黑色需要进行交换

一般插入的节点取红色更好（比较容易调整），如果插入节点是黑色的话很容易就会不符合规则5

2. 旋转

   1. 左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己右孩子取代，而旧的父节点成为新的父节点的左孩子
   2. 右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而旧的父节点成为新的父节点的右孩子

   

   下面讲讲红黑树插入节点时如何进行变换

   先做如下规定：插入的节点是红色，插入的节点为N，其父节点为P，其爷节点为G，其父亲的兄弟节点为U；有如下五种情况：

   1. N位于树的根上，没有父节点（即树为空），此时：变色，让该节点从红色变为黑色
   2. P节点是黑色节点，此时：直接插入
   3. P为红色节点，U也是红色节点，此时：变色，U和P节点都变为黑色，G变为红色

   

   4. U是黑色节点，P红色，G是黑色，N是左孩子，此时：先变色，P变为黑色，G变为红色，然后右旋转（以G作为‘父节点’）

5. P红，U黑，G黑，N为右孩子，此时：先左旋转（以P作为‘父节点’），然后将P，B看做一个整体，作为一个新插入的节点N，原来的N节点看做P，此时符合情况四，依据情况四进行变化，最后还原

9. 哈夫曼树(最优二叉树)

• 定义：带权路径长度最短的二叉树

节点的带权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积

树的带权路径长度：树中所有叶子结点的带权路径长度之和

• 如何构造一颗哈夫曼树（哈夫曼算法）

  1. 构造森林全是根：根据n个给定的权值构成n颗二叉树的森林，其中每一棵树都只有一个带权的根节点构成
  2. 选用两小造新树：从森林中选取两颗根节点权值最小的树作为左右子树，构造成一颗新的二叉树，这颗新的二叉树的根节点的权值就是左右节点的权值之和
  3. 删除两小添新树：从森林中删除这两棵树，将这颗新树添加进去
  4. 重复2，3操作，直到森林中只有一颗二叉树为止，这颗二叉树就是哈夫曼树

10 . 树 —> 二叉树

在兄弟之间加一连线，对每个节点，除了其左孩子外，去除其与其与孩子之间的关系，以树的根节点为轴心，将整棵树顺时针转45度