Tuesday, 15 March 2011

java - Need help on deleting a binary search tree node -


This is a grade 12 assignment. One of the questions asks us to write a method in the BTRE class which takes a BNDD or integer, and removes the node from the tree.

Here's what I have tried:

  Public zero deletion (betode B) {if (b == null) {return; } If (B.Left () () == Null & amp; B.Brite () == Faucet) {B = Null; } Else {//System.out.println("boiboi "); BNode tmp = b; B = Null; Add (tmp.getLeft ()); Add (tmp.getRight ()); Tmp = null; }} Public Zero Deletion (Int v) {//System.out.println("gord "); Delete (think (v)); }   

Find here and find the method that I think is right:

  Public BNode (int v) {return find (v, root); } Public BNode Search (int v, BNode branch) {if (branch == null} branch.getVal () == v) {Return Branch; } If (v & lt; branch.getVal ()) {return search (v, branch.getLeft ()); } Else {// else if (v> branch.getVal ()) return search (v, branch.getRight ()); }} Add Public Zero (Int V) {if (root == null) {root = new BNode (v); } And {add (v, root); }} Add Public Zero (Int v, Beanode branch) {if (v == branch.getVal ()) {return; } If (v & lt; branch.getVal ()) {if (branch.getLeft () == faucet) {branch.setLeft (new BNode (v)); } Else {add (v, branch.getLeft ()); }} Else {if (branch.getRight () == faucet) {branch.setRight (new BNode (v)); } Else {add (v, branch.getRight ()); }}} Add Public Zero (Bnode N) {if (n == null) {return; } Add (n.getVal ()); }   

Here is my test class:

  BTree bTree = new BTree (); BTree.add (50); BTree.add (60); BTree.add (40); BTree.add (35); BTree.add (55); BTree.add (45); BTree.add (51); BTree.delete (60); BTree.display ();   

The output is still everything I have added: 35 40 45 50 51 55 60 Even if I tried to remove 51 which is the easiest case, still Any help or suggestions of the same output will be appreciated, thanks.

In three cases you should take care

  1. If this is a leaf, then go ahead and delete.

  2. If a node is just 1 child, just connect your child to your parents [you will need some helpful methods to get it clearly]

  3. If a node has 2 children, then find the smallest element in the right subtree. And place its node in the current node and delete that node.

    More info here.

No comments:

Post a Comment