二叉搜索树 - 图1
    在我们学习过的两种线性结构中：

    数组：在有序的前提下适合查找（二分查找），不适合插入和删除元素；
    链表：适合插入、删除元素，不适合查找。
    二叉树是链表的扩展，再结合二分这种快速查找的特性，诞生了二叉搜索树（Binary Search Tree）。

    二叉搜索树是特殊的二叉树，树的每个结点包含了键（key）、值（value）、数据、左指针（保存了左结点的内存地址）、右指针（保存了右结点的内存地址），在树形结构上维护了元素的有序性。 key 是最重要的部分，key 决定了二叉树的形态。

    二叉搜索树
    二叉搜索树的定义如下：

    一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个 Comparable 的键（以及相关联的值），且每个结点的键都 大于 其左子树中的任意结点的键，而 小于 右子树的任意结点的键。

    说明：

    Comparable 是接口，实现 Comparable 接口的作用是，为 key 添加比较的逻辑。我们的示例代码为了突出算法思想，使用 int 类型作为 key 和 value；
    对于二叉搜索树的定义，《算法导论》第 12 章采用了 「大于等于」和「小于等于」这样的描述，而《算法（第 4 版）》第 3.3 节采用了「大于」和「小于」这样的描述，二者都是人为定义；
    我们教程为了突出算法思想，使用 《算法（第 4 版）》 的定义，即：不允许重复元素，如果遇到了同样的键值，新的关联的值覆盖旧的关联的值，我们后面的代码实现遵守这个约定。大家以后再看相关教程的时候，需要注意二叉搜索树的定义以及上下文理解相关的逻辑；
    带有相同关键字的二叉搜索树可以查阅 《算法导论》第 12 章思考题 12-1 题。

    二叉搜索树的递归定义
    二叉搜索树还可以通过 递归 的方式定义：

    二叉搜索树可以是一棵空树；
    二叉搜索树由根结点，左子树和右子树组成，其中左子树和右子树都是二叉搜索树，并且左子树上所有结点的键值 小于 根结点的键值，并且右子树上所有结点的键值 大于 根结点的键值。
    根据二叉搜索树的定义得到的性质
    由二叉搜索树的定义和中序遍历的定义得到：二叉搜索树中序遍历得到的序列是有序的。

    通过具体例子理解二叉搜索树是如何组织数据
    下面我们通过向二叉搜索树中逐个添加元素，来理解二叉搜索树是如何构建的，进而理解二叉搜索树的组织形式。

    在有序数组里查找元素可以使用二分查找算法，看到了一个元素的值，和目标元素比较：

    如果找到了这个元素，进行相关操作；
    如果目标元素的值 小于 当前看到的元素值，继续向左边查找；
    如果目标元素的值 大于 当前看到的元素值，继续向右边查找。
    二叉搜索树的定义保证了键的有序，向二叉搜索树中插入元素，首先需要查找到插入元素的位置。查找的时候使用类似二分查找的思路：从根结点开始，通过比较 键 决定向左走还是向右走，直到来到叶子结点，即：每次选择子树中的一半，跳过另一半，这是减治思想的应用。

    二叉搜索树查找元素与插入元素是类似的逻辑：在插入元素的时候，意识地维护了有序性，进而在查找元素的时候，可以根据 有序性 查找元素，时间复杂度为 O(\log N)O(logN)，这里 NN 是树结点的个数，\log NlogN 是树的高度的近似值。

    说明：

    按照一定规则插入元素，那么就可以按照同样的规则查找元素，这里的规则就是二叉搜索树的定义。我们在堆（heap）那一章节也是这样介绍堆的，堆中的数据的操作需要符合堆的定义，堆中删除、增加元素需要维护堆的定义。这一点提示我们：在学习算法与数据结构的过程中，定义是非常关键的，理解定义进而思考算法与数据结构设计的思想和来源，是重要的学习方法。
    二叉搜索树与查找表
    查找表（有些教程上也叫符号表），是「键 - 值」对的集合。应用的场景是：按照键查找对应的值。数组是典型的「键 - 值」对的集合，下标是「键（key）」，下标对应的元素是 value。

    简单说：查找表为 key 附带了一个 value 值。

    查找表支持两种操作：

    插入（put）：将一组新的「键 - 值」对插入查找表；
    查找（get）：根据「键」得到对应的「值」，因此需要先在查找表中找到对应的「键」，由于「值」和「键」绑定，找到「键」才能获得对应的值。
    查找表有两种实现：基于有序结构和无序结构。

    有序结构：典型代表是 二叉搜索树 （及其变种 AVL 树、红黑树、B 树、B+ 树）；
    无序结构：典型代表是 哈希表。
    查找表的两种实现对应于我们在排序那一章节提到的基于比较的排序和非比较排序：其中二叉搜索树是基于比较的，而哈希表在底层是数组，「键」存在哪一个位置是由「键」本身决定的，哈希函数会根据「键」，并通过 哈希函数 决定「键 - 值」对存储在数组的什么位置。

    友情提示：查找表是非常常见的数据结构，典型的空间换时间的思想的体现。如果现在不能理解查找表这个概念关系不大，需要在应用的过程中慢慢理解查找表的概念和设计思想。

    二叉搜索树的抽象数据类型

    1. function BinarySearchTree() {
    3.   //节点内部类
    4.   function Node(key) {
    5.     this.key = key
    6.     this.left = null
    7.     this.right = null
    8.   }
    10.   //属性
    11.   this.root = null
    13.   // 插入节点
    14.   var insertNode = function (node, newNode) {
    15.     // 新节点的key小于比较节点
    16.     if (newNode.key < node.key) {
    17.       // 如果左子节点为空，左子节点指向新节点
    18.       if (node.left === null) {
    19.         node.left = newNode;
    20.         // 如果左子节点不为空，就将新节点与左子节点进行比较
    21.       } else {
    22.         // 递归调用比较函数
    23.         insertNode(node.left, newNode);
    24.       }
    25.       // 新节点的key大于比较节点
    26.     } else {
    27.       // 如果右子节点为空，右子节点指向新节点
    28.       if (node.right === null) {
    29.         node.right = newNode;
    30.         // 如果右子节点不为空，就将新节点与右子节点进行比较
    31.       } else {
    32.         // 递归调用比较函数
    33.         insertNode(node.right, newNode);
    34.       }
    35.     }
    36.   };
    38.   BinarySearchTree.prototype.insert = function (key) {
    39.     // 创建一个表示新节点的类
    40.     var newNode = new Node(key);
    42.     // 判断插入的是否为根节点
    43.     if (this.root === null) {
    44.       this.root = newNode;
    45.     } else {
    46.       // 正常节点插入
    47.       insertNode(this.root, newNode); //{3}
    48.     }
    49.   };
    51.   // 先序遍历
    52.   BinarySearchTree.prototype.preOrderTraverse = function (callback) {
    53.     preOrderTraverseNode(this.root, callback);
    54.   };
    56.   var preOrderTraverseNode = function (node, callback) {
    57.     if (node !== null) {
    58.       // 先访问并处理节点本身
    59.       // 然后访问左子节点，最后访问右子节点，每一层节点都是这样
    60.       callback(node.key);
    61.       preOrderTraverseNode(node.left, callback);
    62.       preOrderTraverseNode(node.right, callback);
    63.     }
    64.   };
    66.   //中序遍历
    67.   BinarySearchTree.prototype.inOrderTraverse = function (callback) {
    68.     inOrderTraverseNode(this.root, callback)
    69.   }
    71.   var inOrderTraverseNode = function (node, callback) {
    72.     if (node !== null) {
    73.       //1.遍历左子树中的节点,这里会层层遍历
    74.       // 直到找到最小值，对最小值执行callback方法
    75.       inOrderTraverseNode(node.left, callback)
    77.       //2.处理节点
    78.       callback(node.key)
    80.       //3.遍历右子树中的节点
    81.       inOrderTraverseNode(node.right, callback)
    82.     }
    83.   }
    85.   // 后序遍历
    86.   BinarySearchTree.prototype.postOrderTraverse = function (callback) {
    87.     postOrderTraverseNode(this.root, callback);
    88.   };
    90.   var postOrderTraverseNode = function (node, callback) {
    91.     if (node !== null) {
    92.       postOrderTraverseNode(node.left, callback);
    93.       postOrderTraverseNode(node.right, callback);
    94.       callback(node.key);
    95.     }
    96.   };
    98.   // 最小值就是左边的最下层
    99.   BinarySearchTree.prototype.min = function () {
    100.     return minNode(this.root);
    101.   };
    103.   var minNode = function (node) {
    104.     if (node) {
    105.       while (node && node.left !== null) {
    106.         node = node.left;
    107.       }
    108.       return node.key;
    109.     }
    110.     return null;
    111.   };
    113.   // 最大值就是右边的最下层
    114.   BinarySearchTree.prototype.max = function () {
    115.     return maxNode(this.root);
    116.   };
    117.   var maxNode = function (node) {
    118.     if (node) {
    119.       while (node && node.right !== null) {
    120.         node = node.right;
    121.       }
    122.       return node.key;
    123.     }
    124.     return null;
    125.   };
    127.   //查找特定的key
    128.   BinarySearchTree.prototype.search = function (key) {
    129.     //1.获取根节点
    130.     let node = this.root
    132.     //2.循环搜索key
    133.     while (node != null) {
    134.       if (key < node.key) {
    135.         //小于根(父)节点就往左边找
    136.         node = node.left
    137.         //大于根(父)节点就往右边找
    138.       } else if (key > node.key) {
    139.         node = node.right
    140.       } else {
    141.         return true
    142.       }
    143.     }
    144.     return false
    145.   }
    147.   //删除节点
    148.   BinarySearchTree.prototype.remove = function (key) {
    149.     //定义变量current保存删除的节点，parent保存它的父节点。isLeftChild保存current是否为parent的左节点
    150.     let current = this.root
    151.     let parent = null
    152.     let isLeftChild = true
    154.     //开始寻找删除的节点
    155.     while (current.key != key) {
    156.       parent = current
    157.       // 小于则往左查找
    158.       if (key < current.key) {
    159.         isLeftChild = true
    160.         current = current.left
    161.       } else {
    162.         isLeftChild = false
    163.         current = current.right
    164.       }
    165.       //找到最后依然没有找到相等的节点
    166.       if (current == null) {
    167.         return false
    168.       }
    169.     }
    170.     //结束while循环后：current.key = key，parent指向其父节点
    172.     //情况1：删除的是叶子节点(没有子节点)
    173.     if (current.left == null && current.right == null) {
    174.       // 如果是根节点
    175.       if (current == this.root) {
    176.         this.root = null
    177.         // 判断是父节点的左子节点还是右子节点，并删除
    178.       } else if (isLeftChild) {
    179.         parent.left = null
    180.       } else {
    181.         parent.right = null
    182.       }
    183.     }
    185.     //情况2：删除的节点有一个子节点
    186.     //当current只存在左子节点时
    187.     else if (current.right == null) {
    188.       // 如果删除的是根节点
    189.       if (current == this.root) {
    190.         this.root = current.left
    191.         // 判断删除的是父节点的左子节点还是右子节点
    192.       } else if (isLeftChild) {
    193.         parent.left = current.left
    194.       } else {
    195.         parent.right = current.left
    196.       }
    197.       //当current只存在右子节点时
    198.     } else if (current.left == null) {
    199.       // 判断是否是根节点
    200.       if (current == this.root) {
    201.         this.root = current.right
    202.         // 判断删除的是父节点的左子节点还是右子节点
    203.       } else if (isLeftChild) {
    204.         parent.left = current.right
    205.       } else {
    206.         parent.right = current.right
    207.       }
    208.     }
    210.     //情况3：删除的节点有两个子节点
    211.     else {
    212.       //1.获取后继节点
    213.       let successor = getSuccessor(current)
    215.       //2.判断是否根节点
    216.       if (current == this.root) {
    217.         this.root = successor
    218.         // 判断删除的是父节点的左子节点还是右子节点
    219.       } else if (isLeftChild) {
    220.         parent.left = successor
    221.       } else {
    222.         parent.right = successor
    223.       }
    225.       //3.将后继的左子节点改为被删除节点的左子节点
    226.       successor.left = current.left
    227.     }
    228.   }
    230.   //封装查找后继的方法
    231.   var getSuccessor = function (delNode) {
    232.     //1.定义变量,保存找到的后继
    233.     let successor = delNode
    234.     let successorParent = delNode
    235.     let current = delNode.right
    237.     //2.循环查找current的右子树的左子节点，直到找到最小值
    238.     while (current != null) {
    239.       successorParent = successor
    240.       successor = current
    241.       current = current.left
    242.     }
    244.     //3.判断寻找到的后继节点是否直接就是删除节点的right节点
    245.     // 如果是右子树的最小子节点，就对其进行处理
    246.     // 它的父节点指向它的右子节点，它的右子节点指向删除节点的右子节点
    247.     if (successor != delNode.right) {
    248.       successorParent.left = successor.right
    249.       successor.right = delNode.right
    250.     }
    251.     // 返回它，用于 删除节点的父节点指向它
    252.     return successor
    253.   }
    254. }