二叉树

二叉树

+ 特性

• 一个二叉树第i层的最大节点树为： ==2^(i-1)==, i >= 1;

• 深度为K的二叉树有最大节点总数为：==2^k - 1==, k >= 1;

• 对任何非空二叉树T，若n0表示叶节点的个数、n2是度为2的非叶节点个数，

  那么两者满足关系n0 = n2 + 1;

二叉搜索树

（BST， Binary Search Tree）,也叫二叉排序树，或二叉查找树

• 二又搜索树是一颗二叉树，可以为空;
• 如果不为空，满足以下==性质==
  • 非空==左子树==的所有键值==小于==其==根节点==的键值
  • 非空==右子树==的所有键值==大于==其==根节点==的键值
• 左、右子树本身也都是二叉搜索树


特点：

• 相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。
• 查找效率非常高，这也是二又搜索树中，搜索的来源

+ 二叉搜索树作为数据存储有重要优势：

可以快速地找到给定关键字的数据项并且可以快速地插入和删除数据项.

+ 问题

如果插入的数据是有序的数据，树的深度会很大，反而影响效率；

树的遍历

适用于所有二叉树

• 先序遍历

  • 
  • 1.访问根节点
  • 2.遍历其左子树
  • 3.遍历其右子树

• 中序遍历

  • 
  • 1.遍历其左子树
  • 2.访问根节点
  • 3.遍历其右子树

• 后序遍历

  • 
  • 1.遍历其左子树
  • 2.遍历其右子树
  • 3.访问根节点

二叉搜索树-封装

属性：node

key: 键

left：左子节点

right：右子节点

方法：

1. insert ()：向树中插入一个新的键;

2. search (key)：搜索特定的节点（值），存在返回true，否则返回false;

3. midOrderTraversal ()：通过中序遍历方式遍历所有节点，根节点在中间时遍历

4. preOrderTraversal ()：通过先序遍历方式遍历所有节点：

   根节点最先遍历：从上到左 -> 从左到右 -> 从子到父

5. postOrderTraversal ()：通过后序遍历方式遍历所有节点，最后遍历根节点

6. min ()：返回树中最小的值/键。一直往左节点查找

7. max ()：返回树中最大的值/键

8. remove (key)：从树中移除某个节点

/***************  二叉搜索树的封装 ***********/

	/**
   *             11
   *        7             15
   *    5      9      13      20
   *  3   6  8  10  12  14  18  25
   */

