Results 1 to 2 of 2
  1. #1
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Default 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.

    Recursion and uniquie Tree-tritreeresults.png

    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
    Java 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);
        }
      }
    Java 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;
      }
    }
    Java 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);
          }
        }
      }
    }
    Attached Files Attached Files

  2. #2
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Default Re: Recursion and uniquie Tree

    Got it. had to move the recursion to get it to work but it is working now.

Similar Threads

  1. Replies: 4
    Last Post: 01-06-2013, 01:52 AM
  2. Replies: 4
    Last Post: 01-06-2013, 01:52 AM
  3. Recursion inside while loop for constructing tree
    By tejaswibm in forum New To Java
    Replies: 0
    Last Post: 07-03-2012, 09:10 AM
  4. Recursion to check the "rightness" of a search tree.
    By kyameron in forum New To Java
    Replies: 0
    Last Post: 12-11-2011, 11:58 PM
  5. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •