Skip to content

Commit c94ffac

Browse files
byhiegbyhieg
committed
Merge branch 'master' of https://github.com/byhieg/JavaTutorial 
2 parents 849f9f0 + d200fb2 commit c94ffac

File tree

9 files changed

+635
-0
lines changed

9 files changed

+635
-0
lines changed

‎images/Thumbs.db‎

11 KB
Binary file not shown.

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

Lines changed: 285 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,285 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
import java.util.Stack;
6+
7+
/**
8+
* Created by byhieg on 17/4/15.
9+
* Mail to byhieg@gmail.com
10+
*/
11+
public class BinaryTree {
12+
13+
/**
14+
* 递归的形式实现先续遍历
15+
* 根-左-右
16+
*
17+
* @param root
18+
*/
19+
public static void preOrder1(Node root) {
20+
if (root != null) {
21+
System.out.print(root.data + " ");
22+
preOrder1(root.left);
23+
preOrder1(root.right);
24+
}
25+
}
26+
27+
/**
28+
* 非递归的形式实现先续遍历
29+
* 根-左-右
30+
*
31+
* @param root
32+
*/
33+
public static void preOrder2(Node root) {
34+
if (root != null) {
35+
Stack<Node> stack = new Stack<>();
36+
stack.push(root);
37+
while (!stack.isEmpty()) {
38+
Node cur = stack.pop();
39+
System.out.print(cur.data + " ");
40+
if (cur.right != null) {
41+
stack.push(cur.right);
42+
}
43+
if (cur.left != null) {
44+
stack.push(cur.left);
45+
}
46+
}
47+
}
48+
}
49+
50+
/**
51+
* 递归实现中序遍历
52+
* 左-根-右
53+
*
54+
* @param root
55+
*/
56+
public static void inOrder1(Node root) {
57+
if (root != null) {
58+
inOrder1(root.left);
59+
System.out.print(root.data + " ");
60+
inOrder1(root.right);
61+
}
62+
}
63+
64+
/**
65+
* 非递归实现中序遍历
66+
* 左-根-右
67+
*
68+
* @param root
69+
*/
70+
public static void inOrder2(Node root) {
71+
if (root != null) {
72+
Stack<Node> stack = new Stack<>();
73+
Node cur = root;
74+
while (!stack.isEmpty() || cur != null) {
75+
if (cur == null) {
76+
Node node = stack.pop();
77+
System.out.print(node.data + " ");
78+
cur = node.right;
79+
} else {
80+
stack.push(cur);
81+
cur = cur.left;
82+
}
83+
84+
}
85+
}
86+
}
87+
88+
/**
89+
* 递归实现树的后续遍历
90+
* 左-右-根
91+
*
92+
* @param root
93+
*/
94+
public static void postOrder1(Node root) {
95+
if (root != null) {
96+
postOrder1(root.left);
97+
postOrder1(root.right);
98+
System.out.print(root.data + " ");
99+
}
100+
}
101+
102+
/**
103+
* 非递归试树的后续遍历
104+
* 左-右-根
105+
*
106+
* @param root
107+
*/
108+
public static void postOrder2(Node root) {
109+
if (root != null) {
110+
Stack<Node> tmpStack = new Stack<>();
111+
Stack<Node> resStack = new Stack<>();
112+
tmpStack.push(root);
113+
while (!tmpStack.isEmpty()) {
114+
Node cur = tmpStack.pop();
115+
resStack.push(cur);
116+
if (cur.left != null) {
117+
tmpStack.push(cur.left);
118+
}
119+
if (cur.right != null) {
120+
tmpStack.push(cur.right);
121+
}
122+
}
123+
124+
while (!resStack.isEmpty()) {
125+
Node cur = resStack.pop();
126+
System.out.print(cur.data + " ");
127+
}
128+
}
129+
}
130+
131+
/**
132+
* 层次遍历
133+
*
134+
* @param root
135+
*/
136+
public static void levelOrder(Node root) {
137+
if (root != null) {
138+
Queue<Node> queue = new LinkedList<>();
139+
queue.offer(root);
140+
while (!queue.isEmpty()) {
141+
Node cur = queue.poll();
142+
System.out.print(cur.data + " ");
143+
if (cur.left != null) {
144+
queue.offer(cur.left);
145+
}
146+
if (cur.right != null) {
147+
queue.offer(cur.right);
148+
}
149+
}
150+
}
151+
}
152+
153+
/**
154+
* 统计树的节点数
155+
*
156+
* @param root
157+
*/
158+
public static int getNodes(Node root) {
159+
if (root == null) {
160+
return 0;
161+
}
162+
return getNodes(root.left) + getNodes(root.right) + 1;
163+
}
164+
165+
/**
166+
* 得到树的叶子节点的数目
167+
* @param root
168+
* @return
169+
*/
170+
public static int getLeafs(Node root) {
171+
if (root == null) {
172+
return 0;
173+
}
174+
if (root.right == null && root.left == null) {
175+
return 1;
176+
}
177+
return getLeafs(root.left) + getLeafs(root.right);
178+
179+
}
180+
181+
182+
/**
183+
* 计算树的深度
184+
* @param root
185+
* @return
186+
*/
187+
public static int getHeight(Node root){
188+
if (root == null) {
189+
return 0;
190+
}
191+
int leftHeight = getHeight(root.left) + 1;
192+
int rightHeight = getHeight(root.right) + 1;
193+
return leftHeight > rightHeight ? leftHeight : rightHeight;
194+
}
195+
196+
/**
197+
* 计算第K层的节点数
198+
* @param root
199+
* @param k
200+
* @return
201+
*/
202+
public static int calcKNodes(Node root, int k) {
203+
if (root == null || k < 0) {
204+
return 0;
205+
}
206+
if (k == 0){
207+
return 1;
208+
}
209+
return calcKNodes(root.left, k - 1) + calcKNodes(root.right, k - 1);
210+
211+
}
212+
213+
/**
214+
* 判断两个树的结构是否相同
215+
* @param root1
216+
* @param root2
217+
* @return
218+
*/
219+
public static boolean isCommon(Node root1, Node root2) {
220+
if (root1 == null && root2 == null) {
221+
return true;
222+
} else if (root1 == null || root2 == null) {
223+
return false;
224+
}else{
225+
boolean isLeftCommon = isCommon(root1.left, root2.left);
226+
boolean isRightCommon = isCommon(root1.right, root2.right);
227+
return isLeftCommon && isRightCommon;
228+
}
229+
}
230+
231+
/**
232+
* 得到树的镜像，即对于每一个节点，交换他们的左右孩子节点。
233+
* @param root
234+
*/
235+
public static void mirror(Node root) {
236+
if (root != null) {
237+
Node tmp = root.left;
238+
root.left = root.right;
239+
root.right = tmp;
240+
mirror(root.left);
241+
mirror(root.right);
242+
}
243+
}
244+
245+
/**
246+
* 得到两个节点的最近公共祖先节点。
247+
* 递归左右子树，如果返回的值都不为空，则表示在左右子树各找到一个target，因为最近的祖先就是cur
248+
* 如果有一个为空，则就不为空就是最近公共祖先。
249+
* @param root
250+
* @param target1
251+
* @param target2
252+
* @return
253+
*/
254+
public static Node findLCA(Node root, Node target1, Node target2) {
255+
if (root == null)
256+
return null;
257+
258+
if (root == target1 || root == target2) {
259+
return root;
260+
}
261+
Node left = findLCA(root.left, target1, target2);
262+
Node right = findLCA(root.right, target1, target2);
263+
if (left != null && right != null) {
264+
return root;
265+
}
266+
return left != null ? left:right;
267+
}
268+
269+
270+
271+
public static class Node {
272+
public int data;
273+
public Node left;
274+
public Node right;
275+
276+
277+
public Node(int data) {
278+
this.data = data;
279+
left = null;
280+
right = null;
281+
}
282+
}
283+
284+
285+
}

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

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
/**
4+
* Created by byhieg on 17/5/2.
5+
* Mail to byhieg@gmail.com
6+
*/
7+
public class SingleLinkList {
8+
9+
10+
public Node head;
11+
12+
/**
13+
* 在当前链表尾部插入一个节点
14+
*
15+
* @param data
16+
* @return
17+
*/
18+
public Node insertFromTail(int data) {
19+
Node cur = getHead();
20+
Node node = new Node(data);
21+
if (cur == null) {
22+
head = node;
23+
return head;
24+
} else {
25+
while (cur.next != null) {
26+
cur = cur.next;
27+
}
28+
cur.next = node;
29+
}
30+
return cur;
31+
}
32+
33+
/**
34+
* 在当前链表头部插入一个节点
35+
*
36+
* @param data
37+
* @return
38+
*/
39+
public Node insertFromHead(int data) {
40+
Node node = new Node(data);
41+
node.next = head;
42+
head = node;
43+
return head;
44+
}
45+
46+
47+
public Node reverseLinkList() {
48+
if (head == null) {
49+
return head;
50+
}
51+
Node reverseHead = null;
52+
Node cur = head;
53+
Node prev = null;
54+
while (cur != null) {
55+
Node next = cur.next;
56+
if (next == null) {
57+
reverseHead = cur;
58+
}
59+
cur.next = prev;
60+
prev = cur;
61+
cur = next;
62+
}
63+
return reverseHead;
64+
}
65+
66+
/**
67+
* 打印链表
68+
*/
69+
public void printLinkList(Node head) {
70+
Node cur = head;
71+
while (cur != null) {
72+
System.out.print(cur.data + " ");
73+
cur = cur.next;
74+
}
75+
}
76+
77+
public Node getHead() {
78+
return head;
79+
}
80+
81+
public static class Node {
82+
public int data;
83+
public Node next;
84+
85+
public Node(int data) {
86+
this.data = data;
87+
}
88+
}
89+
}

‎src/main/java/cn/byhieg/threadtutorial/concurrent/blocking/ArrayBlock.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package cn.byhieg.threadtutorial.concurrent.blocking;
2+
3+
import java.util.concurrent.ArrayBlockingQueue;
4+
import java.util.concurrent.BlockingQueue;
5+
6+
/**
7+
* Created by byhieg on 17/5/3.
8+
* Mail to byhieg@gmail.com
9+
*/
10+
public class ArrayBlock {
11+
12+
private BlockingQueue<String> blockingQueue;
13+
14+
public ArrayBlock(){
15+
blockingQueue = new ArrayBlockingQueue<String>(1024);
16+
}
17+
18+
public BlockingQueue<String> getBlockingQueue() {
19+
return blockingQueue;
20+
}
21+
}

0 commit comments

Comments
 (0)