面试中遇到的手撸代码问题，技术不牢，没有IDE后感觉默写代码一点都想不起来，后来做出来后特此记录
题目
1 | * I |
代码实现
这样的输出就是前序遍历，可以用递归，也可以用栈的方式
- Tree数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24package vip.proyi.entity;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import vip.proyi.demo.BinaryTreeTest;
/**
* 〈二叉树〉
* @author ProYI
* @date 2019-03-23
*/
public class Tree {
private String data;
private Tree leftChild;
private Tree rightChild;
}
因为我这里引入了lombok，并使用其@Data注解简化了实体类中的get/set/tostring等方法，如果你还不了解lombok，可以了解一下，简化修改entity频繁修改时get/set等方法的频繁改动
- 遍历二叉树 BinaryTreeTest.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141package vip.proyi.demo;
import vip.proyi.entity.Tree;
import java.util.Stack;
/**
* 〈二叉树遍历〉
* @author ProYI
* @date 2019-03-23 0:41
*
* I
* / \
* am java
* / \ \
* a good developer
*
* 前序递归遍历算法：访问根结点-->递归遍历根结点的左子树-->递归遍历根结点的右子树
* 中序递归遍历算法：递归遍历根结点的左子树-->访问根结点-->递归遍历根结点的右子树
* 后序递归遍历算法：递归遍历根结点的左子树-->递归遍历根结点的右子树-->访问根结点
*/
public class BinaryTreeTest {
// 前序遍历递归的方式
public void preOrder(Tree tree) {
if (null != tree) {
System.out.print(tree.getData() + " ");
preOrder(tree.getLeftChild());
preOrder(tree.getRightChild());
}
}
// 中序遍历递归的方式
public void inOrder(Tree tree) {
if (null != tree) {
inOrder(tree.getLeftChild());
System.out.print(tree.getData() + " ");
inOrder(tree.getRightChild());
}
}
// 后序遍历递归的方式
public void postOrder(Tree tree) {
if (null != tree) {
postOrder(tree.getLeftChild());
postOrder(tree.getRightChild());
System.out.print(tree.getData() + " ");
}
}
// 堆栈方式
// 前序遍历非递归
public void preOrderNonRecursive(Tree tree) {
Stack<Tree> stack = new Stack<>();
while (true) {
while (tree != null) {
System.out.print(tree.getData() + " ");
stack.push(tree);
tree = tree.getLeftChild();
}
if (stack.isEmpty()) {
break;
}
tree = stack.pop();
tree = tree.getRightChild();
}
}
// 中序遍历非递归
public void inOrderNonRecursive(Tree tree) {
Stack<Tree> stack = new Stack<>();
while (true) {
while (tree != null) {
stack.push(tree);
tree = tree.getLeftChild();
}
if (stack.isEmpty()) {
break;
}
tree = stack.pop();
System.out.print(tree.getData() + " ");
tree = tree.getRightChild();
}
}
// 后序遍历非递归
public void postOrderNonRecursive(Tree tree) {
Stack<Tree> stack = new Stack<>();
while (true) {
if (tree != null) {
stack.push(tree);
tree = tree.getLeftChild();
} else {
if (stack.isEmpty()) {
return;
}
if (null == stack.lastElement().getRightChild()) {
tree = stack.pop();
System.out.print(tree.getData() + " ");
while (tree == stack.lastElement().getRightChild()) {
System.out.print(stack.lastElement().getData() + " ");
tree = stack.pop();
if (stack.isEmpty()) {
break;
}
}
}
if (!stack.isEmpty()) {
tree = stack.lastElement().getRightChild();
} else {
tree = null;
}
}
}
}
public static void main(String[] args) {
Tree node3 = new Tree("a", null, null);
Tree node4 = new Tree("good", null, null);
Tree node2 = new Tree("am", node3, node4);
Tree node6 = new Tree("developer", null, null);
Tree node5 = new Tree("java", null, node6);
Tree node1 = new Tree("I", node2, node5);
BinaryTreeTest tree = new BinaryTreeTest();
tree.preOrder(node1);
System.out.println();
tree.inOrder(node1);
System.out.println();
tree.postOrder(node1);
System.out.println();
tree.preOrderNonRecursive(node1);
System.out.println();
tree.inOrderNonRecursive(node1);
System.out.println();
tree.postOrderNonRecursive(node1);
}
}