Last active
November 28, 2018 22:05
-
-
Save TwoTau/646343374e9addd82206f3f823081feb to your computer and use it in GitHub Desktop.
Ayy this is the Best Tree implementation
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.Scanner; | |
public class BestTree<E extends Comparable<E>> { | |
private TreeNode overallRoot; | |
public BestTree(TreeNode root) { | |
overallRoot = root; | |
} | |
public BestTree() { | |
this(null); | |
} | |
// Adds the given element to the tree in sorted order | |
public void addSorted(E data) { | |
overallRoot = addSorted(overallRoot, data); | |
} | |
private TreeNode addSorted(TreeNode root, E data) { | |
if (root == null) return new TreeNode(data); | |
int compareTo = data.compareTo(root.data); | |
if (compareTo < 0) { // data <= root | |
root.left = addSorted(root.left, data); | |
} else if (compareTo > 0) { // data > root | |
root.right = addSorted(root.right, data); | |
} | |
return root; | |
} | |
private void remove(E data) { | |
overallRoot = remove(overallRoot, data); | |
} | |
private TreeNode remove(TreeNode root, E data) { | |
System.out.println(" / " + root); | |
if (root == null) return null; | |
int compareTo = data.compareTo(root.data); | |
if (compareTo < 0) { // data < root | |
root.left = remove(root.left, data); | |
} else if (compareTo > 0) { // data > root | |
root.right = remove(root.right, data); | |
} else { // data == root, have to delete this node | |
if (root.left == null && root.right == null) { | |
return null; | |
} else if (root.left == null && root.right != null) { | |
return root.right; | |
} else if (root.left != null && root.right == null) { | |
return root.left; | |
} else { // has both left and right nodes | |
Object[] removeMin = removeMin(root.right); | |
root.right = (TreeNode) removeMin[0]; | |
root.data = (E) removeMin[1]; | |
} | |
} | |
return root; | |
} | |
private Object[] removeMin(TreeNode root) { | |
if (root.left == null) { | |
Object[] result = new Object[2] { | |
root, | |
root.data | |
}; | |
return result; | |
} | |
} | |
// returns whether the tree contains the given value, | |
// only works if this is a binary search tree. | |
public boolean contains(E value) { | |
return contains(overallRoot, value); | |
} | |
private boolean contains(TreeNode root, E value) { | |
if (root == null) return false; | |
if (value.compareTo(root.data) < 0) return contains(root.left, value); | |
if (value.compareTo(root.data) > 0) return contains(root.right, value); | |
return true; | |
} | |
public void fillToDepth(int depth, E defaultValue) { | |
overallRoot = fillToDepth(overallRoot, depth, defaultValue); | |
} | |
private TreeNode fillToDepth(TreeNode root, int depth, E defaultValue) { | |
if (depth > 0) { | |
if (root == null) return new TreeNode(defaultValue); | |
root.left = fillToDepth(root.left, depth - 1, defaultValue); | |
root.right = fillToDepth(root.right, depth - 1, defaultValue); | |
} | |
return root; | |
} | |
// Prints contents of tree through in-order traversal | |
public String toString() { | |
return nodeToString(overallRoot).substring(1); | |
} | |
private String nodeToString(TreeNode root) { | |
return (root == null) ? "" : nodeToString(root.left) + "." + | |
root.data.toString() + nodeToString(root.right); | |
} | |
public void printSideways() { | |
printSideways(overallRoot, 0); | |
} | |
private void printSideways(TreeNode root, int depth) { | |
String indentation = new String(new char[depth]).replace("\0", "...."); | |
if (root != null) { | |
printSideways(root.right, depth + 1); | |
System.out.println(indentation + root.data); | |
printSideways(root.left, depth + 1); | |
} | |
} | |
public static void main(String[] args) { | |
System.out.println("Best Tree v1.0\n==============\n"); | |
BestTree<Integer> tree = new BestTree<Integer>(); | |
tree.addSorted(25); | |
for (int i = 0; i < 10; i++) { | |
tree.addSorted((int) (Math.random() * 50 + 1)); | |
} | |
// tree.fillToDepth(4, -1); | |
System.out.println("In order: " + tree); | |
System.out.println("Tree: " + tree); | |
System.out.println("\nSideways Tree:"); | |
tree.printSideways(); | |
Scanner input = new Scanner(System.in); | |
System.out.print("Delete: "); | |
while (input.hasNextInt()) { | |
int n = input.nextInt(); | |
tree.remove(n); | |
tree.printSideways(); | |
System.out.print("\nDelete: "); | |
} | |
} | |
private class TreeNode { | |
public E data; | |
public TreeNode left; | |
public TreeNode right; | |
public TreeNode(E data, TreeNode left, TreeNode right) { | |
this.data = data; | |
this.left = left; | |
this.right = right; | |
} | |
public TreeNode(E data) { | |
this(data, null, null); | |
} | |
public String toString() { | |
return "(" + data.toString() + ")"; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment