CODEWITHSUNDEEP
c++algorithm
jasonkim
jasonkim

Reputation: 706

I am totally stuck when dealing with N-ary Trees traversal

Here is the thing.I wanna traverse any arbitrary two nodes in my N-ary Tree(Family tree in this case).Below is my simplified code for the case that traverses from root to an arbitrary node:

#include <iostream>
#include <string>
using namespace std;

const int max=100;

//structure definition
//every children has only one parent
struct Tree {
   string name;
   int numChildren;
   Tree *children[max];
   ~Tree(){delete [] children;}
}; 

//Label the nodes that are supposed to be in the path
//Suppose the names of those nodes do not contain whitespaces,just trivial names
int *travel_point(Tree *tree,string s){
    Tree *node = new Tree;
    Tree *temp = new Tree;
    node = tree;

    int a[100],i=0,j;
    for(j=0;j<100;j++) a[j]=-1;
    while(tree){
        if(tree->name == s){
           a[i]=0;
           break;
        }
        else{
           for(j=0;j<node->numChildren;j++){
              if(travel_point(node->children[j],s)!=NULL){
                break;      
                }
              }
           a[i]=j+1;
           i++;
           temp=node->children[j];
           node=temp;
        }
    }
    if(a[i-1]==-1) return NULL;
    else a;
}

This is roughly what I have been doing.Since every children has only one parent,then the path from root to one arbitrary node is unique as well.So I wanna set all the other paths as NULL in case that I could take advantage during recursion.

I know that recursion is not a good idea but I just wanna give a shot though.

Upvotes: 1

Views: 911

Answers (2)

Salvatore Previti
Salvatore Previti

Reputation: 9050

Ok i don't want to solve your homework but i would like to give you some advice. First of all, recursive functions with trees are usually good, usually trees don't go too deep in height, so recursive functions are good. They are simpler to write and to understand.

1) You cannot return a pointer to an array in your stack memory and pretend it will work :)

2) You need a stack class, use std::stack<int>, pass a a non-const reference to it as parameter, so you can modify it in all your functions, and return a boolean value that indicates if you found the node or not. You can then convert the stack to a vector or to an array, but as i imagine the algorithm, you need a stack data structure.

3) There is no need to pass the string by copy, pass a const reference to it. (const string& s)

4) The algorithm is wrong, rewrite it. Think more about it.

5) The destructor is wrong, it will not kill child nodes but will do an invalid deallocation, you need a loop.

6) Instead of an array of [max] subtrees i would use a std::vector<Tree*>

I imagine the function as something like ...

bool travel_point(const Tree *tree, const string& s, stack<int>& result)

And to use it...

stack<int> path;
if (travel_point(mytree, "ciao", path))
{
    // print path
}

Upvotes: 1

cdiggins
cdiggins

Reputation: 18203

This will crash and burn. You are returning a pointer to a temporary array "a". Maybe you intended to pass "a" as an argument to the function. However: what is the function supposed to return?

By the way: recursion is a good idea.

Upvotes: 0

Related Questions