creation of simple tree like structure using stl vector c++, need help : )

[vlnikolic]

i would like to create a tree like structure in c++. since the number of children per node is arbitrary i would like to use stl vector for tree creation.

tree should look something like this:

https://i.postimg.cc/8zzT6jvJ/Diagram1.png

also

each node should contain some data, including one stl vector.

at the end i would like to be able to "merge" hierarchically in one large vector - something like this:

K-vector + I-vector + F-vector + B-vector + A-vector

thank you very much for your interest

[keskiverto]

What is the problem then?

Basically:

struct Node {
  T data;
  std::vector<Node*> children;
};

(Although you might consider smart, rather than plain pointers.)


With the "merge" you seem to talk about specific branch rather than "serializing" the entire tree?

[vlnikolic]

thank you for your reply keskiverto,

i think that your spell can do the job, i'll try it as soon as i get to the computer.

please explain to me this comment

> Although you might consider smart, rather than plain pointers. <

by merge i mean to combine values of the one line of branches, like on this picture:

https://i.postimg.cc/6QWrVCKX/Untitled.png

is there maybe a chance that you write down a minimalistic program - just to demonstrate how this actually works

[jonnin]

You don't have to use pointers at all :)
you can use a container, like a vector for the memory management, so that when you push_back a new node you can use the vector's integer index where you would have used a pointer.

I think this has likely been done. I don't like trees, but depending on how hard core and STL like you want this, it may be best to use an existing than recook it. If its for learning or playing, DIY ok.

[seeplus]

[Also asked here https://forums.codeguru.com/showthread.php?565908 ]

[vlnikolic]

hello everybody

thank you for your replies.

jonnin, super idea -thanks

[keskiverto]

2kaud did ask on that other forum:

the more important question is when inserting data into the tree, what is the criteria for creating a new node - or to traverse existing nodes for insertion?

A binary tree can easily have left < root < right. With multiple children the order is in no way obvious.

That comes back when you search a value from the tree. Binary search can efficiently check ordered container (e.g. a binary tree). The search(T,X) answers question: "Does tree T contain node with value X?"

A search can keep track of values that it has encountered. For example, a depth-first left-to-right search for K's value would collect:

A
AB
ABE
ABF
ABFI
ABFIJ
ABFIK

At this point K was found and collected data should be returned.
If you seek value that is not in your tree, then you will visit every node and will return empty set.

[jonnin]

N children tree may not always be a search tool, it can be organizational, like a family tree or the business's emergency call list or whatever weird hierarchy.

I think you can cook up a search tree for an N tree, but you need a fixed N to do that. Otherwise, you just have 1 level where root has a million children. If you have a fixed N, when you reach N you can sort the children of the node and the next one goes to the first child it is less than or off the last one if greater than all, or something like that. then each node becomes its own binary search for which limb to take. Seems messy, but some scheme along those lines (if not exactly this one) should be doable? It may be doable for a variable N as well, but you need a rule for when to go across vs down.

[seeplus]

When we did this at Univ in the dim and distant past, we had the example of storing words. Each node contained one letter and the branch(s) were to the next letter in the word. So each node had a max of 26 branches and the rules for insertion etc were known. This was all done using memory and pointers. Using a fixed array for the node branches wasn't allowed...