binary search tree - TreeNode cannot be cast to java.lang.Comparable? -
i trying write method returns parent specified node (bst), keep getting this:
treenode cannot cast java.lang.comparable any suggestions on how fix this? thanks!
here method (is located @ end!) - (the whole code):
import java.util.arraylist; import chapter27.abstracttree; public class test<e extends comparable<e>> extends abstracttree<e> { protected treenode<e> root; protected int size = 0; /** create default binary tree */ public test() { } /** create binary tree array of objects */ public test(e[] objects) { (int = 0; < objects.length; i++) insert(objects[i]); } @override /** returns true if element in tree */ public boolean search(e e) { treenode<e> current = root; // start root while (current != null) { if (e.compareto(current.element) < 0) { current = current.left; } else if (e.compareto(current.element) > 0) { current = current.right; } else // element matches current.element return true; // element found } return false; } @override /** insert element o binary tree * return true if element inserted */ public boolean insert(e e) { if (root == null) root = createnewnode(e); // create new root else { // locate parent node treenode<e> parent = null; treenode<e> current = root; while (current != null) if (e.compareto(current.element) < 0) { parent = current; current = current.left; } else if (e.compareto(current.element) > 0) { parent = current; current = current.right; } else return false; // duplicate node not inserted // create new node , attach parent node if (e.compareto(parent.element) < 0) parent.left = createnewnode(e); else parent.right = createnewnode(e); } size++; return true; // element inserted } protected treenode<e> createnewnode(e e) { return new treenode<e>(e); } @override /** inorder traversal root*/ public void inorder() { inorder(root); } /** inorder traversal subtree */ protected void inorder(treenode<e> root) { if (root == null) return; inorder(root.left); system.out.print(root.element + " "); inorder(root.right); } @override /** postorder traversal root */ public void postorder() { postorder(root); } /** postorder traversal subtree */ protected void postorder(treenode<e> root) { if (root == null) return; postorder(root.left); postorder(root.right); system.out.print(root.element + " "); } @override /** preorder traversal root */ public void preorder() { preorder(root); } /** preorder traversal subtree */ protected void preorder(treenode<e> root) { if (root == null) return; system.out.print(root.element + " "); preorder(root.left); preorder(root.right); } /** inner class static, because not access instance members defined in outer class */ public static class treenode<e extends comparable<e>> { public e element; public treenode<e> left; public treenode<e> right; public treenode<e> parent; public treenode(e e) { element = e; } } @override /** number of nodes in tree */ public int getsize() { return size; } /** returns root of tree */ public treenode<e> getroot() { return root; } /** returns path root leading specified element */ public java.util.arraylist<treenode<e>> path(e e) { java.util.arraylist<treenode<e>> list = new java.util.arraylist<treenode<e>>(); treenode<e> current = root; // start root while (current != null) { list.add(current); // add node list if (e.compareto(current.element) < 0) { current = current.left; } else if (e.compareto(current.element) > 0) { current = current.right; } else break; } return list; // return array of nodes } @override /** delete element binary tree. * return true if element deleted * return false if element not in tree */ public boolean delete(e e) { // locate node deleted , locate parent node treenode<e> parent = null; treenode<e> current = root; while (current != null) { if (e.compareto(current.element) < 0) { parent = current; current = current.left; } else if (e.compareto(current.element) > 0) { parent = current; current = current.right; } else break; // element in tree pointed @ current } if (current == null) return false; // element not in tree // case 1: current has no left children if (current.left == null) { // connect parent right child of current node if (parent == null) { root = current.right; } else { if (e.compareto(parent.element) < 0) parent.left = current.right; else parent.right = current.right; } } else { // case 2: current node has left child // locate rightmost node in left subtree of // current node , parent treenode<e> parentofrightmost = current; treenode<e> rightmost = current.left; while (rightmost.right != null) { parentofrightmost = rightmost; rightmost = rightmost.right; // keep going right } // replace element in current element in rightmost current.element = rightmost.element; // eliminate rightmost node if (parentofrightmost.right == rightmost) parentofrightmost.right = rightmost.left; else // special case: parentofrightmost == current parentofrightmost.left = rightmost.left; } size--; return true; // element inserted } @override /** obtain iterator. use inorder. */ public java.util.iterator<e> iterator() { return new inorderiterator(); } // inner class inorderiterator private class inorderiterator implements java.util.iterator<e> { // store elements in list private java.util.arraylist<e> list = new java.util.arraylist<e>(); private int current = 0; // point current element in list public inorderiterator() { inorder(); // traverse binary tree , store elements in list } /** inorder traversal root*/ private void inorder() { inorder(root); } /** inorder traversal subtree */ private void inorder(treenode<e> root) { if (root == null)return; inorder(root.left); list.add(root.element); inorder(root.right); } @override /** more elements traversing? */ public boolean hasnext() { if (current < list.size()) return true; return false; } @override /** current element , move next */ public e next() { return list.get(current++); } @override /** remove current element */ public void remove() { delete(list.get(current)); // delete current element list.clear(); // clear list inorder(); // rebuild list } } /** remove elements tree */ public void clear() { root = null; size = 0; } public treenode<e> getparent(treenode<e> node) { treenode<e> parent = null; treenode<e> current = root; while (current != null) { if (((comparable<e>)node.element).compareto((e)current.element) < 0) { parent = current; current = current.left; } else if (((comparable<e>) node.element).compareto((e)current.element) > 0) { parent = current; current = current.right; } else { break; } } size++; return parent; } public arraylist<treenode<e>> getpath(treenode<e> node) { return null; } public static void main(string[] args) { integer[] numbers = {2, 4, 3, 1, 8, 5, 6, 7}; test<integer> list = new test<integer>(numbers); system.out.print("inorder (sorted): "); list.inorder(); system.out.print("\npostorder: "); list.postorder(); system.out.print("\npreorder: "); list.preorder(); system.out.print("\nthe number of nodes " + list.getsize()); system.out.print("\nis 1 in tree? " + list.search(1)); system.out.print("\na path root 5 is: "); java.util.arraylist<test.treenode<integer>> path = list.path(5); (int = 0; path != null && < path.size(); i++) system.out.print(path.get(i).element + " "); treenode<integer> node = new treenode<integer>(5); system.out.print("\nthe parent of " + 5 + ": " + list.getparent(node)); } }
your problem while generic parameter of treenode comparable, class not.
change this:
public static class treenode<e extends comparable<e>> { to this:
public static class treenode<e extends comparable<e>> implements comparable<treenode<e>> { or if don't require generic type comparable:
public static class treenode<e> implements comparable<treenode<e>> { once make change, won't need cast.
Comments
Post a Comment