FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

algorithm/PuzzleCoding/src/BTreeIterator.java at master · wodgithub/algorithm · GitHub

Repository navigation

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();

}

}

}

Back | FazBrowse Home | New Git URL