Skip to content

Commit 9e23fe2

Browse files
coder-dongcoder-dong
committed
common sort alg
0 parents  commit 9e23fe2

28 files changed

+1720
-0
lines changed

‎src/Main.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
public class Main {
2+
3+
public static void main(String[] args) {
4+
System.out.println("Hello World!");
5+
}
6+
}

‎src/com/dong/learn/algorithms/arrange/Arrange.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.dong.learn.algorithms.arrange;
2+
3+
/**
4+
* Created by coding-dong on 2017/5/21.
5+
*/
6+
public class Arrange {
7+
8+
public <T> void arrange(T[] source, int start){
9+
if(start == source.length){
10+
printRange(source);
11+
return;
12+
}
13+
14+
for (int i = start; i < source.length; i++){
15+
swap(source, start, i);
16+
arrange(source, start + 1);
17+
swap(source, start, i);
18+
}
19+
}
20+
21+
private <T> void swap(T[] source, int start, int i) {
22+
T temp = source[start];
23+
source[start] = source[i];
24+
source[i] = temp;
25+
}
26+
27+
private <T> void printRange(T[] source) {
28+
for (T t : source){
29+
System.out.print(t.toString() + " ");
30+
}
31+
System.out.print("\n<====================>\n");
32+
// System.out.println("<====================>");
33+
}
34+
35+
public static void main(String[] args) {
36+
String[] source = {"a", "b", "c", "d"};
37+
38+
Arrange arrange = new Arrange();
39+
arrange.arrange(source, 0);
40+
}
41+
}

‎src/com/dong/learn/algorithms/btree/BTree.java

