Skip to content

Commit 0b6d1a7

Browse files
byhiegbyhieg
committed
合并文件
2 parents 0c45e5b + 722da5d commit 0b6d1a7

7 files changed

Lines changed: 308 additions & 63 deletions

File tree

‎src/main/java/cn/byhieg/algorithmtutorial/BinarySearchTree.java‎

Lines changed: 54 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -5,21 +5,14 @@
55
* Mail to [email protected]
66
*/
77

8+
import java.util.LinkedList;
9+
import java.util.Queue;
810
import java.util.Stack;
911

1012
/**
1113
* 该类是二叉搜索树
1214
* 该树在实现的时候，不考虑数组中有重复的数字。
1315
* 节点的左子节点的值都小于这个节点的值，节点的右子节点的值都大于等于这个节点的值
14-
* 该树并不是平衡二叉树，也就是说左右子树的树高可以存在很大的差距，这就导致了在极端情况下，存在只有左边的树，这样的查找时间复杂度就是o(N)
15-
* 平均情况下 时间复杂度是o(lgN)
16-
*
17-
* 可以考虑是用平衡二叉树，保持了树的左右高度 不会超过1，但是带来的插入和删除的额外开销，因为每次插入删除，都需要调整平衡
18-
* 但他的查找的时间复杂度是o(lgN)
19-
*
20-
* 二叉搜索树(BST)相比二分查找的优势，在于他不需要基于有序的数组，并且插入和删除的操作显然比二分查找的数组有快的多，
21-
* 但是时间复杂度没有二分查找稳定
22-
* 相比二叉平衡搜索树(AVL)而言，虽然多了插入和删除的优势，但是没有AVL稳定
2316
*/
2417
public class BinarySearchTree {
2518

@@ -163,6 +156,8 @@ public void preOrder2(Node node) {
163156
stack.push(tmp.left);
164157
}
165158
}
159+
System.out.println("结束");
160+
166161
}
167162
}
168163

@@ -186,6 +181,8 @@ public void inorder2(Node node) {
186181
cur = cur.left;
187182
}
188183
}
184+
System.out.println("结束");
185+
189186
}
190187
}
191188

@@ -218,9 +215,35 @@ public void postOrder2(Node node) {
218215
while (!result.isEmpty()) {
219216
System.out.print(result.pop().data + "-->");
220217
}
218+
System.out.println("结束");
219+
221220
}
222221
}
223222

223+
/**
224+
* 树的层次遍历，类似于图的BFS
225+
* @param root
226+
*/
227+
public void levelRead(Node root) {
228+
if (root == null) return;
229+
Queue<Node> queue = new LinkedList<>();
230+
queue.offer(root);
231+
while (!queue.isEmpty()) {
232+
Node current = queue.poll();
233+
System.out.print(current.data + "-->");
234+
if (current.left != null) {
235+
queue.offer(current.left);
236+
}
237+
if (current.right != null) {
238+
queue.offer(current.right);
239+
}
240+
}
241+
System.out.println("结束");
242+
243+
}
244+
245+
246+
224247

