Solved

Building a general tree

Posted on 2008-10-22
11
1,356 Views
Last Modified: 2012-05-05
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
Comment
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
  • Learn & ask questions
  • 5
  • 4
11 Comments
 
LVL 3

Expert Comment

by:Blackninja2007
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

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

Expert Comment

by:itsmeandnobodyelse
ID: 22775745
>>>> 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.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:ratatat
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

by:itsmeandnobodyelse
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

by:ratatat
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

by:
itsmeandnobodyelse earned 500 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

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

should be

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

Author Comment

by:ratatat
ID: 22785235
How would an up work given this implementation?
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
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

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

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

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
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.

729 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question