首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >如何在C++中创建树?

如何在C++中创建树?
EN

Stack Overflow用户
提问于 2016-10-07 10:00:50
回答 3查看 1.5K关注 0票数 0

我想在C++中创建一棵树。我有父-子关系和节点数,我想以某种方式存储这棵树。例如,如果我有一个图,我可以用邻接列表来存储它,或者使用向量向量,或者使用一个邻接矩阵。但是树呢?

例如,我有9节点,9-1=8父子关系:7-2,7-3,7-4,3-5,3-6,5-8,5-9,6-1。我想存储这棵树,例如,计算从最老的父(7)到子节点的最长路径(在本例中是7-3-5-87-3-5-9,路径的长度为4)。

EN

回答 3

Stack Overflow用户

发布于 2016-10-07 11:13:14

假设您的图是有向的,并且您不知道节点的数字范围,我建议您使用map<int, vector<int> >作为邻接列表:

代码语言:javascript
运行
复制
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int main()
{
    map< int, vector<int> > adj_list;

    int edges;
    cin >> edges;
    for ( int i=0; i<edges; ++i ){
        int u, v;
        cin>>u>>v;
        adj_list[u].push_back(v);
        //adj_list[v].push_back(u); // uncomment this line if your graph is directed
    }

    for ( auto it = adj_list.begin(); it != adj_list.end(); ++it ){
        const auto& children = it->second;
        cout << "children of " << it->first << " is:" << endl;
        for ( int i=0; i < children.size(); ++i ){
            cout << children[i] << " ";
        }
        cout << endl;
    }
}

输入

代码语言:javascript
运行
复制
8
7 2
7 3
7 4
3 5
3 6
5 8
5 9
6 1

输出

代码语言:javascript
运行
复制
children of 3 is:
5 6 
children of 5 is:
8 9 
children of 6 is:
1 
children of 7 is:
2 3 4 

使用这种结构,map的每个键都以vector<int>的形式保存该节点的邻接列表。这意味着您可以通过遍历adj_list[1]来访问节点1的子节点。

票数 1
EN

Stack Overflow用户

发布于 2016-10-07 10:10:31

我会通过一个节点包含指向节点的(智能)指针的向量来存储树。例如:

代码语言:javascript
运行
复制
struct tree_node
{
    int value;
    std::vector<std::unique_ptr<tree_node>> children;
};
票数 0
EN

Stack Overflow用户

发布于 2016-10-07 11:28:26

如果我有一个图,我可以用邻接表来存储它,或者使用向量向量,或者一个邻接矩阵。但是树呢?

但是树是一种图形类型。

Boost.Graph文档中,甚至有一个关于(家族)树的邻接列表的具体例子。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/39914542

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档