225248
/**
226249
* 得到树中最小的节点
@@ -258,28 +281,28 @@ public Node getMaxNode() {
258281

259282

260283
/**
261-
* 通过先序遍历和中序遍历恢复一棵树
284+
* 从先序遍历和中序遍历中构造出树
262285
* @param preOrders
263286
* @param inOrders
264-
* @param isLeft
287+
* @param r
265288
*/
266-
public void getTree(int[] preOrders, int[] inOrders,boolean isLeft) {
289+
public void getTree(int[] preOrders, int[] inOrders,Node r) {
267290
int root = preOrders[0];
268-
if (isLeft) {
269-
System.out.println("左" + root);
270-
}else{
271-
System.out.println("右" + root);
272-
}
291+
r.data = root;
273292

274-
int index = new Find().binarySearchFind(inOrders, root);
293+
int index = findIndex(inOrders, root);
275294
int[] left = new int[index];
276295
int[] preLeft = new int[index];
277296
if (left.length != 0) {
278297
for (int i = 0; i < index; i++) {
279298
left[i] = inOrders[i];
280299
preLeft[i] = preOrders[i + 1];
281300
}
301+
Node node = new Node(preLeft[0]);
302+
r.left = node;
282303
}
304+
305+
283306
int size = inOrders.length - index - 1;
284307
int[] right = new int[inOrders.length - index - 1];
285308
int[] preRight = new int[size];
@@ -288,17 +311,17 @@ public void getTree(int[] preOrders, int[] inOrders,boolean isLeft) {
288311
right[i] = inOrders[i + index + 1];
289312
preRight[i] = preOrders[preLeft.length + i + 1];
290313
}
314+
Node node = new Node(preRight[0]);
315+
r.right = node;
291316
}
292317

293318
if (preLeft.length != 0) {
294-
getTree(preLeft, left,true);
319+
getTree(preLeft, left,r.left);
295320
}
296321

297322
if (preRight.length != 0) {
298-
getTree(preRight, right,false);
323+
getTree(preRight, right,r.right);
299324
}
300-
System.out.println();
301-
302325
}
303326

304327
public static class Node {
@@ -314,4 +337,13 @@ public Node(int data) {
314337
public Node getRoot() {
315338
return root;
316339
}
340+
341+
private int findIndex(int[] nums, int target) {
342+
for (int i = 0 ; i < nums.length;i++) {
343+
if (nums[i] == target) {
344+
return i;
345+
}
346+
}
347+
return -1;
348+
}
317349
}

‎src/main/java/cn/byhieg/algorithmtutorial/GraphMatrix.java‎

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* Created by shiqifeng on 2017/4/5.
8+
* Mail [email protected]
9+
*/
10+
public class GraphMatrix {
11+
12+
Weight[][] graph;
13+
boolean[] isVisited;
14+
15+
private static final int UNREACH = Integer.MAX_VALUE - 1000;
16+
17+
public GraphMatrix(Weight[][] graph) {
18+
this.graph = graph;
19+
}
20+
21+
/**
22+
* 图的BFS，算法流程
23+
* 1. 首先将begin节点入队
24+
* 2. 然后判断队列是否为空,不为空，则出队一个元素，输出。
25+
* 3. 将出队的元素的所有相邻的元素且没有访问的都放进队列中，重复第二步
26+
*
27+
* 广度优先遍历，从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
28+
* @param begin
29+
*/
30+
public void BFS(Integer begin) {
31+
isVisited = new boolean[graph.length];
32+
for (int i = 0 ; i < isVisited.length;i++) {
33+
isVisited[i] = false;
34+
}
35+
36+
Queue<Integer> queue = new LinkedList<>();
37+
queue.offer(begin);
38+
isVisited[begin] = true;
39+
40+
while (!queue.isEmpty()) {
41+
int current = queue.poll();
42+
System.out.print(current + "-->");
43+
for (int i = 0 ; i < graph[current].length;i++) {
44+
if (i == begin) {
45+
continue;
46+
}
47+
if (graph[current][i].weight != UNREACH && !isVisited[i]) {
48+
queue.offer(i);
49+
isVisited[i] = true;
50+
}
51+
}
52+
}
53+
System.out.println("结束");
54+
}
55+
56+
57+
/**
58+
* 图的DFS算法，算法流程
59+
* 1. 从begin节点出发，输出begin节点。
60+
* 2. 循环遍历所有与begin节点相邻并且没有被访问的节点
61+
* 3. 找到一个节点，就以他为begin,递归调用DFS
62+
* @param begin
63+
*/
64+
public void DFS(Integer begin) {
65+
isVisited = new boolean[graph.length];
66+
for (int i = 0 ; i < isVisited.length;i++) {
67+
isVisited[i] = false;
68+
}
69+
doDFS(begin);
70+
System.out.println("结束");
71+
}
72+
73+
/**
74+
* 假设给定图G的初态是所有顶点均未曾访问过。
75+
* 在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：
76+
* 首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。
77+
* 若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
78+
* 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
79+
* @param begin
80+
*/
81+
private void doDFS(Integer begin) {
82+
isVisited[begin] = true;
83+
System.out.print(begin + "-->");
84+
for (int i = 0 ; i < graph[begin].length;i++) {
85+
if (graph[begin][i].weight != UNREACH && !isVisited[i]) {
86+
doDFS(i);
87+
}
88+
}
89+
}
90+
91+
public void dijkstra(int start) {
92+
//接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
93+
//返回一个int[] 数组，表示从start到它的最短路径长度
94+
int n = graph.length; //顶点个数
95+
int[] shortPath = new int[n]; //存放从start到其他各点的最短路径
96+
String[] path = new String[n]; //存放从start到其他各点的最短路径的字符串表示
97+
for (int i = 0; i < n; i++)
98+
path[i] = new String(start + "-->" + i);
99+
int[] visited = new int[n]; //标记当前该顶点的最短路径是否已经求出,1表示已求出
100+
101+
//初始化，第一个顶点求出
102+
shortPath[start] = 0;
103+
visited[start] = 1;
104+
105+
for (int count = 1; count <= n - 1; count++) //要加入n-1个顶点
106+
{
107+
108+
int k = -1; //选出一个距离初始顶点start最近的未标记顶点
109+
int dmin = Integer.MAX_VALUE;
110+
for (int i = 0; i < n; i++) {
111+
if (visited[i] == 0 && graph[start][i].weight < dmin) {
112+
dmin = graph[start][i].weight;
113+
114+
k = i;
115+
}
116+
117+
}
118+
//将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
119+
shortPath[k] = dmin;
120+
121+
visited[k] = 1;
122+
123+
//以k为中间点，修正从start到未访问各点的距离
124+
for (int i = 0; i < n; i++) { // System.out.println("k="+k);
125+
if (visited[i] == 0 && graph[start][k].weight + graph[k][i].weight < graph[start][i].weight) {
126+
graph[start][i].weight = graph[start][k].weight + graph[k][i].weight;
127+
path[i] = path[k] + "-->" + i;
128+
}
129+
}
130+
}
131+
132+
for (int i = 0; i < n; i++) {
133+
System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i] + " 距离为" + shortPath[i]);
134+
}
135+
}
136+
137+
138+
139+
140+
141+
142+
public static class Weight{
143+
int weight;
144+
public Weight(){
145+
this(UNREACH);
146+
}
147+
148+
public Weight(int weight) {
149+
this.weight = weight;
150+
}
151+
}
152+
}

