java - How do I remove a node in a BST without duplicating nodes? -
my code below. i'm having trouble deletion method, can not delete node in binary search tree , replace without creating 2 of replacement nodes... how can fix this?
public class bstmain { public static void deletevalue(int num, bstnode root){ bstnode cursor = root; while(true){ //move cursor while(cursor.getleft()!=null && num<cursor.getdata()){ //move cursor cursor = cursor.getleft(); } while(cursor.getright()!=null && num>cursor.getdata()){ //move cursor cursor = cursor.getright(); } if(cursor.getdata() == num || (cursor.getleft()==null && num<cursor.getdata()) || (cursor.getright()==null && num>cursor.getdata())) //check placing cases break; //time delete node in tree } if(cursor.getdata()==num){//delete node if(cursor.getleft()!=null){ //if left exists bstnode cursor2 = cursor.getleft(); while(cursor2.getright()!=null){ //get rightmost of left replace cursor2 = cursor2.getright(); } cursor.setdata(cursor2.getdata()); //replace cursor if(cursor2.getleft()!=null) cursor2.getleft().root = cursor2.root; //replace cursor2 cursor2.root.setright(cursor2.getleft()); } else if(cursor.getright()!=null){ //if no left right bstnode cursor2 = cursor.getright(); while(cursor2.getleft()!=null){ //get leftmost of right cursor2 = cursor2.getleft(); } cursor.setdata(cursor2.getdata()); //replace cursor if(cursor2.getright()!=null) cursor2.getright().root = cursor2.root; //replace cursor2 cursor2.root.setleft(cursor2.getright()); } else { system.out.println("node " + num + " not exist!"); } } else system.out.println(num + " not exist in binary search tree!"); } }
some output:
in order: 19 20 21 22 23 23 45
command: d 19
after deletion: 20 20 21 22 23 23 45
command: d 20
after deletion: 20 20 21 22 23 23 45
command: d 21
after deletion: 20 20 22 23 23 45
command: d 22
after deletion: 20 20 20 20 23 23 45
command: d 23
after deletion: 20 20 20 20 23 23 20 20 20 20 45
command: d 45
after deletion: 20 20 20 23 23 20 20 20 20
command: d 20
after deletion: 20 20 20 23 23 20 20 20
command: d 20
after deletion: 20 20 20 23 23 20 20
command: d 20
after deletion: 20 20 20 23 23 20
command: d 20
after deletion: 20 20 20 23 23 23 20 20 20 23
command: d 23
after deletion: 20 20 20 23 23 23 20 20 20 23
command: e
Comments
Post a Comment