We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

# Printing a tree

on
Medium Priority
300 Views
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.
Comment
Watch Question

## View Solution Only

CERTIFIED EXPERT
Top Expert 2009

Commented:
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 !!

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.
CERTIFIED EXPERT
Top Expert 2012

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

Commented:
Hi JKr,

the following code

string full_path = path + tree->pszNodePath;

does not compile

CERTIFIED EXPERT
Top Expert 2012

Commented:
What errors do you get? Be sure to add

#include <string>
using namespace std;

Commented:
I have #include <string.h> included and I cannot control that (It is a must to use these includes),
CERTIFIED EXPERT
Top Expert 2012

Commented:
'string.h' and 'string' are two different things - just add the above.

Commented:
I cannot do that, This is a MUST to use only the already included headers files.
CERTIFIED EXPERT
Top Expert 2009

Commented:
>> 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 ...
CERTIFIED EXPERT
Top Expert 2012

Commented:
'Adding' does not mean that you aren't using the already included header files. You're still using them. Plus one more.

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.
CERTIFIED EXPERT
Top Expert 2009
Commented:
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.

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
Thank you JKr and Infinity for your swift reactions.
##### Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile