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.
LVL 2
bachra04Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
bachra04Author Commented:
Thank you JKr and Infinity for your swift reactions.
I already found a solution that is not bad.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.