# 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?
###### Who is Participating?

Commented:
>>>> another sibling to the first child I created.
As you only stored the pointer for the first sibling you would need to iterate thru all siblings for that functionality. A "r" would be much more convenient.

>>>> How do I keep track of where I am in the tree?
You don't need to beside of the root node.

You have one function - say buildtree - similar to the traverse function I posted. If you make it a member function of struct node, you would not need to pass pointers. Otherwise you pass the next node pointer as first argument. You would create the root node, call buildtree with that node and pass the command sequence "ddudud" as argument. The buildtree would extract the first char of the sequence. In case of 'd' it would create a new node and if leftChild is NULL, set leftChild of the current node to that new node pointer. If leftChild isn't NULL you would need to iterate beginning from leftChild->sibling until sibling is NULL (that is the crucial by not having a 'r' command). Then the new node must be chained to the last sibling node not NULL. Then call buildtree for that new node passing a sequence where the first char was erased (you could pass pointer+1 in case the command sequence is a const char* string). After buildtree of the new child node returned, you call buildtree again for the current node. You pass the string which was returned by the buildtree of the new node (each call of buildtree would 'eat' at least one of the command characters). Finally you only pass the pointer to the zero char which terminates the command string.

To prevent recursion from infinite loop your function would need to look like

const char* node::buildtree(const char* seq)
{
if (*seq = '\0') return seq;
if (*seq != 'd') return seq+1;
// here implement the 'd' case as I pointed out textually

node* rightChild = new node;
rightChild->sibling =  rightChild->leftChild = NULL;

....

// finally call the buildtree for the new child node
char* nseq = rightChild->buildtree(seq+1);
// and call the buildtree for the current node with rest of sequence
return buildtree(nseq);
}

0

Commented:
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
0

Author Commented:
Unfortunately, I don't think that helps me much :(
0

Commented:
>>>> duddudud. D = down, u = up.

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

void node::traverse(int lev)
{

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

Author Commented:
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

0

Commented:
>>>> 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.

0

Author Commented:
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?
0

Commented:
>>>> if (*seq = '\0') return seq;

should be

if (*seq == '\0') return seq;
0

Author Commented:
How would an up work given this implementation?
0

Commented:
>>>> 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;

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.