Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Building a general tree

Posted on 2008-10-22
Medium Priority
1,370 Views
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?
0
Question by:ratatat
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 5
• 4

LVL 3

Expert Comment

ID: 22775392
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 Comment

ID: 22775735
Unfortunately, I don't think that helps me much :(
0

LVL 39

Expert Comment

ID: 22775745
>>>> 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 Comment

ID: 22775914
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

LVL 39

Expert Comment

ID: 22778497
>>>> 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 Comment

ID: 22778611
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

LVL 39

Accepted Solution

itsmeandnobodyelse earned 2000 total points
ID: 22779108
>>>> 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

LVL 39

Expert Comment

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

should be

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

Author Comment

ID: 22785235
How would an up work given this implementation?
0

LVL 39

Expert Comment

ID: 22794173
>>>> 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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on thâ€¦
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
###### Suggested Courses
Course of the Month7 days, 15 hours left to enroll