什么是二叉搜索树
二叉搜索树（Binary Search Tree，BST）是一种特殊类型的二叉树，它具有以下性质：
每个节点最多有两个子节点，分别称为左子节点和右子节点。
对于任意节点，其左子树中的所有节点的值都小于该节点的值。
对于任意节点，其右子树中的所有节点的值都大于该节点的值。
对于任意节点，其左子树和右子树也分别是二叉搜索树。
二叉搜索树特点
有序性：二叉搜索树中的节点按照一定的顺序排列，左子树的值小于根节点的值，右子树的值大于根节点的值。这使得在树中进行搜索、插入或删除操作时具有高效性能。
快速查找：由于有序性，可以利用二叉搜索树进行快速查找操作。通过比较目标值与当前节点的值，可以根据大小关系递归地在左子树或右子树中继续查找目标值。
插入和删除操作：由于二叉搜索树的有序性，插入和删除操作可以保持树的有序性。插入操作按照节点值的大小关系找到合适的位置插入新节点。删除操作需要维护树的有序性，并根据节点的情况进行相应的调整。
二叉搜索树的常见操作
查找（Search）
在二叉搜索树中查找给定值。从根节点开始，比较目标值与当前节点的值，根据大小关系递归地在左子树或右子树中查找，直到找到目标值或遍历到叶子节点。
以下实例在二分搜索树中寻找 43 元素
(1) 元素 43 比根节点 42 大，需要在右子节点继续比较。
(2) 元素 43 比 59 小，需要在左子节点继续比较。
(3) 元素 43 比 51 小，需要在左子节点继续比较。
(4) 查找 51 的左子节点 43，正好和相等，结束。
插入（Insertion）
向二叉搜索树中插入新节点。按照节点值的大小关系，递归地在左子树或右子树中找到合适的位置插入新节点。
以下实例向如下二分搜索树中插入元素 61 的步骤：
（1）需要插入的元素 61 比 42 大，比较 42 的右子树根节点。
（2）61 比 59 大，所以需要把 61 移动到 59 右子树相应位置，而此时为空，直接插入作为 59 的右子节点。
插入操作也是一个递归过程，分三种情况，等于、大于、小于。
删除（Deletion）
从二叉搜索树中删除节点。删除节点时，需要考虑节点的子树情况和维护树的有序性。常见的情况包括删除叶子节点、删除只有一个子节点的节点以及删除有两个子节点的节点。
1、删除只有左孩子的节点，如下图节点 58
删除掉元素 58，让左子树直接代替 58 的位置，整个二分搜索树的性质不变。
2、删除只有右孩子的节点，如下图节点 58
删除掉元素 58，让右子树直接代替 58 的位置，整个二分搜索树的性质不变。
3、删除左右都有孩子的节点，如下图节点 58
（1）找到右子树中的最小值，为节点 59
（2）节点 59 代替待删除节点 58
最小值和最大值（Minimum and Maximum）
最小值在树的最左边叶子节点上，最大值在树的最右边叶子节点上。
遍历（Traversal）
按照一定的顺序遍历二叉搜索树的所有节点。常见的遍历方式包括深度优先遍历和广度优先遍历。
前序遍历：
中序遍历：
后序遍历：
层序遍历：
通过引入一个队列来支撑层序遍历：
如果根节点为空，无可遍历；
如果根节点不为空：
先将根节点入队；
只要队列不为空：
出队队首节点，并遍历；
如果队首节点有左孩子，将左孩子入队；
如果队首节点有右孩子，将右孩子入队；
（1）先取出根节点放入队列
（2）取出 29，左右孩子节点入队
（3）队首 17 出队，孩子节点 14、23 入队。
（4）31 出队，孩子节点 30 和 43 入队
（5）最后全部出队
