forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBTreeIterator.java
More file actions
101 lines (88 loc) · 2.41 KB
/
BTreeIterator.java
File metadata and controls
101 lines (88 loc) · 2.41 KB
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
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;
public class BTreeIterator {
private Node root;
private Stack<Node> stack;
private Stack<Node> preOrderStack;
private Queue<Node> postOrderQueue;
public BTreeIterator(Node n) {
root = n;
stack = new Stack<Node>();
pushLeft(root);
// for post-order, no need for in-order
postOrderQueue = new LinkedList<Node>();
pushPostOrder(root);
// for pre-order
preOrderStack = new Stack<Node>();
preOrderStack.push(root);
}
//in-order
public boolean hasNext() {
return !stack.isEmpty();
}
public void reset() {
stack.empty();
postOrderQueue.clear();
pushLeft(root);
}
public void remove() {
throw new java.lang.UnsupportedOperationException("remove");
}
public Node next() {
return inOrderNext();
}
// in-order : left, root, right
public Node inOrderNext() {
if (hasNext()) {
Node node = stack.pop();
pushLeft(node.right);
return node;
} else {
throw new NoSuchElementException();
}
}
private void pushLeft(Node node) {
if (node != null) {
stack.push(node);
pushLeft(node.left);
}
}
public boolean hasNextPreOrder(){
return !preOrderStack.isEmpty();
}
//pre-order: root, left, right
public Node preOrderNext() {
if (!preOrderStack.isEmpty()) {
Node node = preOrderStack.pop();
if (node.right != null)
preOrderStack.push(node.right);
if (node.left != null)
preOrderStack.push(node.left);
return node;
} else {
return null;
}
}
public void pushPostOrder(Node n){
if(n == null)
return;
if(n.left != null)
pushPostOrder(n.left);
if(n.right != null)
pushPostOrder(n.right);
postOrderQueue.add(n);
}
public boolean hasNextPostOrder(){
return !postOrderQueue.isEmpty();
}
//post-order: left, right, root
public Node postOrderNext() {
if (!postOrderQueue.isEmpty()) {
return postOrderQueue.poll();
} else {
throw new NoSuchElementException();
}
}
}