Skip to content

Instantly share code, notes, and snippets.

@palianytsia
Created July 7, 2015 21:38
Show Gist options
  • Save palianytsia/02e92f360ff3983c35e3 to your computer and use it in GitHub Desktop.
Save palianytsia/02e92f360ff3983c35e3 to your computer and use it in GitHub Desktop.
Binary tree, post-order traversal
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* Binary tree, post-order traversal
*
* @author Ivan Palianytsia
*
*/
public class BinaryTree implements Iterable<Integer> {
private Node root = null;
public void setRoot(Node node) {
this.root = node;
}
public Node getRoot() {
return this.root;
}
public static class Node {
private Node parent;
private Node leftChild;
private Node rightChild;
private final int value;
public Node(int value) {
this.value = value;
}
public void setLeftChild(Node node) {
this.leftChild = node;
node.parent = this;
}
public void setRightChild(Node node) {
this.rightChild = node;
node.parent = this;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
}
@Override
public Iterator<Integer> iterator() {
return new MyIterator(root);
}
public List<Integer> toList() {
List<Integer> values = new LinkedList<>();
if (root != null) {
fillValues(root, values);
}
return values;
}
private void fillValues(Node node, List<Integer> values) {
if (node.leftChild != null) {
fillValues(node.leftChild, values);
}
if (node.rightChild != null) {
fillValues(node.rightChild, values);
}
values.add(node.value);
}
private static class MyIterator implements Iterator<Integer> {
private Node nextNode = null;
public MyIterator(Node root) {
this.nextNode = root;
while (nextNode.leftChild != null || nextNode.rightChild != null) {
if (nextNode.leftChild != null) {
nextNode = nextNode.leftChild;
} else {
nextNode = nextNode.rightChild;
}
}
}
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public Integer next() {
Node toReturn = nextNode;
if (toReturn.parent == null) {
nextNode = null;
} else if (toReturn.parent.rightChild == null || toReturn.parent.rightChild == toReturn) {
nextNode = toReturn.parent;
} else {
Node node = toReturn.parent.rightChild;
while (node.leftChild != null && node.rightChild != null) {
if (node.leftChild != null) {
node = node.leftChild;
}
}
nextNode = node;
}
return toReturn.value;
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.setRoot(new BinaryTree.Node(1));
tree.root.setLeftChild(new BinaryTree.Node(2));
tree.root.setRightChild(new BinaryTree.Node(3));
tree.root.leftChild.setLeftChild(new BinaryTree.Node(4));
tree.root.leftChild.leftChild.setRightChild(new BinaryTree.Node(5));
Iterator<Integer> iterator = tree.iterator();
while (iterator.hasNext()) {
Integer i = iterator.next();
System.out.println(i);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment