Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 283
  • Last Modified:

Printing a tree

Hi All,

I need to do the following

I have a tree with the following structure

STree
{
    STree* pchildTree;
    STree* pNextTree;
    const char* pszNodePath;
}

I need to print the whole tree (full path of each node) without using dynamic allocation.
I need an elegant solution.

Thanks

BT.
0
bachra04
Asked:
bachra04
  • 6
  • 4
  • 3
1 Solution
 
Infinity08Commented:
Just use a recursive function to go over every node in the tree, starting with the root node. Combination of pseudo code and real code :

void print_tree(Stree* tree) {
  // print this node
  print_tree(tree->pChildTree);
  print_tree(tree->pNextTree);
}

If pszNodePath already contains the path, then you can just use that - if not, you'll have to keep the path uptill now in the recursive function, and add to it (passing it to the next recursion step).

btw, what do you mean by "no dynamic allocation" ? Where would you need it (maybe for storing the path ?) and why don't you want to use it ?

Final remark : a recursive solution is only good for limited depth trees - otherwise you'll fast run out of stack space !!
0
 
bachra04Author Commented:
Just a little remark
here
STree
{
    STree* pchildTree;
    STree* pNextTree;
    const char* pszNodePath;
}

here pszNodePath does not contain the full path, it contains only the node name
so I need to concatenate to get the full path.
0
 
jkrCommented:
Then include that in the recursiion, e.g.

void print_tree(Stree* tree, string path) {
  // print this node

  string full_path = path + tree->pszNodePath;

  cout << full_path << endl;

  print_tree(tree->pChildTree, full_path);
  print_tree(tree->pNextTree, full_path);
}

If you add a recursion counter, you could even manage indentation.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
bachra04Author Commented:
Hi JKr,

the following code

 string full_path = path + tree->pszNodePath;

does not compile

0
 
jkrCommented:
What errors do you get? Be sure to add

#include <string>
using namespace std;
0
 
bachra04Author Commented:
I have #include <string.h> included and I cannot control that (It is a must to use these includes),
0
 
jkrCommented:
'string.h' and 'string' are two different things - just add the above.
0
 
bachra04Author Commented:
I cannot do that, This is a MUST to use only the already included headers files.
0
 
Infinity08Commented:
>> I cannot do that, This is a MUST to use only the already included headers files.
I thought that this was homework ... maybe jkr gave away too much ... re-read my post, and try to find a way to do the same a different way ... If you don't find anything, we'll be glad to help you further - just post the code you have uptill then ...
0
 
jkrCommented:
'Adding' does not mean that you aren't using the already included header files. You're still using them. Plus one more.
0
 
bachra04Author Commented:
Note that I develop embdded software where code size is very important
Including the string library will increase the code size.
This a high level decision and for me as developer I cannot control that
I must do that using teh functions availabes in string.h
I should use strcat function but this can be the source of the memory allocation
problem. I need to do it in a clean way.
0
 
Infinity08Commented:
If it's a problem of memory, then an option could be to keep an array of pointers to the pszNodePath strings in the nodes for the current path. and iterate over that array to print the current path. ie. :

void print_tree(Stree* tree, char **path) {
  // add a pointer to tree->pszNodePath to the end of the path array
  for (int i = 0; i < size_of_path; i++) {
    //print path[i]
  }
  print_tree(tree->pChildTree, path);
  print_tree(tree->pNextTree, path);
}

of course, foresee sufficient memory for the path array, a way to specify the current length of the path array, and of course sentinels in case the end of a branch is met.
0
 
bachra04Author Commented:
Thank you JKr and Infinity for your swift reactions.
I already found a solution that is not bad.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 6
  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now