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?
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?
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.
??? 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.
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
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.
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.
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?
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>>>> if (*seq = '\0') return seq;
should be
if (*seq == '\0') return seq;
should be
if (*seq == '\0') return seq;
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;
It simply works by eating one character and returning from recursive call called by the parent node.
if (*seq != 'd') return seq+1;
http://www.dofactory.com/Patterns/PatternComposite.aspx
Derek