# Binary Tree Data Structure

Printable View

• 06-03-2012, 04:01 PM
amportugal
Binary Tree Data Structure
I'm doing the Binary Tree Data Structure module, but there seems to be some trouble because it's not working with the method "set" and i doubt the "delete" method is correct.

Please I need some urgent help. Here's the code:

Code:

```public class AssociativeArray<T>{  public class Node<T>{  String key;  T value;  Node<T> left;  Node<T> right;  }  Node root;  int size;  public AssociativeArray(int n){   root=null;   size=0;  }  public void set(String key, T value){   Node n=new Node();   n.key=key;   n.value=value;   if(root==null) root=n;   else setNode(n, root);   size++;  }  private void setNode(Node n, Node r){   if(n.key.compareTo(r.key)<0){   if(r.left!=null)     setNode(n ,r.left);   else     r.left=n;   }   else   if(r.right!=null)     setNode(n,r.right);    }  public T get(String key){   return getNode(key, root).value;  }  private Node<T> getNode(String key, Node r){   if(r==null) return null;   if(r.key.equals(key))   return r;   else if(key.compareTo(r.key)<0) return getNode(key, r.right);   else return getNode(key, r.left);  }  public boolean exists(String k){   try{   getNode(k, root);   }catch(AssertionError e){   return false;   }   return true;  }  public void delete(String key){         deleteNode(key, root, null);   size--;  }  private void deleteNode(String key, Node r, Node p){   if(r.key.compareTo(key)==0){   if(r.left==null && r.right==null){     if(p.left==r)     p.left=null;     if(p.right==r)     p.right=null;   }   else if(r.left==null)     r=r.right;   else if (r.right==null)     r=r.left;   else{     Node min=searchMinimum(r.right);     deleteNode(key, min.right, min);     min.left=r.left;     min.right=r.right;     r=min;   }   }   else if(r.key.compareTo(key)<0) deleteNode(key, r.right, r);   else if(r.key.compareTo(key)>0) deleteNode(key, r.left, r);         }  private Node searchMinimum(Node e){   while(e.left!=null)   e=e.left;   return e;  }  public String[] keysToArray(){   String[] keys=new String[size];   keystoArrayInOrder(root, keys, 0);   return keys;  }  private int keystoArrayInOrder(Node<T> n, String[] keys, int i){   int next=i;   if(n!=null)   {   keys[next]=n.key;   if(n.left!=null)   next=keystoArrayInOrder(n.left, keys, next+1);   if(n.right!=null)   next=keystoArrayInOrder(n.right, keys, next+1);   }   return next;  }  public void clear(){   root=null;   size=0;  }  public int size(){   return size;  }  public boolean isEmpty(){   return size==0;  } }```
• 06-03-2012, 04:15 PM
JosAH
Re: Binary Tree Data Structure
Your setNode( ... ) method also isn't correct: it works out all possibilities if the new data is less than the data item in the current node, but it goofs for the opposite situation.

kind regards,

Jos
• 06-03-2012, 04:20 PM
amportugal
Re: Binary Tree Data Structure
Done, thanks a lot.

What about the delete method?
I'm pretty sure it's wrong and I'm having lots of difficulty of implementing that type of delete algorithm.
• 06-03-2012, 04:36 PM
JosAH
Re: Binary Tree Data Structure
System.out.println( ... ) is your friend here; put it everywhere where you suspect your implementation to be wrong; it's a perfect poor man's debugger.

kind regards,

Jos
• 06-03-2012, 04:42 PM
amportugal
Re: Binary Tree Data Structure
Can someone aid on the code of the delete method?
• 06-03-2012, 05:01 PM
JosAH
Re: Binary Tree Data Structure
Quote:

Originally Posted by amportugal
Can someone aid on the code of the delete method?

Aid on what? Write down in words (not code) what your code has to do; suppose the node to be deleted is a leaf node; what to do? Suppose the node isn't a leaf node (so it has either a left or right sub tree); what to do?

kind regards,

Jos
• 06-03-2012, 05:18 PM
amportugal
Re: Binary Tree Data Structure
Ok then:
If it's a leaf: simply eliminates it and the parent points to null where the refered leaf was;
If it's a Node with one subtree: eliminates it and its Parent is connected to its "son";
If it's a Node with two subtrees: eliminates it and substitute it with the Node with the minimum key (the "left'est") on its right subtree.
• 06-03-2012, 05:32 PM
JosAH
Re: Binary Tree Data Structure
That's it; only the third point needs a bit of coding; the other two are just a few if-statements to figure out what to do exactly.

kind regards,

Jos
• 06-03-2012, 05:35 PM
amportugal
Re: Binary Tree Data Structure
That's exactly what I'm feeling difficulties on, doing the third point...
• 06-03-2012, 06:02 PM
JosAH
Re: Binary Tree Data Structure
Quote:

Originally Posted by amportugal
That's exactly what I'm feeling difficulties on, doing the third point...

That's the point where you have to find the leftmost element in the right sub-tree. It would be something like this:

Code:

```Node findLeftMost(Node r) {   if (r.left == null) return r; // found it   return findLeftMost(r.left); // it must be there }```
You can do it iteratively as well:

Code:

```Node findLeftMost(Node r) {   while (r.left != null) r= r.left; // move left as far as possible   return r; // found it }```
kind regards,

Jos
• 06-03-2012, 06:13 PM
amportugal
Re: Binary Tree Data Structure
I've done that already, but thanks anyway :D
• 06-03-2012, 06:31 PM
JosAH
Re: Binary Tree Data Structure
Quote:

Originally Posted by amportugal
I've done that already, but thanks anyway :D

So there are no problems left anymore?

kind regards,

Jos