‎src/main/java/cn/byhieg/algorithmtutorial/Sort.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -250,7 +250,8 @@ public void sink(int [] nums, int i,int n) {
250250
nums[i] = nums[son];
251251
nums[son] = temp;
252252
i = son;
253-
} else {
253+
son = 2 * i + 1;
254+
}else{
254255
break;
255256
}
256257
}

‎src/test/java/cn/byhieg/algorithmtutorialtest/FindTest.java‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -12,23 +12,23 @@ public class FindTest extends TestCase {
1212
int result;
1313
public void setUp() throws Exception {
1414
super.setUp();
15-
nums = new int[]{1};
15+
nums = new int[]{};
1616
}
1717

1818
public void tearDown() throws Exception {
1919
System.out.println(result);
2020
}
2121

22-
// public void testBinarySerachFind() throws Exception {
23-
// result = new Find().binarySerachFind(nums,6);
24-
// }
25-
////
22+
public void testBinarySerachFind() throws Exception {
23+
result = new Find().binarySearchFind(nums,2);
24+
}
25+
2626
// public void testBinarySearchMinFind() throws Exception {
2727
// result = new Find().binarySearchMinFind(nums,1);
2828
// }
2929

30-
public void testBinarySearchMaxFind() throws Exception {
31-
result = new Find().binarySearchMaxFind(nums, 2);
32-
}
30+
// public void testBinarySearchMaxFind() throws Exception {
31+
// result = new Find().binarySearchMaxFind(nums, 2);
32+
// }
3333

3434
}

0 commit comments

Comments
 (0)