Building a general tree

Posted on 2008-10-22
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...

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

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++


Author Comment

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

Expert Comment

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.

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

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

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

    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.

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?
LVL 39

Accepted Solution

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);
LVL 39

Expert Comment

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

should be

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

Author Comment

ID: 22785235
How would an up work given this implementation?
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;


Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
scoresClump  challenge 31 151
sorting efficency of sorting algorithm 30 133
learn programming 8 72
Can Live bindings change TGrid Cell Colour ? 1 35
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

726 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