Java基础-二叉查找树

1.二叉查找树（Binary Search Tree）

概念：是一棵空树，或者是具有下列性质的二叉树

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
• 任意节点的左、右子树也分别为二叉查找树
• 没有键值相等的节点

示例图：

查找操作：

在二叉查找树中查找一个给定的值 k ，与二分查找很类似
首先拿 k 与树根的值进行比较，如果 k 比根的值大，则在根的右子树中查找，否则在根的左子树中查找，重复此过程，直到找到 k 和遇到空节点为止

查找的过程：

1. 若二叉树是空树，则查找失败
2. 若 k 等于根节点的数据，则查找成功
3. 若 k 小于根节点的数据，则递归查找其左子树
4. 若 k 大于根节点的数据，则递归查找其右子树

注意：
查找最小值：较小的值总是位于左节点上，只需要遍历左子树查找最后一个节点即可

查找最大值：较大的值总是位于右节点上，只需要遍历右子树查找最后一个节点即可

删除操作：

• 如果删除的是叶节点，可以直接删除
• 如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置
• 如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除

插入操作：

当向树中插入一个新的节点时，该节点将总是作为叶子节点。将这个新的节点称为节点 n，而遍历的当前节点称为节点 c。开始时，节点 c 为 BST 的根节点。
则定位节点 n 父节点的步骤如下：

1. 如果节点 c 为空，则节点 c 的父节点将作为节点 n 的父节点。如果节点 n 的值小于该父节点的值，则节点 n 将作为该父节点的左孩子；否则节点 n 将作为该父节点的右孩子
2. 比较节点 c 与节点 n 的值，如果节点 c 的值与节点 n 的值相等，则说明用户在试图插入一个重复的节点。解决办法可以是直接丢弃节点 n，或者可以抛出异常
3. 如果节点 n 的值小于节点 c 的值，则说明节点 n 一定是在节点 c 的左子树中。则将父节点设置为节点 c，并将节点 c 设置为节点 c 的左孩子，然后返回至第 1 步
4. 如果节点 n 的值大于节点 c 的值，则说明节点 n 一定是在节点 c 的右子树中。则将父节点设置为节点 c，并将节点 c 设置为节点 c 的右孩子，然后返回至第 1 步