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

bachra04
bachra04 asked
on
Medium Priority
300 Views
Last Modified: 2010-04-01
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

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

Author

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

Author

Commented:
Hi JKr,

the following code

 string full_path = path + tree->pszNodePath;

does not compile

jkr
CERTIFIED EXPERT
Top Expert 2012

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

#include <string>
using namespace std;

Author

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

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

Author

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

Author

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.

Ask the Experts

Author

Commented:
Thank you JKr and Infinity for your swift reactions.
I already found a solution that is not bad.
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

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

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.