Results 1 to 12 of 12
Thread: Binary Tree Data Structure
 06032012, 04:01 PM #1Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
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:
Java 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; } }
 06032012, 04:15 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
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,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 06032012, 04:20 PM #3Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
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.
 06032012, 04:36 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
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,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 06032012, 04:42 PM #5Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
Re: Binary Tree Data Structure
Can someone aid on the code of the delete method?
 06032012, 05:01 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
Re: Binary Tree Data Structure
I have the stamina of a seal; I lie on the beach instead of running on it.
 06032012, 05:18 PM #7Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
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.
 06032012, 05:32 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
Re: Binary Tree Data Structure
That's it; only the third point needs a bit of coding; the other two are just a few ifstatements to figure out what to do exactly.
kind regards,
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 06032012, 05:35 PM #9Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
Re: Binary Tree Data Structure
That's exactly what I'm feeling difficulties on, doing the third point...
 06032012, 06:02 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
Re: Binary Tree Data Structure
That's the point where you have to find the leftmost element in the right subtree. It would be something like this:
Java Code:Node findLeftMost(Node r) { if (r.left == null) return r; // found it return findLeftMost(r.left); // it must be there }
Java Code:Node findLeftMost(Node r) { while (r.left != null) r= r.left; // move left as far as possible return r; // found it }
JosI have the stamina of a seal; I lie on the beach instead of running on it.
 06032012, 06:13 PM #11Member
 Join Date
 Mar 2012
 Posts
 13
 Rep Power
 0
Re: Binary Tree Data Structure
I've done that already, but thanks anyway :D
 06032012, 06:31 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,038
 Blog Entries
 7
 Rep Power
 23
Similar Threads

Binary Tree Help  Find the largest subtree
By joshhazel in forum New To JavaReplies: 2Last Post: 01302012, 03:08 AM 
Linked list with multiple links to implement Tree data structure
By kavithavr in forum Advanced JavaReplies: 8Last Post: 10172011, 09:17 AM 
Tree data structure
By Nacao in forum New To JavaReplies: 18Last Post: 08232011, 06:26 PM 
Tree Structure
By chiku in forum New To JavaReplies: 2Last Post: 01272011, 09:31 PM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM
Bookmarks