Results 1 to 3 of 3
  1. #1
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default How to keep track of nodes in a tree?

    I'm having trouble keeping track of nodes in a tree. I can insert them fine, but when I need to access, modify, or remove a node, I can't figure out to reference the node. Aside from creating a "new Node" for every single Node....

    For example, if I have a tree with some root, and attach 5 nodes with elements H, A, P, P, Y one after the other so that Y is a child of P, P is a child of P, P is a child of A, etc...

    I'd like to attach H,E,L,L starting from H but I don't know how to reference it. Currently I just have two separate H nodes.

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,573
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by ryuzog View Post
    I'm having trouble keeping track of nodes in a tree. I can insert them fine, but when I need to access, modify, or remove a node, I can't figure out to reference the node. Aside from creating a "new Node" for every single Node....

    For example, if I have a tree with some root, and attach 5 nodes with elements H, A, P, P, Y one after the other so that Y is a child of P, P is a child of P, P is a child of A, etc...

    I'd like to attach H,E,L,L starting from H but I don't know how to reference it. Currently I just have two separate H nodes.
    Are the nodes ordered? i.e. for a node N, a left child L and a right child R, L < N <= R? If so a simple recursive search can find a node where you have to attach another (new) node: (this implementation assumes that at least one root node is present)

    Java Code:
    public void insert(Node n, Node child) {
       if (n.data > child.data)
          if (n.left == null)
             n.left= child;
          else
             insert(n.left, child);
       else
          if (n.right == null)
             n.right= child;
          else
             insert(n.right, child);
    }
    Deleting a node is a bit more complicated but Google is your friend.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default

    Thank you, very helpful.

    I have something like this:
    Java Code:
     Position<Keystroke> currentPos = tree.root();
            Iterator<Position<Keystroke>> childrenList;
            childrenList = tree.children(currentPos);
    
                for(int i=0; i<keys.length; i++){
                    while(childrenList.hasNext()){
                         Position<Keystroke> potentialPos = childrenList.next();
                         if(potentialPos.element().key == keys[i]){
                             currentPos = potentialPos;
                             childrenList = tree.children(currentPos);
                             break;//not needed, but prevents needless searching
                         }
                    }
                }
                System.out.println("found it: " + currentPos.element().words.first().element());
    It's not a binary tree nor is it ordered, and this is actually the first time I've tried to use an iterator. It "sorta" works but it doesn't seem really elegant. What I believe happens is that I use the iterator to create a list of children, then I step through the children, making current position THAT child if something matches and changing the "child list" the the children of said child.

Similar Threads

  1. Replies: 2
    Last Post: 11-09-2010, 01:34 PM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. Adding/removing nodes to tree under TreeViewer
    By Rodrigo Braz in forum SWT / JFace
    Replies: 0
    Last Post: 04-20-2009, 01:02 AM
  4. Track download
    By nilesh.malode in forum Advanced Java
    Replies: 1
    Last Post: 07-13-2007, 09:44 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
  •