Link to home
Start Free TrialLog in
Avatar of ratatat
ratatat

asked on

Building a general tree

I need to build a general tree using a line of input such as duddudud. D = down, u = up. For example, the previous input would create the following tree...

          1
         -
        2
     -  -  -
  3   4    5

I understand I would want to use a struct such as this:

struct node
{
     node * leftChild;
     node * sibling;
};

But that is where I'm left in the dust... Not sure where to go from there. It needs to be done recursively, how can this be achieved?
Avatar of Blackninja2007
Blackninja2007

I think this might help when building a tree diagram shows C# code but sure you wouldn't find it difficult to convert to C++

http://www.dofactory.com/Patterns/PatternComposite.aspx


Derek
Avatar of ratatat

ASKER

Unfortunately, I don't think that helps me much :(
>>>> duddudud. D = down, u = up.

??? And how you would traverse to the right?

void node::traverse(int lev)
{
     // put here your output

     if (leftChild != NULL)  leftChild->traverse(lev+1);
     if (sibling != NULL) sibling->traverse(lev);
}

when calling the above with a root node it would traverse all nodes.

Remarks:
1. normally a node has a data member, e. g. a number or name which could be outputted.

2. The tree you posted is wrong, i. e. it doesn't fit to the node struct cause any node (not only the first one of each level) may have (own) child nodes and siblings.

3. a line of input such as duddudud doesn't make so much sense as the nodes would need to fit to these commands. Actually "duddudud" (maybe with some r's) would be an alternative description of a tree (with no data). So you may *create* a tree from a input line but not take it as a output command for an already existing tree.
Avatar of ratatat

ASKER

1. I don't need any data in the nodes, just for the nodes to be created.

2. Ah, yes I apologize the initial input is incorrect in correlation with the tree. The input for the tree I gave would be ddudud. Don't know what I was thinking when I made that earlier.

3. All I need to do is create the tree

>>>> would be ddudud

That seems still wrong for me.

When translating the ddudud to

1->2    2->3   3->2   2->4   4->2   2->5

Then, then the 3->2 could be made by using recursion but for the 2->4 we would have to make 2->3 and 3->4. Same applies for 2->5.

So, the above better would be  ddrrr  (r = right) and would give a tree like

    1
    |
    2
    |
    3 -> 4 -> 5

where node 1 and 2 have only the leftChild set and node 3 has a sibling 4 and node 4 has a sibling 5.
     
     
Avatar of ratatat

ASKER

I would like it to work like this.

I get a D, so I create a child for the root node to the left, I another d, so I create a child node for that child, then I get a u, so I go up to the parent of the previous node I created, get another d, so I create a sibling to the first child, a u, back up to the parent, another d, another sibling to the first child I created.

I'm just getting lost in the implementation. How do I keep track of where I am in the tree?
ASKER CERTIFIED SOLUTION
Avatar of itsmeandnobodyelse
itsmeandnobodyelse
Flag of Germany image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>>>> if (*seq = '\0') return seq;

should be

  if (*seq == '\0') return seq;
Avatar of ratatat

ASKER

How would an up work given this implementation?
>>>> How would an up work given this implementation?
It simply works by eating one character and returning from recursive call called by the parent node.  

      if (*seq != 'd') return seq+1;