一甩挫、順序表查找
順序查找又叫線性查找椿每，查找過程：從第一個/最后一個元素開始查找，若找到某個元素的關(guān)鍵字和給定的值相等亦渗，那么查找成功汁尺，否則查到最后一個/第一個都沒有匹配的，則查找不成功搂蜓。
- 栗子：for 循環(huán)查找列表
二、有序表查找
-
1相味、折半查找（二分查找）
前提：查找的集合有序
栗子：二分法查找
-
2殉挽、插值查找
插值查找其實就是針對表長較大，關(guān)鍵字分布比較均勻的表對二分法進(jìn)行優(yōu)化的查找一死，就是將 mid 的計算方法換成了跟關(guān)鍵字 key 有關(guān)的算法傻唾。
適用于表長較大，關(guān)鍵字分布比較均勻的表逛裤。
三猴抹、二叉排序樹
二叉排序樹又叫二叉查找樹，它有如下性質(zhì)：
若左子樹不為空蝙砌，則左子樹上所有結(jié)點(diǎn)值均小于它的根結(jié)構(gòu)的值
若右子樹不為空跋理，則右子樹所有結(jié)點(diǎn)值均大于它的根結(jié)構(gòu)的值
它的左右子樹也分別為二叉排序樹
1. 二叉查找樹的查找
在二叉查找樹中查找 key 的過程如下：
1、若二叉樹是空樹肚邢，則查找失敗拭卿。
2峻厚、若 x 等于根結(jié)點(diǎn)的數(shù)據(jù)，則查找成功惠桃，否則。
3劈狐、若 x 小于根結(jié)點(diǎn)的數(shù)據(jù)懈息，則遞歸查找其左子樹，否則辫继。
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. 二叉查找樹的插入
插入其實是查找的更進(jìn)一步舵变，當(dāng)找到相等的元素的時候便不做操作纪隙，直接返回找到的結(jié)點(diǎn)扛或。否則根據(jù)最后找到的結(jié)點(diǎn)，判斷要插入的結(jié)點(diǎn)為其左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)悲伶。
show my code
/**
* 插入元素
* @param key
* @param root
* @return 要插入的結(jié)點(diǎn)
*/
public static BinaryTreeNode insert(Integer key,BinaryTreeNode root){
//空樹 或者 遍歷到了葉子結(jié)點(diǎn)
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. 二叉查找樹的刪除
對于二叉查找樹的刪除操作（這里根據(jù)值刪除舆声，而非結(jié)點(diǎn)）分三種情況：
不過在此之前媳握，我們應(yīng)該確保根據(jù)給定的值找到了要刪除的結(jié)點(diǎn)，如若沒找到該結(jié)點(diǎn)忽媒，不會執(zhí)行刪除操作腋粥！
下面三種情況假設(shè)已經(jīng)找到了要刪除的結(jié)點(diǎn)隘冲。
1、如果結(jié)點(diǎn)為葉子結(jié)點(diǎn)（沒有左奥邮、右子樹）罗珍，此時刪除該結(jié)點(diǎn)不會破壞樹的結(jié)構(gòu)，直接刪除即可覆旱，并修改其父結(jié)點(diǎn)指向它的引用為 null 。如下圖：
2、如果其結(jié)點(diǎn)只包含左子樹噪沙，或者右子樹的話正歼，此時直接刪除該結(jié)點(diǎn)，并將其左子樹或者右子樹設(shè)置為其父結(jié)點(diǎn)的左子樹或者右子樹即可齐疙，此操作不會破壞樹結(jié)構(gòu)旭咽。
3穷绵、當(dāng)結(jié)點(diǎn)的左右子樹都不空的時候仲墨，一般的刪除策略是用其右子樹的最小數(shù)據(jù)（后繼結(jié)點(diǎn)）代替要刪除的結(jié)點(diǎn)數(shù)據(jù)，并遞歸刪除后繼結(jié)點(diǎn)俩由，因為右子樹的最小結(jié)點(diǎn)不可能有左孩子幻梯，所以第二次刪除較為容易。
z 的左子樹和右子樹均不空碘梢。找到 z 的后繼結(jié)點(diǎn) y，因為 y 一定沒有左子樹肛鹏，所以可以刪除 y。用 y 的值代替 z 的值并讓 y 的雙親結(jié)點(diǎn)指向 y 的右子樹恩沛。如圖：
show my code
/**
* 查詢出最小元素所在的結(jié)點(diǎn)
* @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的結(jié)點(diǎn)
* @param key
* @param root
* @return
*/
public static BinaryTreeNode deleteNode(Integer key,BinaryTreeNode root){
if(root == null){
System.out.println("沒有找到要刪除的結(jié)點(diǎn)在扰，刪除失敗");
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("找到了要刪除的結(jié)點(diǎn)："+root.value);
//找到了要刪除的結(jié)點(diǎn)
if(root.leftNode != null && root.rightNode != null){
//找到后繼結(jié)點(diǎn)（右子樹最小結(jié)點(diǎn)）
root.value = findMin(root.rightNode).value;
//刪除后繼結(jié)點(diǎn)
deleteNode(root.value,root.rightNode);
}else if(root.leftNode != null && root.rightNode == null){
//左子樹不為空，右子樹為空
root = root.leftNode;
}else {
root = root.rightNode;
}
}
return root;
}
四健田、平衡二叉樹
平衡二叉樹是一種二叉排序樹佛纫，其中每一個結(jié)點(diǎn)左子樹和右子樹的高度差至多等于 1呈宇。
