Skip to content

Commit c7e8bbb

Browse files
byhiegbyhieg
committed
添加树的相关算法
1 parent cda002d commit c7e8bbb

3 files changed

Lines changed: 267 additions & 0 deletions

File tree

‎images/Thumbs.db‎

11 KB
Binary file not shown.

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

Lines changed: 188 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,188 @@
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 [email protected]
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+
public static int getLeafs(Node root) {
166+
if (root == null) {
167+
return 0;
168+
}
169+
if (root.right == null && root.left == null) {
170+
return 1;
171+
}
172+
return getLeafs(root.left) + getLeafs(root.right);
173+
174+
}
175+
176+
public static class Node {
177+
public int data;
178+
public Node left;
179+
public Node right;
180+
181+
182+
public Node(int data) {
183+
this.data = data;
184+
left = null;
185+
right = null;
186+
}
187+
}
188+
}

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

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package cn.byhieg.algorithmtutorialtest;
2+
3+
import cn.byhieg.algorithmtutorial.BinaryTree;
4+
import cn.byhieg.iotutorial.bytestreamio.BufferdInputStreamExample;
5+
import junit.framework.TestCase;
6+
7+
/**
8+
* Created by byhieg on 17/4/15.
9+
* Mail to [email protected]
10+
*/
11+
public class BinaryTreeTest extends TestCase {
12+
13+
14+
BinaryTree.Node root = new BinaryTree.Node(1);
15+
public void setUp() throws Exception {
16+
super.setUp();
17+
BinaryTree.Node[] nodes = new BinaryTree.Node[10];
18+
nodes[0] = new BinaryTree.Node(2);
19+
root.left = nodes[0];
20+
for (int i = 1 ; i < 10;i++) {
21+
nodes[i] = new BinaryTree.Node(2 + i);
22+
if (i % 2 == 0){
23+
nodes[i - 1].left = nodes[i];
24+
}else{
25+
nodes[i - 1].right = nodes[i];
26+
}
27+
}
28+
29+
}
30+
31+
public void tearDown() throws Exception {
32+
System.out.println();
33+
}
34+
35+
public void testPreOrder1() throws Exception {
36+
System.out.println("递归的先续遍历");
37+
BinaryTree.preOrder1(root);
38+
}
39+
40+
public void testPreOrder2() throws Exception {
41+
System.out.println("非递归的先续遍历");
42+
BinaryTree.preOrder2(root);
43+
}
44+
45+
46+
public void testInOrder1() throws Exception {
47+
System.out.println("递归的中序遍历");
48+
BinaryTree.inOrder1(root);
49+
}
50+
51+
public void testInOrder2() throws Exception {
52+
System.out.println("非递归的中序遍历");
53+
BinaryTree.inOrder2(root);
54+
}
55+
56+
public void testPostOrder1() throws Exception {
57+
System.out.println("递归的后续遍历");
58+
BinaryTree.postOrder1(root);
59+
}
60+
61+
public void testPostOrder2() throws Exception {
62+
System.out.println("非递归的后续遍历");
63+
BinaryTree.postOrder2(root);
64+
}
65+
66+
public void testLevelOrder() throws Exception {
67+
System.out.println("层次遍历");
68+
BinaryTree.levelOrder(root);
69+
}
70+
71+
public void testGetNodes() throws Exception {
72+
System.out.println("节点数" + BinaryTree.getNodes(root));
73+
}
74+
75+
public void testGetLeafs() throws Exception {
76+
System.out.println("叶子数" + BinaryTree.getLeafs(root));
77+
}
78+
79+
}

0 commit comments

Comments
 (0)