How to keep track of nodes in a tree?

[ryuzog]

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.

[JosAH]

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)

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

[ryuzog]

Thank you, very helpful.

I have something like this:

 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.