二叉搜索树

二叉搜索树(BST)

二叉搜索树的结构有两种可能：

• 空树
• 左子节点的值小于根节点，右子节点的值大于根节点

** 基本操作 **

1. 查找
2. 插入
3. 删除

1. 查找

• 遍历二叉树，如果当前遍历的节点为空，则以为着没有目标结点，直接返回
• 若当前遍历的结点的值正好和目标值相等，则查找成功，返回
• 若当前遍历的结点的值大于目标值，则应该在该结点的左子树进行查找，设置下一步遍历范围为root.left，继续递归遍历
• 若当前遍历的结点的值小于目标值，则应该在该结点的右子树进行查找，设置下一步遍历范围为root.right，继续递归遍历