Created
May 13, 2020 18:48
-
-
Save mbrc12/861a60e83eed89fb8d6466e31dfd1be7 to your computer and use it in GitHub Desktop.
A Binary-Tree ADT in Java using the Visitor pattern
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
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); | |
} | |
} |
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
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); | |
} | |
} |
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
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); | |
} | |
} |
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
public interface Tree<T> { | |
public T get(); | |
public <R> R accept(TreeVisitor<T, R> v); | |
} |
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.*; | |
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()); | |
} | |
} |
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
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