Last active
May 11, 2018 21:18
-
-
Save ethanjurman/0526ca250f17467b39c4e1c033c0c3b0 to your computer and use it in GitHub Desktop.
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
| // one class needs to have a main() method | |
| public class HelloWorld | |
| { | |
| // arguments are passed using the text field below this editor | |
| public static void main(String[] args) | |
| { | |
| Node<Integer> nodeA = new Node<>(1); | |
| Node<Integer> nodeB = new Node<>(2); | |
| Node<Integer> nodeC = new Node<>(3); | |
| Node<Integer> nodeD = new Node<>(4); | |
| Node<Integer> nodeE = new Node<>(5); | |
| Node<Integer> nodeF = new Node<>(6); | |
| Node<Integer> nodeG = new Node<>(7); | |
| nodeA.insert(nodeB).insert(nodeC).insert(nodeD).insert(nodeE).insert(nodeF).insert(nodeG); | |
| Node<Integer> nodeFound = nodeA.findNode(2); | |
| System.out.println(nodeA.getString()); | |
| System.out.println(nodeA.getSize()); | |
| System.out.println(nodeFound.getString()); | |
| nodeC.delete(); | |
| System.out.println(nodeA.getString()); | |
| } | |
| } | |
| // you can add other public classes to this editor in any order | |
| public class Node<T> | |
| { | |
| // Our Binary Tree Node has 4 values | |
| // leftChild, rightChild, a parent, and a value. | |
| // the value is a generic type, so it could store a String, int, boolean, etc... | |
| // the parent is ONLY necessary for the purposes of deleting nodes. | |
| public Node<T> leftChild; | |
| public Node<T> rightChild; | |
| public Node<T> parent; | |
| public T value; | |
| // initialize the Node with a value of generic type | |
| public Node(T initialValue) { | |
| value = initialValue; | |
| } | |
| // we can calculate the size of all nodes by counting it's left and right children, | |
| // + 1 for the node we are on right now. | |
| public int getSize() { | |
| int leftSize = leftChild != null ? leftChild.getSize() : 0; | |
| int rightSize = rightChild != null ? rightChild.getSize() : 0; | |
| return 1 + leftSize + rightSize; | |
| } | |
| // return if the node we are on is a left sibling | |
| public boolean isLeftChild() { | |
| return parent.leftChild == this; | |
| } | |
| // return if the node we are on is a right sibling | |
| public boolean isRightChild() { | |
| return parent.rightChild == this; | |
| } | |
| // if left/ right child is null, insert node there | |
| // if both are not null, check which one is smaller and insert it to the smaller one. | |
| public Node<T> insert(Node<T> node) { | |
| if (leftChild == null) { | |
| leftChild = node; | |
| node.parent = this; | |
| } else if (rightChild == null) { | |
| rightChild = node; | |
| node.parent = this; | |
| } else if (leftChild.getSize() <= rightChild.getSize()) { | |
| leftChild.insert(node); | |
| } else { | |
| rightChild.insert(node); | |
| } | |
| return this; | |
| } | |
| // recurse down until we find a node with no children | |
| public Node<T> getLeafNode() { | |
| if (leftChild == null && rightChild == null) { | |
| return this; | |
| } else if (leftChild != null) { | |
| return leftChild.getLeafNode(); | |
| } else { | |
| return rightChild.getLeafNode(); | |
| } | |
| } | |
| // replace this node on by grabbing our parent, | |
| // and change it's left/ right child value (depending on what sibling we are). | |
| public void replace(Node<T> replacement) { | |
| if (this.isLeftChild()) { | |
| parent.leftChild = replacement; | |
| } else if (this.isRightChild()) { | |
| parent.rightChild = replacement; | |
| } | |
| } | |
| // if we have no left child (but we do have a right child) | |
| // then replace this node with the right child tree | |
| // if we have no right child (but we do have a left child) | |
| // then replace this node with the left child tree | |
| // if we have both a left and right child, then replace our value with a leaf node | |
| // then delete the leaf node | |
| // else (we have no children) just delete us. | |
| public void delete() { | |
| if (leftChild == null && rightChild != null) { | |
| replace(rightChild); | |
| } else if (rightChild == null && leftChild != null) { | |
| replace(leftChild); | |
| } else if (rightChild != null && leftChild != null) { | |
| value = getLeafNode().value; | |
| getLeafNode().replace(null); | |
| } else { | |
| replace(null); | |
| } | |
| } | |
| // search for a node | |
| // if the value we are looking for is here, then just return us | |
| // if not | |
| // search our left children, and our right children | |
| // return null no value can be found from either branch. | |
| public Node<T> findNode(T searchValue) { | |
| if (value == searchValue) { | |
| return this; | |
| } | |
| if (leftChild != null) { | |
| Node<T> leftSearch = leftChild.findNode(searchValue); | |
| if (leftSearch != null) { | |
| return leftSearch; | |
| } | |
| } | |
| if (rightChild != null) { | |
| Node<T> rightSearch = rightChild.findNode(searchValue); | |
| if (rightSearch != null) { | |
| return rightSearch; | |
| } | |
| } | |
| return null; | |
| } | |
| // a nice way to print the tree | |
| public String getString() { | |
| String leftString = leftChild != null ? leftChild.getString() : ""; | |
| String rightString = rightChild != null ? rightChild.getString() : ""; | |
| return "(" + leftString + " " + value + " " + rightString + ")"; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment