Skip to content

Instantly share code, notes, and snippets.

@mbrc12
Created May 13, 2020 18:48
Show Gist options
  • Save mbrc12/861a60e83eed89fb8d6466e31dfd1be7 to your computer and use it in GitHub Desktop.
Save mbrc12/861a60e83eed89fb8d6466e31dfd1be7 to your computer and use it in GitHub Desktop.
A Binary-Tree ADT in Java using the Visitor pattern
public class Branch<T> implements Tree<T>{
private T elem;
private Tree<T> left;
private Tree<T> right;
public Branch(T elem, Tree<T> left, Tree<T> right) {
this.elem = elem;
this.left = left;
this.right = right;
}
public T get() {
return elem;
}
public Tree<T> left() {
return left;
}
public Tree<T> right() {
return right;
}
public <R> R accept(TreeVisitor<T, R> visitor) {
return visitor.onBranch(this);
}
}
public class Leaf<T> implements Tree<T>{
private T elem;
public Leaf(T elem) {
this.elem = elem;
}
public T get() {
return elem;
}
public <R> R accept(TreeVisitor<T, R> visitor) {
return visitor.onLeaf(this);
}
}
public class Main {
static <T> void prettyPrint(Tree<T> t) {
t.accept(new TreeMatcher<T, Void> (
(T x) -> {
System.out.println("Leaf ".concat(x.toString()));
return null;
},
(T x, Tree<T> left, Tree<T> right) -> {
System.out.println("Branch ".concat(x.toString()).concat(" ["));
prettyPrint(left);
prettyPrint(right);
System.out.println("] ");
return null;
}));
}
public static void main(String[] args) {
Tree<Long> T = new Branch<>(3L, new Leaf<>(5L), new Branch<>(9L, new Leaf<>(4L), new Leaf<>(6L)));
prettyPrint(T);
}
}
public interface Tree<T> {
public T get();
public <R> R accept(TreeVisitor<T, R> v);
}
import java.util.function.*;
public class TreeMatcher<T, R> implements TreeVisitor<T, R> {
public interface LeafAction<T, R> {
public R apply(T x);
}
public interface BranchAction<T, A, B, R> {
public R apply(T x, A left, B right);
}
public LeafAction<T, R> leafAction;
public BranchAction<T, Tree<T>, Tree<T>, R> branchAction;
public TreeMatcher(LeafAction<T, R> leaf, BranchAction<T, Tree<T>, Tree<T>, R> branch) {
this.leafAction = leaf;
this.branchAction = branch;
}
public R onLeaf(Leaf<T> leaf) {
return leafAction.apply(leaf.get());
}
public R onBranch(Branch<T> branch) {
return branchAction.apply(branch.get(), branch.left(), branch.right());
}
}
public interface TreeVisitor<T, R> {
public R onLeaf(Leaf<T> leaf);
public R onBranch(Branch<T> branch);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment