Sollicitatievraag bij Nextlabs
2. Implement the following interface to implement a binary search tree in Java public interface BinaryTree<T extends Comparable<? super T>> { public void insert(T data); public T findMin(); public boolean contains(T data); public void remove(T data); } 2.1. (optional) What does T extends Comparable< super T>> mean? Ans: It means that T has to be of type Comparable, which can avoid redundantly specifying type parameters
Antwoord op sollicitatievraag
Anoniem
/*************************************************************************** * INSERT ****************************************************************************/ public void insert(T data) { root = insert(root, data); } private Node insert(Node p, T toInsert) { if (p == null) return new Node(toInsert); if (toInsert.compareTo(p.data) == 0) return p; if (toInsert.compareTo(p.data) findMin( Node t ) { if( t == null ) return null; else if( t.left == null ) return t; return findMin( t.left ); } /*************************************************************************** * CONTAINS ****************************************************************************/ public boolean contains(T data) { return contains(root, data); } private boolean contains(Node p, T toSearch) { if (p == null) return false; else if (toSearch.compareTo(p.data) == 0) return true; else if (toSearch.compareTo(p.data) remove(Node p, T d) { if (p == null) throw new RuntimeException("cannot be remove."); else if (d.compareTo(p.data) 0) p.right = delete (p.right, d); else { if (p.left == null) return p.right; else if (p.right == null) return p.left; else { Node tmp = new Node(retrieveData(p.left)); tmp.left = delete(p.left, tmp.data) ; tmp.right = p.right; p = tmp; } } return p; } private T retrieveData(Node p) { while (p.right != null) p = p.right; return p.data; }