function BinarySearchTree() {

  function Node(key) {
    this.key = key;
    this.left = null
    this.right = null;
  }

  this.root = null;

  /**
     * @description 向树中插入一个新的键
     * 
     * 思路：
     * 1.从根节点开始查找，大于该节点，往右查找；小于该节点，往左查找；
     * 2.直到 被计较的 节点为空，则在该位置插入新节点；
     * 
     */
  BinarySearchTree.prototype.insert = function (key) {
    // 1.创建节点
    const newNode = new Node(key);

    // 2.判断是否存在根节点
    if (this.root == null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }

  }

  /**
     * @description 内部调用的方式，不对外暴露
     * @node 被计较的节点
     * @newNode 要插入的节点
     * 
     */
  BinarySearchTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) { // 向左查找
      if (node.left == null) { // 左边节点不存在，直接插入
        node.left = newNode;
      } else { // 左边节点不为空，继续进行比较
        this.insertNode(node.left, newNode);
      }

    } else { // 向右查找
      if (node.right == null) {
        node.right = newNode;
      } else { // 右边节点不为空，继续进行比较
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 通过中序遍历方式遍历所有节点，根节点在中间时遍历
  BinarySearchTree.prototype.midOrderTraversal = function (handler) {
    this.midOrderTraversalNode(this.root, handler);
  }

  BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      // 1.处理经过节点的 左子节点
      this.preOrderTraverseNode(node.left, handler);

      // 2.处理经过的节点
      handler(node.key);

      // 3.处理经过节点的 右子节点
      this.preOrderTraverseNode(node.right, handler);
    }
  }

  // 通过先序遍历方式遍历所有节点：根节点最先遍历：从上到左 -> 从左到右 -> 从子到父
  BinarySearchTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTraverseNode(this.root, handler);
  }

  BinarySearchTree.prototype.preOrderTraverseNode = function (node, handler) {
    if (node !== null) {
      // 1.处理经过的节点
      handler(node.key);

      // 2.处理经过节点的 左子节点
      this.preOrderTraverseNode(node.left, handler);

      // 3.处理经过节点的 右子节点
      this.preOrderTraverseNode(node.right, handler);
    }
  }

  // 通过后序遍历方式遍历所有节点，最后遍历根节点
  BinarySearchTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler);
  }

  BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      // 1.处理经过节点的 左子节点
      this.postOrderTraversalNode(node.left, handler);

      // 2.处理经过节点的 右子节点
      this.postOrderTraversalNode(node.right, handler);

      // 3.处理经过的节点
      handler(node.key);
    }
  }

  // 返回树中最小的值/键：一直往左节点查找
  BinarySearchTree.prototype.min = function () {
    let node = this.root;
    while (node.left !== null) {
      node = node.left;
    }
    return node.key;
  }

  // 返回树中最大的值/键
  BinarySearchTree.prototype.max = function () {
    let node = this.root;
    while (node.right !== null) {
      node = node.right;
    }
    return node.key;
  }

  // 搜索特定的节点（值）
  BinarySearchTree.prototype.search = function (key) {

    // 一、循环方式
    // 结束循环条件 node === null

    // 1.获取根节点
    let node = this.root;

    // 2.遍历所有节点
    while (node) {
      if (key < node.key) { // 向左查找
        node = node.left;
      } else if (key > node.key) { // 向右查找
        node = node.right;
      } else {
        return true;
      }
    }
    return false;


    // 二、递归方式
    // return this.searchNode(this.root, key)
  }

  // 退出递归的条件：
  // 1.当前节点为null, node === null; 
  // 2.找到了key，node.key === key;
  BinarySearchTree.prototype.searchNode = function (node, key) {

    if (node === null) {
      return false;
    }

    if (key < node.key) { // 向左查找
      return this.searchNode(node.left, key);
    } else if (key > node.key) { // 向右查找
      return this.searchNode(node.right, key);
    } else {
      return true;
    }

  }

  /**
     * @description 从树中移除某个节点
     * 
     * 1.找到要删除的节点，如果没有找到，不进行删除操作
     * 2.如果找到了，则分为如下 三种情况：
     * 
     * 一、没有子节点：叶节点
     * 1.检测 当前节点的 left & right === null
     * 2.都为null之后，检测是否为 根节点，如果是，则清空二叉树
     * 3.如果不是根节点，将父节点的 left 或者 right 设置为null 即可
     * 
     * 二、只有一个子节点
     * 
     * 三、有两个子节点
     * 
     */

  BinarySearchTree.prototype.remove = function (key) {
    // 1.寻找要删除的节点

    // 1.1 保存当前节点，要删除的节点的父节点
    let currentNode = this.root;
    let parentNode = null;
    let isLeftChild = true;

    // 1.2 遍历查找
    while (currentNode.key !== key) {
      parentNode = currentNode;

      if (key < currentNode.key) { // 向左查找
        isLeftChild = true;
        currentNode = currentNode.left;
      } else { // 向右查找
        isLeftChild = false;
        currentNode = currentNode.right;
      }

      // 直到遍历到了最后的节点，依然没有找到 == key 的节点
      if (currentNode === null) return false;
    }

    // 2.根据对应的情况删除节点
    // 2.1 删除的节点是叶子节点
    if (currentNode.left === null && currentNode.right === null) {
      if (currentNode === this.root) {
        this.root = null;
      } else if (isLeftChild) {
        parentNode.left = null;
      } else {
        parentNode.right = null;
      }
    }

    // 2.2 删除的节点有一个子节点
    /**
       *             11
       *        7             15
       *    5      9      13      20
       *  3  6   8  10  12  14  18  25
       */

    // 2.2.1 当前节点在左节点，currentNode.left === parentNode.left;(例如：5)
    // left:  parentNode.left = currentNode.left;（有3无6的情况）
    // right: parentNode.left = currentNode.right;（有6无3的情况）

    else if (currentNode.right === null) {
      // 当前节点为根节点，父节点为null
      if (currentNode === this.root) {
        this.root = currentNode.left;
      } else if (isLeftChild) {
        parentNode.left = currentNode.left; // （有3无6的情况）
      } else {
        parentNode.right = currentNode.left; // （有8无10的情况）
      }
    }

    // 2.2.2 当前节点在右节点，currentNode.right === parentNode.right;(例如：9)
    // left:  parentNode.right = currentNode.left;（有8无10的情况）
    // right: parentNode.right = currentNode.right;（有10无8的情况）
    else if (currentNode.left === null) {
      // 当前节点为根节点，父节点为null
      if (currentNode === this.root) {
        this.root = currentNode.right;
      } else if (isLeftChild) {
        parentNode.left = currentNode.right; // （有6无3的情况）
      } else {
        parentNode.right = currentNode.right; // （有10无8的情况）
      }
    }


    /**
       *             11
       *        7             15
       *    5      9      13      20
       *  3      8  10  12  14  18  25
       *                          19
       * 
       * 19连着18连着20
       */

    // 2.3 删除的节点有两个子节点
    // 情况一：删除节点9，任选8或者10放到原本9的位置

    // 情况二：删除节点7
    // - 方案一：左边：将5移到7的位置，3移到原本5的位置；
    // - 方案二：右边：将8放到7的位置

    // 情况三：删除节点15
    // - 方案一：左边：将14放到15的位置
    // - 方案二：右边：将18放到15的位置，19移到原本18的位置；

    // 规律 & 思路
    // + 如果我们要删除的节点有两个子节点甚至子节点还有子节点,
    // 这种情况下我们需要从下面的子节点中找到个节点,来替换当前的节点

    // + 但是找到的这个节点有什么特征呢?应该是 current节点下面所有节点中最接近 current节点的
    // - 要么比 current节点小一点点要么比 current节点大一点点
    // - 总之你最接近 current,你就可以用来替换 current的位置.

    // + 这个节点怎么找呢？
    // - 比 current小一点点的节点一定是 current左子树的最大值
    // - 比 current大一点点的节点一定是 current右子树的最小值

    // + 前驱&后继
    // - 在二叉搜索树中,这两个特别的节点有两个特别的名字
    // - 比 current小一点点的节点称为 current节点的前区
    // - 比 current大一点点的节点称为 current节点的后继

    // + 也就是为了能够删除有两个子节点的α urrent,要么找到它的前驱,要么找到它的后继.
    // + 所以接下来,我们先找到这样的节点(前驱或者后继都可以我这里以找后继为例)

    else {
      // 1.获取后继节点
      let successor = this.getSuccssor(currentNode)

      // 2.判断是否为根节点
      if (currentNode === this.root) {
        this.root = successor;
      }

    }

  }

  // 找到后继
  BinarySearchTree.prototype.getSuccssor = function (delNode) {
    // 1.定义变量，，保存找到的后继
    let successor = delNode;
    let current = delNode.right;

    // 2.循环查找
    while (current !== null) {
      successor = current;
      current = current.left;
    }

    return successor;
  }
}

测试用例：

/**
   * 删除用的
   *             11
   *        7             15
   *    5      9      13      20
   *     6   8  10  12  14  18  25
   */
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
bst.insert(19);

// 测试先序遍历
let resultString1 = "";
bst.preOrderTraversal(function (key) {
  resultString1 += key + ' '
});

console.log('先序遍历：', resultString1)

// 测试中序遍历
let resultString2 = "";
bst.midOrderTraversal(function (key) {
  resultString2 += key + ' '
});

console.log('先序遍历：', resultString2)

// 测试后续序遍历
let resultString3 = "";
bst.postOrderTraversal(function (key) {
  resultString3 += key + ' '
});

console.log('后序遍历：', resultString3)

console.log('最小值：', bst.min())
console.log('最大值：', bst.max())

console.log('是否存在 key = 3 的节点', bst.search(3));
console.log('是否存在 key = 9 的节点', bst.search(9));
console.log('是否存在 key = 13 的节点', bst.search(13));
console.log('是否存在 key = 18 的节点', bst.search(18));
console.log('是否存在 key = 21 的节点', bst.search(21));

console.log('删除6', bst.remove(6), bst)
// console.log('删除3', bst.remove(3), bst)
// console.log('删除5', bst.remove(5), bst)