Created
July 7, 2015 21:38
-
-
Save palianytsia/02e92f360ff3983c35e3 to your computer and use it in GitHub Desktop.
Binary tree, post-order traversal
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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