按照顺序，遍历数组,比对数字，如果找到，返回下标，由于比较简单，不再介绍
二分查找思路分析：
需要查找的数组必须是有序的，否则查找没有意义
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[] { 1, 8, 10, 60, 89, 1000, 1234 };
int i = binarySearch(arr, 0, arr.length - 1, 60);
System.out.println(i);
}
//普通二分查找
public static int binarySearch(int[] arr, int left, int right, int findValue) {
// 递归调用出口
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] == findValue) {
return mid;
} else if (arr[mid] > findValue) {
return binarySearch(arr, left, mid - 1, findValue);
} else if (arr[mid] < findValue) {
return binarySearch(arr, mid + 1, right, findValue);
}
return -1;
}
一般二分查找只能找到一个索引，如果符合条件的数据有多个，那么就只能返回第一个符合条件数据的索引，如果要返回多个索引，需要继续查找：
二分查找实现（多个查询）：
public static int[] binarySearch2(int[] arr, int left, int right, int findValue) {
if (left > right) {
return result;
}
int mid = (left + right) / 2;
if (arr[mid] == findValue) {
result[index++] = mid;
binarySearch2(arr, mid + 1, right, findValue);
binarySearch2(arr, left, mid -1, findValue);
return result;
} else if (arr[mid] > findValue) {
return binarySearch2(arr, left, mid - 1, findValue);
} else if (arr[mid] < findValue) {
return binarySearch2(arr, mid + 1, right, findValue);
}
return result;
}
插值查找思路分析：
插值查找适用于平均分布的数据
插值查找是二分查找对平均分布数据的优化
只要将mid值得求法改成公式即可：
int mid = left + (findValue - arr[left]) / (arr[right] - arr[left]) * right;
插值查找注意事项：
哈希表介绍：
百度百科的图例：
二叉树的遍历
遍历思路分析：
public class MyTree {
public static void main(String[] args) {
Tree tree = new Tree();
tree.add(new TreeNode(1, "1"));
tree.add(new TreeNode(2, "2"));
tree.add(new TreeNode(3, "3"));
tree.add(new TreeNode(4, "4"));
tree.Hlist(tree.rootNode);
}
}
//管理二叉树的类
class Tree {
public TreeNode rootNode;
public void add(TreeNode node) {
if (rootNode == null) {
rootNode = node;
return;
}
TreeNode temp = rootNode;
while (true) {
if(temp == null) {
break;
}
if (temp.id < node.id) {
if (temp.rightChild == null) {
temp.rightChild = node;
break;
} else {
temp = temp.rightChild;
}
} else if (temp.id >= node.id) {
if (temp.leftChild == null) {
temp.leftChild = node;
break;
} else {
temp = temp.leftChild;
}
}
}
}
public void Qlist(TreeNode node) {
if (node == null) {
System.out.println("子树为空");
return;
}
System.out.println(node);
System.out.println("左子树：->");
Qlist(node.leftChild);
System.out.println("右子树：->");
Qlist(node.rightChild);
System.out.println("退回->");
}
public void Zlist(TreeNode node) {
if (node == null) {
System.out.println("子树为空");
return;
}
System.out.println("左子树：->");
Zlist(node.leftChild);
System.out.println(node);
System.out.println("右子树：->");
Zlist(node.rightChild);
System.out.println("退回->");
}
public void Hlist(TreeNode node) {
if (node == null) {
System.out.println("子树为空");
return;
}
System.out.println("左子树：->");
Hlist(node.leftChild);
System.out.println("右子树：->");
Hlist(node.rightChild);
System.out.println(node);
System.out.println("退回->");
}
}
class TreeNode {
public int id;
public String name;
public TreeNode rightChild;
public TreeNode leftChild;
public TreeNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "TreeNode [id=" + id + ", name=" + name + "]";
}
}
步骤（遍历比对）：
遍历判断效率低，应该根据待删除的编号找到节点的父节点后将其删除：
//调用时传入头节点，和待删除的节点编号
public void del(TreeNode node, int id) {
if (node.rightChild == null && node.leftChild == null) {
System.out.println("没有找到");
return;
}
if(node.id == id) {
rootNode = null;
}
if (node.id < id) {
if (node.rightChild != null) {
if (node.rightChild.id == id) {
node.rightChild = null;
return;
} else {
del(node.rightChild, id);
}
}
}
if (node.id > id) {
if (node.leftChild != null) {
if (node.leftChild.id == id) {
node.leftChild = null;
return;
} else {
del(node.leftChild, id);
}
}
}
}
package tree;
public class OrderTree {
public static void main(String[] args) {
//定义二叉树
int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Zlist(arr, 0, 0, arr.length - 1);
}
// 前序
public static void Qlist(int[] arr, int current, int begin, int end) {
if (arr == null || arr.length == 0) {
return;
}
if (current < begin || current > end) {
return;
}
System.out.print(arr[current] + " ");
Qlist(arr, current * 2 + 1, begin, end);
Qlist(arr, current * 2 + 2, begin, end);
}
public static void Zlist(int[] arr, int current, int begin, int end) {
if (arr == null || arr.length == 0) {
return;
}
if (current < begin || current > end) {
return;
}
Zlist(arr, current * 2 + 1, begin, end);
System.out.print(arr[current] + " ");
Zlist(arr, current * 2 + 2, begin, end);
}
public static void Hlist(int[] arr, int current, int begin, int end) {
if (arr == null || arr.length == 0) {
return;
}
if (current < begin || current > end) {
return;
}
Hlist(arr, current * 2 + 1, begin, end);
Hlist(arr, current * 2 + 2, begin, end);
System.out.print(arr[current] + " ");
}
}
如上图，我们需要右一个指针指向遍历的前一个结点才可以构建线索二叉树（在原二叉树的基础上）
实现代码：
class TreeNode2 {
public int id;
public String name;
public TreeNode2 right;
public TreeNode2 left;
// leftType == 0表示指向的是左子树(默认)，如果1则表示指向前驱节点
// 如果rightType ==0表示指向是右子树（默认），如果1表示指向后继节点
//用于遍历
public int leftType;
public int rightType;
public TreeNode2(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "TreeNode2 [id=" + id + ", name=" + name + "]";
}
}
public TreeNode2 rootNode;
public TreeNode2 preNode = null;
/**
* 中序线索化，传入头节点
*
* @param node 需要线索化的节点
*/
public void ZthreadNodes(TreeNode2 node) {
if (node == null) {
return;
}
// 线索化左子树
if (node.leftType != 1)
ZthreadNodes(node.left);
///
// node的值依次为[8,3,10,1,14,6]
// preNode的值依次为[null,8,3,10,1,14]
// 线索化当前节点
// 处理前驱
if (node.left == null) {
// 当前结点的左指针指向前驱节点
node.left = preNode;
node.leftType = 1;
}
// 处理后继结点
// 如上述分析preNode的值可能为null，需要判断
if (preNode != null && preNode.right == null) {
// 前驱结点的右指针指向当前结点
preNode.right = node;
preNode.rightType = 1;
}
// 每处理一个结点后，让当前结点为下一个结点的前驱结点
preNode = node;
//
// 线索化右子树
if (node.rightType != 1)
ZthreadNodes(node.right);
}
//遍历方法
public void Zlist(TreeNode2 node) {
while (node != null) {
// 找到最左边的结点
while (node.leftType == 0) {
node = node.left;
}
// 输出
System.out.println(node);
//开始向后继结点遍历
while (node.rightType == 1) {
node = node.right;
System.out.println(node);
}
// 替换这个遍历的结点
node = node.right;
}
}
public TreeNode2 rootNode;
public TreeNode2 preNode = null;
public void QthreadNodes(TreeNode2 node) {
if (node == null) {
return;
}
if (node.left == null) {
node.left = preNode;
node.leftType = 1;
}
if (preNode != null && preNode.right == null) {
preNode.right = node;
preNode.rightType = 1;
}
preNode = node;
if (node.leftType != 1)
QthreadNodes(node.left);
if (node.rightType != 1)
QthreadNodes(node.right);
}
//遍历
public void Qlist(TreeNode2 node) {
while(node!=null) {
while(node.leftType == 0) {
System.out.println(node);
node = node.left;
}
System.out.println(node);
node = node.right;
}
}
由于后序遍历比较难，附上完整代码：
一定要在构造结点的时候为父节点赋值！！
构建的树：
public class ThreadTree {
public static void main(String[] args) {
//创建结点
TreeNode2 node1 = new TreeNode2(1, "");
TreeNode2 node3 = new TreeNode2(3, "");
TreeNode2 node6 = new TreeNode2(6, "");
TreeNode2 node8 = new TreeNode2(8, "");
TreeNode2 node10 = new TreeNode2(10, "");
TreeNode2 node14 = new TreeNode2(14, "");
node1.right = node6;
node3.right = node10;
node1.left = node3;
node3.left = node8;
node6.left = node14;
//这一步很重要，没有这一步则遍历失败！！！
node3.parentNode = node1;
node6.parentNode = node1;
node8.parentNode = node3;
node10.parentNode = node3;
node14.parentNode = node6;
/
Tree2 tree2 = new Tree2();
tree2.HthreadNodes(node1);
tree2.Hlist(node1);
}
}
class Tree2 {
public TreeNode2 rootNode;
public TreeNode2 preNode = null;
//后序线索化
public void HthreadNodes(TreeNode2 node) {
if (node == null) {
return;
}
if (node.leftType != 1)
HthreadNodes(node.left);
if (node.rightType != 1)
HthreadNodes(node.right);
if (node.left == null) {
node.left = preNode;
node.leftType = 1;
}
if (preNode != null && preNode.right == null) {
preNode.right = node;
preNode.rightType = 1;
}
preNode = node;
}
//后续遍历，方法中不会初始化parentNode结点，请在调用前，手动初始化parentNode结点
public void Hlist(TreeNode2 node) {
if (node == null) {
return;
}
// 先找到就开始遍历的结点，也就是最左边的结点（线索化之前原来树的最左边）
//因为后序遍历就是从这里开始的
// 迭代左指针，要过滤掉前驱的类型
while (node != null && node.leftType == 0) {
node = node.left;
}
while(node!=null) {
//如果有后继结点，就可以顺着后继结点遍历了
if(node.rightType == 1) {
System.out.println(node);
preNode = node;
//记录上一个结点，向后继移动
node = node.right;
}else {
//如果上次处理的结点时当前结点的右节点
//因为后序的遍历顺序为左 -> 右 ->当前结点
//所以可以处理当前结点了
if(node.right == preNode) {
System.out.println(node);
//在后序遍历中，根节点时最后访问到的，如果是根节点
//遍历结束
if(node == rootNode) {
return;
}
preNode = node;
//回退到上一次结点
node = node.parentNode;
}else {
//既没有后继结点，右边的结点也不是上次处理的结点
node = node.right;
while(node!=null&& node.leftType == 0) {
node = node.left;
}
}
}
}
}
}
//结点结构
class TreeNode2 {
public int id;
public String name;
public TreeNode2 right;
public TreeNode2 left;
// leftType == 0表示指向的是左子树(默认)，如果1则表示指向前驱节点
// 如果rightType ==0表示指向是右子树（默认），如果1表示指向后继节点
// 用于后续遍历
public TreeNode2 parentNode;
// 用于遍历
public int leftType;
public int rightType;
public TreeNode2(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "TreeNode2 [id=" + id + ", name=" + name + "]";
}
}