i'm having problem getheight() method, not returning correct height tree. think problem has queuelist class can not life of me solve issue. i'm open suggestions on how better implement binary search. below queuelist class.
package lab5; import java.util.nosuchelementexception; public class queuelist<e> implements queue<e> { private node<e> front; private node<e> rear; private int size = 0; public queuelist (e it){ front = rear = new node<e>(it); size++; } public queuelist(){ front = rear = new node<e>(); size=0; } public boolean isempty() { return size==0; } public void enqueue(e it) { rear.setnext(rear); rear.setelement(it); size++; } public void clear() { front=new node<e>(); rear=new node<e>(); front.setnext(null); rear.setnext(null); front.setnext(null); size=0; } public int size() { return size; } public e front() { return front.getelement(); } public e dequeue() { node<e> temp = front; if(isempty()){ throw new nosuchelementexception(); } else{ front = front.getnext(); size--; return temp.getelement(); } } } here binary search tree class, of bstnode method works correctly assume not issue.
package lab5; public class binarysearchtree<e extends comparable<e>> { private bstnode root; private int size; public binarysearchtree() { root = null; size = 0; } public binarysearchtree(bstnode node) { root = node; size = 1; } /** * searches node contains it. * * if finds it, returns node * * else returns null * * @param * - element * * @return node contains * */ public bstnode search(e it) { bstnode<e> parent = null; bstnode<e> child = null; bstnode<e> node = root; while (node != null && node.getelement() != it) { parent = node; int compareresult = it.compareto(node.getelement()); if (compareresult < 0) { node = node.getleft(); } else { node = node.getright(); } } if (node == null) { return null; } return node; } /** * determines if tree contains element * * @return true if in tree * */ public boolean contains(e it) { return (search(it) != null); } /** * add element correct location * * elements left less parent * * elements rights greater parent * * not allow duplicates * * @param * element insert * */ public void insert(e it) { bstnode<e> newnode = new bstnode<e>(it); if (root == null) { root = newnode; return; } bstnode<e> parent = null; bstnode<e> node = root; while (node != null) { parent = node; int compareresult = it.compareto(node.getelement()); if (compareresult < 0) { node = node.getleft(); } else if (compareresult > 0) { node = node.getright(); } else { // duplicate return; } } int res = it.compareto(parent.getelement()); if (res < 0) { parent.setleft(newnode); } else { parent.setright(newnode); } size++; } /** * removes node contains it. * * if tree not contain it, prints * * user , nothing else. * * otherwise removes node , maintains * * bst properties * * if removing node 2 children, replace * * in order predecessor. * * @param * element of node want remove. * */ public void remove(e it) { bstnode<e> parent = null; bstnode<e> child = null; bstnode<e> node = root; // find node contains while (node != null && node.getelement() != it) { parent = node; int compareresult = it.compareto(node.getelement()); if (compareresult < 0) { node = node.getleft(); } else { node = node.getright(); } } if (node == null) { system.out.println("failed find: " + + " removal"); return; } if (node.isleaf()) { if (parent == null) { root = null; } else if (it.compareto(parent.getelement()) < 0) { parent.setleft(null); } else { parent.setright(null); } } else if (node.getleft() == null) { child = node.getright(); swapelements(node, child); node.setleft(child.getleft()); node.setright(child.getright()); } else if (node.getright() == null) { child = node.getleft(); } else { child = node.getleft(); parent = null; while (child.getright() != null) { parent = child; child = parent.getright(); } if (parent == null) { swapelements(node, child); node.setleft(child.getleft()); } else { swapelements(node, child); parent.setright(child.getleft()); } } size--; } /** * returns height of tree * * if tree empty, height -1 * * if tree has 1 node, height 0 * * @return integer height of tree * * * */ public int getheight() { int height = -1; queuelist<bstnode> q = new queuelist<bstnode>(); if (root == null) { return height; } q.enqueue(root); while (!q.isempty()) { int nodecount = q.size(); height++; while (nodecount > 0) { bstnode<e> node = q.dequeue(); if (node.hasleft()) { q.enqueue(node.getleft()); } if (node.hasright()) { q.enqueue(node.getright()); } nodecount--; } } return height; } /** * helper method * * removal need swap elements of nodes * * @param node1 * , node2 nodes contents swapping * */ private void swapelements(bstnode node1, bstnode node2) { bstnode temp = null; temp.setelement(node1.getelement()); node1.setelement(node2.getelement()); node2.setelement(temp.getelement()); } /** * prints each level of tree on own line * * use queue class * */ public void printlevelorder() { queuelist<bstnode> q = new queuelist<bstnode>(); q.enqueue(root);//you don't need write root here, written in loop while (q.size() > 0) { bstnode n = q.dequeue(); system.out.println(n.tostring()); //only write value when dequeue if (n.hasleft()) { q.enqueue(n.getleft());//enqueue left child } if (n.hasright()) { q.enqueue(n.getright());//enque right child } } } /** * prints tree in depth-first fashion * * use stack class * */ public void printbydepth() { stacklist<bstnode> s = new stacklist<bstnode>(); s.push(root); while (s.isempty() == false) { bstnode x = s.pop(); if (x.getright() != null) s.push(x.getright()); if (x.getleft() != null) s.push(x.getright()); system.out.print(" " + x.tostring()); } } /** * prints tree in inorder fashion. * * uses stack push left children onto stack * */ public void printinorder() { if (root == null) return; stacklist s = new stacklist(); bstnode currentnode = root; while (!s.isempty() || currentnode != null) { if (currentnode != null) { s.push(currentnode); currentnode = currentnode.getleft(); } else { bstnode n = null; n.setelement(s.pop()); system.out.printf("%d ", n.tostring()); currentnode = n.getright(); } } } }
as recursion popular when dealing binary trees, can use solution:
public int getheight() { return getheight(root, 0); } private int getheight(bstnode node, int currentheight) { if (node == null) { return currentheight; } int rightheight = getheight(node.getright(), currentheight + 1) int leftheight = getheight(node.getleft(), currentheight + 1); return math.max(rightheight, leftheight); } note returns height=0 empty tree.
Comments
Post a Comment