Going through a node and it's children

[MrPickle]

I have a structure like so:

struct node
{
	float x, y, z;
	std::vector<node> children;
};

and I want to loop through all the node's children, then all the children's children then all the children's children's children, etc..

I know one way would be to use recursive functions, but is this the only way?

Also, what's the proper name for this structure? I think it's a tree, but then there's lots of different types of trees. I'd just like to know for future reference.

Edit: after some research I believe it to be a multi-way tree.

[unauthorized]

I have a structure like so:

struct node
{
	float x, y, z;
	std::vector<node> children;
};

and I want to loop through all the node's children, then all the children's children then all the children's children's children, etc..

I know one way would be to use recursive functions, but is this the only way?

Also, what's the proper name for this structure? I think it's a tree, but then there's lots of different types of trees. I'd just like to know for future reference.

Edit: after some research I believe it to be a multi-way tree.

Going through data structures that can fork to (theoretical) infinity is best done with recursion for a number of reasons, the simplest being we aren't in the 80s where the performance loss of a few extra function calls is a big deal. And if you are doing something where performance actually does matter, you should already know your algorithms inside out and certainly not ask here.

Seeing as you use C++ containers, my advise is to add a member function that iterates over each node by doing whatever you want it to do and then calling the same function on the child element. You only have to call this once on the root node and watch the fireworks.

[MrPickle]

Thank you. I have taken the recursion route, just out of curiosity, what other ways is there to do this?

[unauthorized]

Thank you. I have taken the recursion route, just out of curiosity, what other ways is there to do this?

I suppose you could make a loop out of it, but you would have to manually allocate from the heap and keep track on which memory belongs to which tree leaf... believe me, it gets ugly. The only reason you would want to go this route is if you keep running out of stack space due to recursion overload and increasing the stack size is not an option.

[JosAH]

I have a structure like so:

struct node
{
	float x, y, z;
	std::vector<node> children;
};

and I want to loop through all the node's children, then all the children's children then all the children's children's children, etc..

I know one way would be to use recursive functions, but is this the only way?

Also, what's the proper name for this structure? I think it's a tree, but then there's lots of different types of trees. I'd just like to know for future reference.

Edit: after some research I believe it to be a multi-way tree.

You structure doesn't have to be a tree; suppose two or more elements of vector of a node contain the same node; you have a directed graph then.

But it can very well represent a tree; there are basically two ways to traverse a tree: depth first order and breadth first order. The first (depth first) is easy to implement recursively (pseudo code):

void traverse(Node* node) {
   if (node == null) // nothing to do
      return;
   process(node->data);
   forall (node : in vector)
      traverse(node);
}

Breadth first traversal needs a queue of nodes:

void traverse(Node* node) {
   queue<Node*> list;
   list.pushfront(node);
   while (!list.isEmpty()) {
      node= list.popback();
      if (node != null) {
         process(node->data);
         list.pushall(node->vector);
   }
}

If you have a binary tree every node just has a left child and a right child; there are three major ways to depth first traverse it:

// prefix:
process(node->data);
traverse(node->left);
traverse(node->right);

// infix:
traverse(node->left);
process(node->data);
traverse(node->right);

// postfix:
traverse(node->left);
traverse(node->right);
process(node->data);

kind regards,

Jos

[unauthorized]

It's a tree, because he is using a vector of instances, rather than pointers.
It would be a graph if he had a vector<Node*>, but not with vector<Node>. Got me fooled at first too.

BTW, don't write someone's hw for him!

[Banfa]

BTW, don't write someone's hw for him!

If you check the message headers you will see that Jos is a Moderator with over 10,000 posts on this forum (where as you are a Member with 72 posts), he is also a well known and well respected member of our community.

As such he is fully conversant with the forum rules and more over has the authority and ability to enforce them.

So I guess what I am saying is "don't teach your grandmother to suck eggs".

However thank you for caring enough to want to help this forum stay with-in its own principles. All of what Jos has posted is small snippets of code (or pseudo code) that wont compile without either modification or additional code.

Banfa
Administrator

[unauthorized]

I'm well aware that JosAH is a moderator. My point was not about the board rule (which I was unaware of until now), but rather expressing my dissatisfaction with handing people code just like this.

Cheer up, I'm not criticizing him. ;) He did what he thinks was right, and I gave my opinion on the matter. I'm not the one to shy from speaking my mind out with people in power. Don't think for a second that I give a damn about that little number next to a person's name or the color of his rank. Mods are not immune to making mistakes any more than 1st posters are.

Still, I understand what you are trying to tell me, and will avoid being so blunt with Mods/Admins in the future. But only because you asked nicely.

[JosAH]

BTW, don't write someone's hw for him!

I didn't do that, I showed how depth first and breadth first traversal work by using a simple form of pseudo code; I also showed the three alternatives for depth first traversal on a binary tree. And don't yell at me.

kind regards,

Jos

[MrPickle]

It's not my homework. I'm just a hobby programmer, well, for now.

Thank you all. (: