java - 从边构造一棵树

Question

如果我试图构建一个给定输入的树，每行一个边，其中一条边由它连接的两个顶点表示。是否可以使用 Node 结构/类来构造树，还是应该像图形一样将其表示为邻接列表？

我遇到的主要问题是输入的顺序。如果给我两个或多个起初根本没有连接的边，那么我有一堆没有连接的 Node 对象，而通常给你一棵树并插入树中只是使新节点成为子节点（或父节点？）另一个节点。

Answer 1

您是否考虑过使用图数据库技术（例如 neo4j）来存储节点和边？它是可嵌入的。

我在 scala 上广泛使用嵌入式 orientdb 和 tinkerpop 蓝图来绘制图形算法。我建议您查看这些技术，因为它们使这些问题和图算法构造变得微不足道。

属性图 dbs 使用索引来允许查找类型，因此您可以找到一个节点并从那里开始遍历图。无需重新发明轮子。

主要概念是：节点、边、属性（可以存在于节点或边上。边类型（例如在社交图中“知道”）。用于确定遍历方向的出边和内边边缘。以及提到的索引，它“键入”节点并允许查找。

可以查询每个节点的入边或出边，并且可以检查边的类型和属性。

Answer 2

如果您担心如何存储多个节点而不是一个根节点，一种方法是拥有一个指向 Node.js 的 N 指针数组。假设每个节点的索引为 0 到 N - 1，其中 N 是树中的节点数，您可以将第 i 个节点指针存储在数组的第 i 个元素中。

如果您将在堆栈中一次分配 N 个节点的数组（在 C/C++ 中），而不是使用指针，这种方法会更加有益。这是内存分配时间的巨大改进。