Tree with multiple child nodes and next node

Question

I want to build a tree with the following characteristics:

1. Every node can have 1 "next node".
2. Every node can have multiple child nodes.
3. The number of child nodes can vary from one node to the other

I was thinking of a struct which looked like this:

struct tree {
  int value;
  struct tree* nextnode;
  struct tree** childnode;
};

The number of children at each node has to be parametrized. I am not sure how to do this. Thanks in advance!

Edit: Let me try to define it using an example: Let us take the starting node. Now, I will define at compile time that there will be 3 NextNodes and each of these NextNodes will have 2 ChildNodes. This is at Depth=0. At Depth = 1 (i.e. for each child node from Depth=0) I specify that there will be 4 NextNodes and for each of these NextNodes there will be 3 ChildNodes and so on. Hope I am able to convey it properly. Please do ask if I am not clear somewhere.

Edit2: Here is a pic:

Answer 1

You could use Boost.Graph library.

Very complicated at first, but provide efficient data storage and highly optimized graph algorithm implementations.

From the site:

Algorithms

The BGL algorithms consist of a core set of algorithm patterns (implemented as generic algorithms) and a larger set of graph algorithms. The core algorithm patterns are

• Breadth First Search
• Depth First Search
• Uniform Cost Search

By themselves, the algorithm patterns do not compute any meaningful quantities over graphs; they are merely building blocks for constructing graph algorithms. The graph algorithms in the BGL currently include

• Dijkstra's Shortest Paths
• Bellman-Ford Shortest Paths
• Johnson's All-Pairs Shortest Paths
• Kruskal's Minimum Spanning Tree
• Prim's Minimum Spanning Tree
• Connected Components
• Strongly Connected Components
• Dynamic Connected Components (using Disjoint Sets)
• Topological Sort Transpose
• Reverse Cuthill Mckee Ordering
• Smallest Last Vertex Ordering
• Sequential Vertex Coloring

Data Structures

The BGL currently provides two graph classes and an edge list adaptor:

• adjacency_list
• adjacency_matrix
• edge_list

The adjacency_list class is the general purpose “swiss army knife” of graph classes. It is highly parameterized so that it can be optimized for different situations: the graph is directed or undirected, allow or disallow parallel edges, efficient access to just the out-edges or also to the in-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.

The adjacency_matrix class stores edges in a |V| x |V| matrix (where |V| is the number of vertices). The elements of this matrix represent edges in the graph. Adjacency matrix representations are especially suitable for very dense graphs, i.e., those where the number of edges approaches |V|2.

The edge_list class is an adaptor that takes any kind of edge iterator and implements an Edge List Graph.

Answer 2

Below is method that develops a node with multiple nodes.

Reference: https://www.geeksforgeeks.org/generic-tree-level-order-traversal/

/* Let us create below tree 
*            10 
*    / / \ \ 
*    2 34 56 100 
*    / \         | / | \ 
*    77 88   1 7 8 9 
*/



 // CPP program to do level order traversal 
 // of a generic tree 

 #include <bits/stdc++.h> 
 using namespace std; 

 // Represents a node of an n-ary tree 

 struct Node 
 { 
   int key; 
   vector<Node *>child; 
 }; 

// Utility function to create a new tree node 

 Node *newNode(int key) 
 { 
    Node *temp = new Node; 
    temp->key = key; 
    return temp; 
 } 


// Driver program 

int main() 
{ 
/* Let us create below tree 
*            10 
*    / / \ \ 
*    2 34 56 100 
*    / \         | / | \ 
*    77 88   1 7 8 9 
*/
Node *root = newNode(10); 
(root->child).push_back(newNode(2)); 
(root->child).push_back(newNode(34)); 
(root->child).push_back(newNode(56)); 
(root->child).push_back(newNode(100)); 
(root->child[0]->child).push_back(newNode(77)); 
(root->child[0]->child).push_back(newNode(88)); 
(root->child[2]->child).push_back(newNode(1)); 
(root->child[3]->child).push_back(newNode(7)); 
(root->child[3]->child).push_back(newNode(8)); 
(root->child[3]->child).push_back(newNode(9)); 


return 0; 
}