一、顺序表查找
顺序查找又叫线性查找，查找过程：从第一个/最后一个元素开始查找，若找到某个元素的关键字和给定的值相等，那么查找成功，否则查到最后一个/第一个都没有匹配的，则查找不成功。
- 栗子：for 循环查找列表
二、有序表查找
-
1、折半查找（二分查找）
前提：查找的集合有序
栗子：二分法查找
-
2、插值查找
插值查找其实就是针对表长较大，关键字分布比较均匀的表对二分法进行优化的查找，就是将 mid 的计算方法换成了跟关键字 key 有关的算法。
适用于表长较大，关键字分布比较均匀的表。
三、二叉排序树
二叉排序树又叫二叉查找树，它有如下性质：
-
若左子树不为空，则左子树上所有结点值均小于它的根结构的值
-
若右子树不为空，则右子树所有结点值均大于它的根结构的值
-
它的左右子树也分别为二叉排序树
1. 二叉查找树的查找
在二叉查找树中查找 key 的过程如下：
-
1、若二叉树是空树，则查找失败。
-
2、若 x 等于根结点的数据，则查找成功，否则。
-
3、若 x 小于根结点的数据，则递归查找其左子树，否则。
-
4、递归查找其右子树。
show my code
/**
* 判断二叉搜索树是否包含某个值
* @param key
* @param root
* @return
*/
public static boolean contains(Integer key,BinaryTreeNode root){
if(root == null){
return false;
}
int result = key.compareTo(root.value);
//遍历右子树
if(result > 0){
return contains(key,root.rightNode);
}else if(result < 0){
//遍历左子树
return contains(key,root.leftNode);
}else{
return true;
}
}
2. 二叉查找树的插入
插入其实是查找的更进一步，当找到相等的元素的时候便不做操作，直接返回找到的结点。否则根据最后找到的结点，判断要插入的结点为其左子结点还是右子结点。
show my code
/**
* 插入元素
* @param key
* @param root
* @return 要插入的结点
*/
public static BinaryTreeNode insert(Integer key,BinaryTreeNode root){
//空树 或者 遍历到了叶子结点
if(root == null){
return new BinaryTreeNode(key);
}
int result = key.compareTo(root.value);
//在右子树遍历
if(result > 0){
return root.rightNode = insert(key, root.rightNode);
}else if(result < 0){
//在左子树遍历
return root.leftNode = insert(key, root.leftNode);
}else{
System.out.println("有一个相同的值，不再插入");
return root;
}
}
3. 二叉查找树的删除
对于二叉查找树的删除操作（这里根据值删除，而非结点）分三种情况：
不过在此之前，我们应该确保根据给定的值找到了要删除的结点，如若没找到该结点，不会执行删除操作！
下面三种情况假设已经找到了要删除的结点。
1、如果结点为叶子结点（没有左、右子树），此时删除该结点不会破坏树的结构，直接删除即可，并修改其父结点指向它的引用为 null 。如下图：
情况一
2、如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。
情况二
3、当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据（后继结点）代替要删除的结点数据，并递归删除后继结点，因为右子树的最小结点不可能有左孩子，所以第二次删除较为容易。
z 的左子树和右子树均不空。找到 z 的后继结点 y，因为 y 一定没有左子树，所以可以删除 y。用 y 的值代替 z 的值并让 y 的双亲结点指向 y 的右子树。如图：
情况三
show my code
/**
* 查询出最小元素所在的结点
* @param node
* @return
*/
public static BinaryTreeNode findMin(BinaryTreeNode node){
if(node==null){
return null;
}else if(node.leftNode ==null){
return node;
}
return findMin(node.leftNode);//递归查找
}
/**
* 删除值等于key的结点
* @param key
* @param root
* @return
*/
public static BinaryTreeNode deleteNode(Integer key,BinaryTreeNode root){
if(root == null){
System.out.println("没有找到要删除的结点，删除失败");
return null;
}
int result = key.compareTo(root.value);
if(result > 0){
root.rightNode = deleteNode(key, root.rightNode);
}else if(result < 0){
root.leftNode = deleteNode(key, root.leftNode);
}else{
System.out.println("找到了要删除的结点："+root.value);
//找到了要删除的结点
if(root.leftNode != null && root.rightNode != null){
//找到后继结点（右子树最小结点）
root.value = findMin(root.rightNode).value;
//删除后继结点
deleteNode(root.value,root.rightNode);
}else if(root.leftNode != null && root.rightNode == null){
//左子树不为空，右子树为空
root = root.leftNode;
}else {
root = root.rightNode;
}
}
return root;
}
四、平衡二叉树
平衡二叉树是一种二叉排序树，其中每一个结点左子树和右子树的高度差至多等于 1。
网友评论