#Create Tree with levels and numebr of child nodes

1 messages · Page 1 of 1 (latest)

pure atlas
#

I wnat to dynamically create a tree with a fucntion taking the number of levels and childnodes for each node as an arguemnt. i have created the path from the root node to the lowest level and there are able to add as much child nodes as needed. now i need to move up the other levels to ensure thy also have enough child ndoes.

i would really appreciate if someone would help me figure out the logic on how to do that or does knwo how to find pseudocode or explanations on how to do that on google :3 bc i all found are depthg first searches...

clear fiberBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

spring mirage
#

what is the issue? you can store a pointer to the parent node in each node, then walk up using those

pure atlas
#

the problem is i dont know how to do the algorithm logical

#

i want that but i got
1
2
3
4
5

image.png
spring mirage
#

what exactly is the input?

pure atlas
#

void Node::create_complete_tree(int nr_child_nodes, int tree_depth)

spring mirage
#

is this a binary tree?

pure atlas
spring mirage
#

so nr_child_nodes is the number of children each node has?

pure atlas
#

yes

#

node_1
node_2
node_3
node_2
node_5
node_6
node_3
node_2
node_4
node_5
node_2
node_3
node_6
node_2
node_8
node_9

thats the point im at with my c++ code ;-,

spring mirage
#

so as far as I understand you want to construct a complete n-ary tree of a certain depth

pure atlas
#

i add the parent als child of itself

pure atlas
spring mirage
#

this is very simple to do using recursion

pure atlas
#

i dont know how its called so searching for stuff didnt wokr, but thx this seems to bve easier to google

pure atlas
#

thx

# 

void Node::create_complete_tree(int nr_child_nodes, int tree_depth)
{
    // Node *parent = this;
    int currentId = 1;

    for (int i = 1; i < tree_depth; i++)
    {
        Node *levelParent = this;
        
        for (int j = 0; j < nr_child_nodes; j++)
        {
            Node *childParent = levelParent;
            Node *newNode = new Node(currentId);
            currentId += 1;

            if (newNode->get_name() != levelParent->get_name())
            {
                childParent->add_child(newNode);
                std::cout << newNode->get_name() << " in  " << childParent->get_name() << " ->" << childParent->get_nr_children() << std::endl;
            }
            childParent = newNode;

            if (tree_depth - i > 0 && nr_child_nodes - j > 0)
            {
                newNode->create_complete_tree(nr_child_nodes - j, tree_depth - i);
                continue;
            }

            levelParent = childParent;
        }
        currentId += 1;
    }
}
spring mirage
#

it's more complicated than it has to be

#

basically what you want to do:
0. if tree_depth == 0, then return

  1. create nr_child_nodes children
  2. for each child, call the function recursively with tree_depth - 1
pure atlas
#

node_2 in node_1 ->1
node_2 in node_2 ->1
node_2 in node_2 ->1
node_3 in node_2 ->2
node_3 in node_2 ->2
node_2 in node_3 ->1
node_3 in node_3 ->2
node_3 in node_1 ->2
node_2 in node_3 ->1
node_2 in node_2 ->1
node_3 in node_2 ->2
node_3 in node_3 ->2
node_2 in node_3 ->1
node_3 in node_3 ->2
node_1
node_2
node_2
node_2
node_3
node_3
node_2
node_3
node_3
node_2
node_2
node_3
node_3
node_2

# 
void Node::create_complete_tree(int nr_child_nodes, int tree_depth)
{
    if (tree_depth <= 1)
    {
        return;
    }

    int currentId = 1;

    for (int j = 0; j < nr_child_nodes; j++)
    {
        Node *newNode = new Node(currentId);
        currentId += 1;

        this->add_child(newNode);
        std::cout << newNode->get_name() << " in  " << this->get_name() << " ->" << this->get_nr_children() << std::endl;

        newNode->create_complete_tree(nr_child_nodes, tree_depth - 1);
    }
    currentId += 1;
}
spring mirage
#

something like that yes

#

obviously currentId won't work like that

pure atlas
#

hmhm oki thx! the structure looks right so now i just gotta fix the numbers

pure atlas
spring mirage
#

you can pass it by reference

#

then maybe this is not the expected solution

pure atlas
#

yeah idk, i could try to search the whole tree for the highest number and then increase that one for the next node... but that soudn right either xd

spring mirage
#

you can do an iterative version

pure atlas
#

?

#

how do you eman that?

spring mirage
#

one without recursion

pure atlas
#

nah it has to be recursive sadly :c

spring mirage
#

can you change the return type?

pure atlas
#

the fucntion doesnt return smth, it just reates the tree and another function then prints it

spring mirage
#

hmmm, but still, the easiest would be to take a reference to the current index

pure atlas
#

idk if thats allowed - but i created just a second fucntion doing the same but with index pointer xd now the ndoes dont have the same name

#

thx a lot! you solved my problem what i tried to do in 3 hours xd

#

!solved