Solved

Building a general tree

Posted on 2008-10-22
11
1,329 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
  • 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
 

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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 

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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.

708 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

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now