Results 1 to 12 of 12
Thread: Binary Tree Data Structure
 06032012, 05: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, 05:15 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06032012, 05: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, 05:36 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06032012, 05: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, 06:01 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
Re: Binary Tree Data Structure
cenosillicaphobia: the fear for an empty beer glass
 06032012, 06: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, 06:32 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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,
Joscenosillicaphobia: the fear for an empty beer glass
 06032012, 06: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, 07:02 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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 }
Joscenosillicaphobia: the fear for an empty beer glass
 06032012, 07: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, 07:31 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,776
 Blog Entries
 7
 Rep Power
 21
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, 10:17 AM 
Tree data structure
By Nacao in forum New To JavaReplies: 18Last Post: 08232011, 07: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, 08:40 AM
Bookmarks