Recursion and uniquie Tree

• 05-07-2013, 02:07 PM
Recursion and uniquie Tree
Greetings all,
So I have a project I am working on and the instructions are to create something like a 2-3 Tree but it does not have to be balanced as a matter of fact it probably won't be balanced.
So I have put my current code below and attached the project zipped file and what I am asking my question about is recursively inserting a node. So each node can have 1 or 2 data items in it. dataItem 2 can only be present if there is a dataItem 1

Right now I am only working on adding the low nodes because if I can figure out the recursion for the low nodes, then adding the mid nodes and high nodes will be similar.

When I run my code now, I get the root node and then I get the low node, but when I go to try to add another low node to the low node it just overwrites the current low node.

Attachment 4950

I think it has to do with how I am recuring? I will say that I have been working on this all night and totally stumped as to how to get the recursion to work. I am only asking for someone to look at this and tell give suggestions or examples of how to make this work. when I run this in debug mode in netbeans, I see that when I go to add 9, it overwrites 12 which should be the new parent node to the new node. Please help, it would be much appreciated.

Wally
Code:

```package tri.tree; public class TrTreeApp {   public static void main(String[] args)   {     TriLinkTree tree = new TriLinkTree();         tree.insert(65);         tree.insert(22);                    tree.insert(18);         tree.insert(12);         tree.insert(9);         tree.insert(6);     }   }```
Code:

```package tri.tree; public class TriLinkNode {   public int lowKey;   public int hiKey;   public TriLinkNode parent;   public TriLinkNode low;   public TriLinkNode mid;   public TriLinkNode high;   public int keyCount=0;       public TriLinkNode()   {       lowKey = 0;       parent = null;       low = null;       mid = null;       high = null;   }   public int getLowKey()   {     return lowKey;   }   public void setLowKey(int lowKey)   {     this.lowKey = lowKey;   }   public int getHiKey()   {     return hiKey;   }   public void setHiKey(int hiKey)   {     this.hiKey = hiKey;   }   public TriLinkNode getParent()   {     return parent;   }   public void setParent(TriLinkNode parent)   {     this.parent = parent;   }   public TriLinkNode getLow()   {     return low;   }   public void setLow(TriLinkNode low)   {     this.low = low;   }   public TriLinkNode getMid()   {     return mid;   }   public void setMid(TriLinkNode mid)   {     this.mid = mid;   }   public TriLinkNode getHigh()   {     return high;   }   public void setHigh(TriLinkNode high)   {     this.high = high;   }   public int getKeyCount()   {     return keyCount;   }   public void setKeyCount(int keyCount)   {     this.keyCount = keyCount;   } }```
Code:

```package tri.tree; public class TriLinkTree {   public TriLinkNode root;   public TriLinkTree()   {     root = null;   }   public void insert(int value)   {     if (root == null)     {       root = new TriLinkNode();       root.lowKey = value;     }     if (root.hiKey == 0)     {       if (root.lowKey > value)       {         root.hiKey = root.lowKey;         root.lowKey = value;       }             if (root.lowKey < value)       {         root.hiKey = value;       }     } else     {       recInsert(root, value);     }   }   private void recInsert(TriLinkNode myNode, int value)   {     if (myNode.lowKey > value)     {       TriLinkNode tempNode = new TriLinkNode();        if (myNode.low == null)       {       tempNode.parent = myNode;       tempNode.lowKey = value;       myNode.low = tempNode;       myNode = tempNode;       }       else if (myNode.low.lowKey > value)       {         myNode.low.hiKey = myNode.low.lowKey;         myNode.low.lowKey = value;       } else if (myNode.low.lowKey < value)       {         myNode.low.hiKey = value;       } else       {         recInsert(myNode.low, value);       }     } else if (myNode.lowKey < value && myNode.hiKey > value)     {       if (myNode.mid == null)       {         myNode.mid = new TriLinkNode();         myNode.mid.parent = myNode;       } else if (myNode.lowKey > value)       {         myNode.hiKey = myNode.lowKey;         myNode.lowKey = value;       } else       {         recInsert(myNode.mid, value);       }     } else     {       if (myNode.high == null)       {         myNode.high = new TriLinkNode();         myNode.high.parent = myNode;       } else if (myNode.lowKey > value)       {         myNode.hiKey = myNode.lowKey;         myNode.lowKey = value;       } else       {         recInsert(myNode.high, value);       }     }   } }```
• 05-08-2013, 05:04 AM