Lines changed: 250 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,250 @@
1+
package com.dong.learn.algorithms.btree;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
import java.util.Stack;
6+
7+
/**
8+
* Created by coding-dong on 2017/10/24.
9+
*/
10+
public class BTree<T extends String> {
11+
12+
private BTreeNode<T> rootNode;
13+
14+
private int counter = 0;
15+
16+
public BTreeNode<T> createBTree(String treeStr){
17+
char nodeData = treeStr.charAt(counter++);
18+
19+
if('#' == nodeData){
20+
return null;
21+
}else {
22+
BTreeNode<T> node = new BTreeNode<>();
23+
node.setData((T)String.valueOf(nodeData));
24+
25+
node.setlChild(createBTree(treeStr));
26+
node.setrChild(createBTree(treeStr));
27+
28+
return node;
29+
}
30+
}
31+
32+
public void initRoot(String treeStr){
33+
rootNode = createBTree(treeStr);
34+
}
35+
36+
public void preBTree(BTreeNode rootNode, int level){
37+
if(rootNode == null){
38+
return;
39+
}
40+
System.out.println("data : " + rootNode.getData() + ", level : " + level);
41+
42+
preBTree(rootNode.getlChild(), level + 1);
43+
44+
preBTree(rootNode.getrChild(), level + 1);
45+
}
46+
47+
public int depthBTree(BTreeNode rootNode){
48+
if(rootNode == null){
49+
return 0;
50+
}
51+
52+
int leftDepth = depthBTree(rootNode.getlChild());
53+
int rightDepth = depthBTree(rootNode.getrChild());
54+
55+
return 1 + Math.max(leftDepth, rightDepth);
56+
}
57+
58+
public void printNodeAtLevel(BTreeNode rootNode, int level){
59+
if(rootNode == null || level < 1){
60+
System.out.print("#" + " ");
61+
return;
62+
}
63+
64+
65+
if(level == 1){
66+
System.out.print(rootNode.getData() + " ");
67+
if(rootNode == this.rootNode){
68+
System.out.println();
69+
}
70+
return;
71+
}
72+
73+
printNodeAtLevel(rootNode.getlChild(), level - 1);
74+
printNodeAtLevel(rootNode.getrChild(), level - 1);
75+
76+
System.out.println();
77+
}
78+
79+
public void levelTraverse(){
80+
int depth = depthBTree(rootNode);
81+
82+
for(int i = 1; i <= depth; i++){
83+
printNodeAtLevel(rootNode, i);
84+
}
85+
}
86+
87+
public int nodeCount(BTreeNode bTreeNode){
88+
if(bTreeNode == null){
89+
return 0;
90+
}
91+
92+
int leftCount = nodeCount(bTreeNode.getlChild());
93+
int rightCount = nodeCount(bTreeNode.getrChild());
94+
95+
return leftCount + rightCount + 1;
96+
}
97+
98+
public int leafNodeCount(BTreeNode bTreeNode){
99+
if(bTreeNode == null){
100+
return 0;
101+
}
102+
103+
if(bTreeNode.getlChild() == null && bTreeNode.getrChild() == null){
104+
return 1;
105+
}
106+
107+
int leftLeafNodeCount = leafNodeCount(bTreeNode.getlChild());
108+
int rightLeafNodeCount = leafNodeCount(bTreeNode.getrChild());
109+
110+
return leftLeafNodeCount + rightLeafNodeCount;
111+
}
112+
113+
public BTreeNode mirror(BTreeNode bTreeNode){
114+
if(bTreeNode == null){
115+
return null;
116+
}
117+
118+
BTreeNode leftNode = mirror(bTreeNode.getlChild());
119+
BTreeNode rightNode = mirror(bTreeNode.getrChild());
120+
121+
bTreeNode.setlChild(rightNode);
122+
bTreeNode.setrChild(leftNode);
123+
124+
return bTreeNode;
125+
}
126+
127+
public void levelTraverseNoRecur(){
128+
Queue<BTreeNode> treeNodeQueue = new LinkedList<>();
129+
130+
treeNodeQueue.offer(rootNode);
131+
132+
while (!treeNodeQueue.isEmpty()){
133+
BTreeNode bTreeNode = treeNodeQueue.poll();
134+
System.out.print(bTreeNode.getData() + " ");
135+
136+
if(bTreeNode.getlChild() != null){
137+
treeNodeQueue.offer(bTreeNode.getlChild());
138+
}
139+
140+
if(bTreeNode.getrChild() != null){
141+
treeNodeQueue.offer(bTreeNode.getrChild());
142+
}
143+
}
144+
}
145+
146+
public void preBTreeNoRecur(){
147+
Stack<BTreeNode> treeNodeStack = new Stack<>();
148+
BTreeNode popNode = rootNode;
149+
while (popNode != null || !treeNodeStack.isEmpty()){
150+
151+
while (popNode != null){
152+
System.out.print(popNode.getData() + " ");
153+
154+
treeNodeStack.push(popNode);
155+
156+
popNode = popNode.getlChild();
157+
158+
}
159+
160+
popNode = treeNodeStack.pop();
161+
162+
popNode = popNode.getrChild();
163+
}
164+
165+
System.out.println();
166+
}
167+
168+
public void middleBTreeNoRecur(){
169+
Stack<BTreeNode> treeNodeStack = new Stack<>();
170+
BTreeNode popNode = rootNode;
171+
172+
while (popNode != null || !treeNodeStack.isEmpty()){
173+
while (popNode != null){
174+
treeNodeStack.push(popNode);
175+
176+
popNode = popNode.getlChild();
177+
}
178+
179+
popNode = treeNodeStack.pop();
180+
181+
System.out.print(popNode.getData() + " ");
182+
183+
popNode = popNode.getrChild();
184+
}
185+
186+
System.out.println();
187+
}
188+
189+
public void postBTreeNoRecur(){
190+
Stack<BTreeNode> treeNodeStack = new Stack<>();
191+
BTreeNode popNode = rootNode;
192+
while (true){
193+
while (popNode != null){
194+
treeNodeStack.push(popNode);
195+
196+
popNode = popNode.getlChild();
197+
}
198+
199+
while (!treeNodeStack.isEmpty() && treeNodeStack.peek().getrChild() == popNode){
200+
popNode = treeNodeStack.peek();
201+
202+
System.out.print(popNode.getData() + " ");
203+
204+
treeNodeStack.pop();
205+
}
206+
207+
if(treeNodeStack.isEmpty()){
208+
break;
209+
}
210+
211+
popNode = treeNodeStack.peek().getrChild();
212+
}
213+
214+
System.out.println();
215+
}
216+
217+
public static void main(String[] args){
218+
String treeStr = "abd##e##c#f##";
219+
BTree<String> bTree = new BTree<>();
220+
bTree.initRoot(treeStr);
221+
bTree.preBTree(bTree.rootNode, 1);
222+
223+
// System.out.println("btreeDepth : " + bTree.depthBTree(bTree.rootNode));
224+
//
225+
// bTree.levelTraverse();
226+
//
227+
// System.out.println("<=====================>");
228+
// System.out.println("nodeCount : " + bTree.nodeCount(bTree.rootNode));
229+
//
230+
// System.out.println("<=====================>");
231+
// System.out.println("leafNodeCount : " + bTree.leafNodeCount(bTree.rootNode));
232+
//
233+
// System.out.println("<######################################>");
234+
// bTree.levelTraverseNoRecur();
235+
//
236+
// System.out.println("<=====================>");
237+
// bTree.mirror(bTree.rootNode);
238+
// bTree.levelTraverse();
239+
240+
System.out.println("<================================>");
241+
bTree.preBTreeNoRecur();
242+
System.out.println("<================================>");
243+
bTree.middleBTreeNoRecur();
244+
System.out.println("<================================>");
245+
bTree.postBTreeNoRecur();
246+
System.out.println("<================================>");
247+
bTree.levelTraverse();
248+
249+
}
250+
}

‎src/com/dong/learn/algorithms/btree/BTreeNode.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.dong.learn.algorithms.btree;
2+
3+
/**
4+
* Created by coding-dong on 2017/10/24.
5+
*/
6+
public class BTreeNode<T extends String> {
7+
8+
private T data;
9+
10+
private BTreeNode lChild;
11+
12+
private BTreeNode rChild;
13+
14+
public T getData() {
15+
return data;
16+
}
17+
18+
public void setData(T data) {
19+
this.data = data;
20+
}
21+
22+
public BTreeNode getlChild() {
23+
return lChild;
24+
}
25+
26+
public void setlChild(BTreeNode lChild) {
27+
this.lChild = lChild;
28+
}
29+
30+
public BTreeNode getrChild() {
31+
return rChild;
32+
}
33+
34+
public void setrChild(BTreeNode rChild) {
35+
this.rChild = rChild;
36+
}
37+
}

0 commit comments

Comments
 (0)