C语言 具有多个子节点和下一个节点的树

Tree with multiple child nodes and next node

提问by user560913

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

1. 每个节点可以有 1 个“下一个节点”。
2. 每个节点可以有多个子节点。
3. 子节点的数量可以从一个节点到另一个节点不同

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 NextNodesand each of these NextNodeswill 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 NextNodesand for each of these NextNodesthere will be 3 ChildNodesand so on. Hope I am able to convey it properly. Please do ask if I am not clear somewhere.

编辑：让我试着用一个例子来定义它：让我们以起始节点为例。现在，我将在编译时定义将有 3 个NextNodes，每个NextNodes将有 2 个ChildNodes。这是在Depth=0。在Depth = 1（即对于来自 的每个子节点Depth=0），我指定将有 4 个NextNodes，对于每个子节点，NextNodes将有 3 个ChildNodes，依此类推。希望我能够正确地传达它。请不要问我是否有不清楚的地方。

Edit2: Here is a pic:

Edit2：这是一张图片：

回答by 9dan

You could use Boost.Graphlibrary.

您可以使用Boost.Graph库。

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

BGL 算法由一组核心算法模式（作为通用算法实现）和一组更大的图算法组成。核心算法模式是

• 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

算法模式本身不计算任何有意义的图形量；它们只是构建图算法的构建块。BGL中的图算法目前包括

• 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

• Dijkstra 的最短路径
• 贝尔曼-福特最短路径
• Johnson 的所有对最短路径
• Kruskal 的最小生成树
• Prim 的最小生成树
• 连接组件
• 强连接组件
• 动态连接组件（使用不相交集）
• 拓扑排序转置
• 反向 Cuthill Mckee 排序
• 最小最后顶点排序
• 顺序顶点着色

Data Structures

数据结构

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

BGL 目前提供了两个图类和一个边列表适配器：

• adjacency_list
• adjacency_matrix
• edge_list

• 邻接表
• 邻接矩阵
• 边列表

The adjacency_listclass 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.

本adjacency_list类是通用的“瑞士军刀”图类的。它是高度参数化的，因此可以针对不同情况进行优化：图是有向或无向的，允许或禁止平行边，有效访问仅出边或入边，快速插入和删除顶点额外空间开销等的成本。

The adjacency_matrixclass 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.

在adjacency_matrix类存储在边缘| V | ×|V| 矩阵（其中 |V| 是顶点数）。该矩阵的元素表示图中的边。邻接矩阵表示特别适用于非常密集的图，即边数接近 |V|2 的图。

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

该edge_list班是一个适配器，采用任何一种边迭代器和器具的边列表图的。

回答by Ank_247shbm

Below is method that develops a node with multiple nodes.

下面是开发具有多个节点的节点的方法。

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

参考：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; 
} 

回答by apprentice

This is a N-ary tree. I suggest you of split in Tree and Node

这是一棵 N 叉树。我建议你拆分树和节点

typedef struct tree tree;
typedef struct node node;

struct tree {
    node * root;
};

struct node {
    int value;
    node * next_node;
};

now you can perform all the operation of the tree structure

现在您可以执行树结构的所有操作

here an example

这里有一个例子

node * add_child(node *parent, int child_value){
    node * child = malloc(sizeof(node));
    child->value = child_value;
    if(parent->next == NULL)
        parent->next = child;
    else{
        node * temp = parent->next;
        while(temp->next != NULL)
            temp = temp->next;
        temp->next = child;
    }
    return child;
}