Download code

Jump to: navigation, search

Back to Binary_search_tree_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

BinaryTree.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Binary_search_tree_(Java)?oldid=18914
 14 */
 15 
 16 import java.util.List;
 17 import java.util.ArrayList;
 18 import java.util.Arrays;
 19 import static org.junit.Assert.*;
 20 import org.junit.Test;
 21 
 22 class Node<E extends Comparable<? super E>> {
 23 	public Node<E> left;
 24 	public Node<E> right;
 25 	public final E value;
 26 	Node(E value) {
 27 		this.value = value;
 28 	}
 29 	Node(Node<E> node) {
 30 		left = node.left;
 31 		right = node.right;
 32 		value = node.value;
 33 	}
 34 }
 35     
 36 public class BinaryTree<E extends Comparable<? super E>> {
 37 	Node<E> root;
 38 	int size = 0;
 39 	int i;
 40 	@Test
 41 	public void testTree() {
 42 		
 43 		BinaryTree<String> tree = new BinaryTree<String>();
 44 		tree.add("Hanno");
 45 		tree.add("Zacharias");
 46 		tree.add("Berhard");
 47 		assertEquals(new String[]{ "Berhard", "Hanno", "Zacharias" }, tree.toList().toArray(new String[3]));
 48 		assertEquals(null, tree.get("Otto"));
 49 		assertEquals("Hanno", tree.get("Hanno"));
 50 	}
 51 	
 52 	public void add(E element) {
 53 	    if (root == null && element != null) {
 54 	        root = new Node<E>(element);
 55 	        size++;
 56 	    } else if (element != null) {
 57 	        root = insert(root, element);
 58 	    }
 59 	}
 60 
 61 	private Node<E> insert(Node<E> node, E value) {
 62 		Node<E> result = new Node<E>(node);
 63 		int compare = result.value.compareTo(value);
 64 		
 65 		if (compare == 0) {
 66 		    return result;
 67 		}
 68 		
 69 		if (compare > 0) {
 70 		    if (result.left != null) {
 71 		        result.left = insert(result.left, value);
 72 		    } else {
 73 		        result.left = new Node<E>(value);
 74 		        size++;
 75 		    }
 76 		}
 77 		
 78 		else if (compare < 0) {
 79 		    if (result.right != null) {
 80 		        result.right = insert(result.right, value);
 81 		    } else {
 82 		        result.right = new Node<E>(value);
 83 		        size++;
 84 		    }
 85 		}
 86 		return result;
 87 	}
 88 	
 89 	public E get(E key) {
 90 	    if (root == null)
 91 	        return null;
 92 
 93 	    Node<E> node = root;
 94 	    int compareResult;
 95 	    while ((compareResult = node.value.compareTo(key)) != 0) {
 96 	        if (compareResult > 0) {
 97 	            if (node.left != null)
 98 	                node = node.left;
 99 	            else
100 	                return null;
101 	        } else {
102 	            if (node.right != null)
103 	                node = node.right;
104 	            else
105 	                return null;
106 	        }
107 	    }
108 	    return node.value;
109 	}
110 	
111 	public List<E> toList() {
112 	    List<E> result = new ArrayList<E>();
113 	    treeToList(root, result);
114 	    return result;
115 	}
116 	
117 	private void treeToList(Node<E> node, List<E> goal) {
118 	    if (node != null) {
119 	        treeToList(node.left, goal);
120 	        goal.add(node.value);
121 	        treeToList(node.right, goal);
122 	    }
123 	}
124 }


hijacker
hijacker
hijacker
hijacker