i'm implementing binary search tree in java. however, search function doesn't seem working in remove function. doesn't find nodes inside tree, whether in tree or not. think logic correct comparing node moving left , right depending on whether node search larger or smaller, may have issues when return values. if adding node class or test of program help, can that. suggestions?
public class binarysearchtree { private boolean empty = true; private int size = 0; private node root; public binarysearchtree(node root) { this.root = root; } public node[] search(int value) { node parent = null; node currentnode = root; node[] returnlist = new node[2]; while ( currentnode != null ) { if (currentnode.getvalue() == value) { returnlist[0] = parent; returnlist[1] = currentnode; return returnlist; } else if (value < currentnode.getvalue()) { parent = currentnode; currentnode = currentnode.getleft(); } else if (value > currentnode.getvalue()) { parent = currentnode; currentnode = currentnode.getright(); } } return returnlist; } public void add(int value) { node comparingnode = root; while (true) { if (comparingnode.getvalue() == value) { system.out.println("tried add duplicate value of " + value); break; } if (comparingnode.getleft() == null && comparingnode.getright() == null) { if (value > comparingnode.getvalue()) { comparingnode.setright(new node(value)); } if (value < comparingnode.getvalue()) { comparingnode.setleft(new node(value)); } break; } else { if (value < comparingnode.getvalue()) { if (comparingnode.getleft() == null) { comparingnode.setleft(new node(value)); break; } else { comparingnode = comparingnode.getleft(); } } if (value > comparingnode.getvalue()) { if (comparingnode.getright() == null) { comparingnode.setright(new node(value)); break; } else { comparingnode = comparingnode.getright(); } } } } } public void remove(int value) { node[] nodesfound = search( value ); node parent = nodesfound[0]; node child = nodesfound[1]; boolean fleft = ( parent.getleft() == child ); // child node has no children. if (fleft) { parent.setleft(null); } else { parent.setright(null); } if( child.getleft() != null && child.getright() == null ) { // child node has left child. if( fleft ) { parent.setleft(child.getleft()); } else { parent.setright(child.getleft()); } } else if ( child.getright() != null && child.getleft() == null ) { // child node has right child. if( fleft ) { parent.setleft(child.getright()); } else { parent.setright(child.getright()); } } else { // child node has both children. if( child.getright().getleft() == null ) { child.getright().setleft( child.getleft() ); parent.setright( child.getright() ); } else { node[] returnlist = findleftmost2children(child.getright()); node leftmostparent = returnlist[0]; node leftmostchild = returnlist[1]; leftmostparent.setleft(null); leftmostchild.setleft(child.getleft()); leftmostchild.setright(child.getright()); parent.setright(leftmostchild); } } } public node getroot() { return root; } public void outputtreeinorder( node root ) { if( root == null ) return; // output left tree. if( root.getleft() != null ) outputtreeinorder( root.getleft() ); // output current node. system.out.print( root.getvalue() + " " ); // output right tree. if( root.getright() != null ) outputtreeinorder( root.getright() ); } private node[] findleftmost2children( node root ) { node parent = null; node current = root; while (current.getleft() != null) { parent = current; current = current.getleft(); } node[] returnlist = new node[2]; returnlist[0] = parent; returnlist[1] = current; return returnlist; } }
i corrected code in question. realized had set proper pointers moving node when deleting, not changing value. have move node new pointers , parent.
