Last active
February 25, 2016 00:30
-
-
Save jrdalpra/c4ef40066c11268e9cba to your computer and use it in GitHub Desktop.
Java 8 BinaryTree
This file contains 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.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