子项具有不同父项的树结构
子项具有不同父项的树结构
提问于 2015-10-30 15:25:59
我需要一种数据结构来存储整数，这样每个数字都与其下面的两个(或更多)相邻数字相连，例如
1
/ \
3 2
/ \ / \
5 6 4
/ \ / \ / \
7 9 8 10我正在尝试用java来实现这一点。我是数据结构的新手，我能够实现树形结构，但我发现在java中实现这一点很困难。
回答 3
Stack Overflow用户
发布于 2015-10-30 16:50:36
您可以将其以可变长度的2-D矩阵的形式存储。
1
3 2
5 6 4
7 9 8 10对于索引(i,j)，它的左子索引将是索引(i+1,j)，右子索引将是(i+1,j+1)，如果i+1和j+1在2个子索引的范围内。你也可以将其扩展为更多的孩子。
Stack Overflow用户
发布于 2015-10-30 18:32:26
您可以按如下方式创建树结构
class Node
{
Node mNodeLeftParent;
Node mNodeRightParent;
Node mNodeLeftChild;
Node mNodeRightChild;
int miValue;
}
class MyTree
{
Node root;
}Stack Overflow用户
发布于 2015-10-30 19:51:06
就数据结构而言，您的情况不是一棵树，而是一张图(更一般)。JDK没有Graph数据类型(就此而言，也没有Tree )，所以您必须使用类似JGraphT的数据类型。
DirectedGraph<Integer, DefaultEdge> g =
SimpleDirectedGraph.<Integer, DefaultEdge> builder(DefaultEdge.class)
.addEdgeChain(1, 3, 5, 7)
.addEdgeChain(1, 3, 5, 9)
.addEdgeChain(1, 3, 6, 9)
.addEdgeChain(1, 3, 6, 8)
.addEdgeChain(1, 2, 6, 9)
.addEdgeChain(1, 2, 6, 8)
.addEdgeChain(1, 2, 4, 8)
.build();
// the edge chains are just to be exhaustive in all the paths
// but only one edge is added, for each pair, like the following
g.addVertex(10);
g.addEdge(8, 10);
Stream<Integer> parents = g.incomingEdgesOf(6).stream().map(g::getEdgeSource);
Stream<Integer> children = g.outgoingEdgesOf(6).stream().map(g::getEdgeTarget);
System.out.println(" parents of 6 = " + parents.collect(Collectors.toList()));
System.out.println("children of 6 = " + children.collect(Collectors.toList()));您也可以使用无向图，但是您需要获得连接6的所有边，并检查6是源还是目标，以获得您想要的结果。
对于您的场景，可能会有一些开销，因为JGraphT非常通用。尽管如此，它仍然非常方便，并且在第一次尝试API之后，使用起来也很简单。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33430726
复制相关文章
相似问题
腾讯云开发者
