Skip to content

Instantly share code, notes, and snippets.

@jrdalpra
Last active February 25, 2016 00:30
Show Gist options
  • Save jrdalpra/c4ef40066c11268e9cba to your computer and use it in GitHub Desktop.
Save jrdalpra/c4ef40066c11268e9cba to your computer and use it in GitHub Desktop.
Java 8 BinaryTree
import java.util.function.Consumer;
import lombok.ToString;
import lombok.val;
@ToString
public class BinaryTree<T extends Comparable<T>> {
private final Node<T> root;
public BinaryTree(Node<T> root) {
this.root = root;
this.root.level = 0;
}
public BinaryTree<T> insert(Node<T> child) {
this.root.insert(child);
return this;
}
public Integer levels() {
return this.root.levels();
}
public void visit(final VisitorAlgorithm<T> visitor) {
this.visit(visitor, null);
}
public void visit(final VisitorAlgorithm<T> visitor, Consumer<Node<T>> lastAction) {
this.root.visit(visitor);
if (lastAction != null)
lastAction.accept(this.root);
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object obj) {
if (!(obj instanceof BinaryTree))
return false;
val other = (BinaryTree<T>) obj;
return this.root.equals(other.root);
}
@ToString
public static class Node<T extends Comparable<T>> implements Comparable<Node<T>> {
private final T content;
private Node<T> left;
private Node<T> right;
private Integer level;
public Node(T content) {
this.content = content;
}
public Integer levels() {
val left = this.left == null ? this.level : this.left.levels();
val right = this.right == null ? this.level : this.right.levels();
return Math.max(left, right);
}
public void visit(VisitorAlgorithm<T> visitor) {
visitor.accept(this);
}
public Node<T> insert(Node<T> child) {
int comparision = child.content.compareTo(this.content);
if (comparision < 0) {
if (this.left == null) {
this.left = child;
this.left.level = this.level + 1;
return this;
}
this.left.insert(child);
return this;
}
if (comparision >= 0) {
if (this.right == null) {
this.right = child;
this.right.level = this.level + 1;
return this;
}
this.right.insert(child);
return this;
}
return this;
}
@Override
public int compareTo(Node<T> o) {
return this.content.compareTo(o.content);
}
@SuppressWarnings({ "unchecked", "rawtypes" })
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Node))
return false;
val other = (Node) obj;
return this.contentEquals(other) && this.leftEquals(other) && this.rightEquals(other);
}
private boolean leftEquals(Node<T> other) {
if (this.left == null && other.left == null)
return true;
return this.left != null && other.left != null && this.left.equals(other.left);
}
private boolean rightEquals(Node<T> other) {
if (this.right == null && other.right == null)
return true;
return this.right != null && other.right != null && this.right.equals(other.right);
}
private boolean contentEquals(Node<T> other) {
if (this.content == null && other.content == null)
return true;
return this.content != null && other.content != null && this.content.compareTo((T) other.content) == 0;
}
}
@FunctionalInterface
public static interface VisitorAlgorithm<T extends Comparable<T>> extends Consumer<Node<T>> {
}
public static class InOrder<T extends Comparable<T>> implements VisitorAlgorithm<T> {
private final VisitorAlgorithm<T> visitor;
public InOrder(VisitorAlgorithm<T> visitor) {
this.visitor = visitor;
}
@Override
public void accept(Node<T> node) {
if (node == null)
return;
accept(node.left);
visitor.accept(node);
accept(node.right);
}
}
public static class PostOrder<T extends Comparable<T>> implements VisitorAlgorithm<T> {
private final VisitorAlgorithm<T> visitor;
public PostOrder(VisitorAlgorithm<T> visitor) {
this.visitor = visitor;
}
@Override
public void accept(Node<T> node) {
if (node == null)
return;
accept(node.left);
accept(node.right);
this.visitor.accept(node);
}
}
public static class PreOrder<T extends Comparable<T>> implements VisitorAlgorithm<T> {
private final VisitorAlgorithm<T> visitor;
public PreOrder(VisitorAlgorithm<T> visitor) {
this.visitor = visitor;
}
@Override
public void accept(Node<T> node) {
if (node == null)
return;
this.visitor.accept(node);
accept(node.left);
accept(node.right);
}
}
public static class FrontToBack<T extends Comparable<T>> implements VisitorAlgorithm<T> {
private final VisitorAlgorithm<T> visitor;
private final T comparable;
public FrontToBack(final VisitorAlgorithm<T> visitor, final T comparable) {
this.visitor = visitor;
this.comparable = comparable;
}
@Override
public void accept(Node<T> node) {
if (node == null)
return;
int comparision = node.content.compareTo(comparable);
if (comparision > 0) {
accept(node.left);
this.visitor.accept(node);
accept(node.right);
return;
}
if (comparision <= 0) {
accept(node.right);
this.visitor.accept(node);
accept(node.left);
return;
}
}
}
public static void main(String[] args) {
val t1 = new BinaryTree<Integer>(new Node<>(5));
t1.insert(new Node<>(1));
t1.insert(new Node<>(8));
t1.insert(new Node<>(6));
t1.insert(new Node<>(3));
t1.insert(new Node<>(9));
t1.insert(new Node<>(1));
t1.insert(new Node<>(8));
System.out.println(t1.levels());
val t2 = new BinaryTree<Integer>(new Node<>(5));
t2.insert(new Node<>(1));
t2.insert(new Node<>(8));
t2.insert(new Node<>(6));
t2.insert(new Node<>(3));
t2.insert(new Node<>(9));
t2.insert(new Node<>(1));
t2.insert(new Node<>(8));
System.out.println(t1.equals(t2));
t1.visit(new PreOrder<>(n -> System.out.print(n.content + " ")), n -> System.out.println());
t1.visit(new InOrder<>(n -> System.out.print(n.content + " ")), n -> System.out.println());
t1.visit(new PostOrder<>(n -> System.out.print(n.content + " ")), n -> System.out.println());
t1.visit(new FrontToBack<>(n -> System.out.print(n.content + " "), 7), n -> System.out.println());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment