【Day15】[资料结构]-二元搜寻树Binary Search Tree, BST

二元搜寻树(Binary Search Tree)，也称有序/排序二元树，是一种特殊二元树结构，而节点资料的排序具备一些特性。

特性如下

• 左子树任一节点的值一定小於根节点的值。
• 右子树任一节点的值一定大於根节点的值。
• 任一节点的左、右子树也分别为二元搜寻树。
• 每一个节点不能出现重复的资料。

如下面这棵树，就是一棵合法的BST

下面这棵树就不是一棵合法的BST，虽然节点11大於8是合法，大於6也是合法的。但是不能大於10这个节点。毕竟11这个节点还是属於10节点的左子树。因此不是一棵合法的二元搜寻树。

新增节点

若目标值小於节点的值，则前往左子树；若目标值大於节点的值，则前往右子树；

搜寻节点

若目标值小於节点的值，则继续在左子树中搜寻；若目标值大於节点的值，则继续在右子树中搜寻；

删除节点

需要考虑节点的三种情况

• 叶子节点（无子树），直接删除。
  
• 节点有单边子树，用子树代替该节点。
  
• 节点有左右两边子树，左子树取最大值，右子树取最小值。