gpt4 book ai didi

algorithm - 遍历任意树结构中的每条唯一路径(从根到叶)

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:29:45 26 4
gpt4 key购买 nike

我有几个列表:

A = ["a0", "a1"]       // the number of lists varies
B = ["b0", "b1", "b2"] // such as the number of elements in a list.
C = ["c1"]
D = ["d0", "d1"]

我将这个结构转换成一棵树:

             _____ROOT______
/ \
___a0____ ____a1____
/ | \ / | \
b0 b1 b2 b0 b1 b2
| | | | | |
c1 c1 c1 c1 c1 c1
/ | / | / | / | / | / |
d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1

我正在打印树中的每条唯一路径(省略根):

a0 -> b0 -> c1 -> d0
a0 -> b0 -> c1 -> d1
a0 -> b1 -> c1 -> d0
...
a1 -> b2 -> c1 -> d1

我通过以下方式遍历树时“破坏”树本身来做到这一点:

public static void delete(Node node) {
if (node.isLeaf() && !node.isRoot()) {
Node parent = node.getParent();
parent.removeChild(node);
delete(parent);
}
}

public static void traverse(Node node) {
if (node.isRoot())
System.out.println("---");
else
System.out.println(node.getName());

if (node.isLeaf()) { // I'm still working on
if (!node.isRoot()) { // removing unnecessary checks
delete(node);
traverse(node.getRoot());
}
} else {
Node child = node.firstChild();
if (null != child)
traverse(child);
}
}

traverse(Node) 总是打印树的第一条可用路径(从根到叶),而 delete(Node) 剪切已经访问过的树的叶子通过遍历(节点)

这按预期工作,但我渴望找到一种解决方案,以前面描述的方式遍历树而不破坏它。如果有办法做到这一点,那么我有兴趣遍历相同的结构,但以图形的形式来减少冗余。

最佳答案

好的。我认为您实际上是想找到从根到叶的每条路径。

然后(未优化的版本)

void traverse (Node root) {
// assume root != NULL
traverse (root, new LinkedList<Node>());
}

private void traverse (Node root, LinkedList<Node> path) {
path.add(root);
if (root.isLeaf()) {
print path;
}
else {
for each node of root {
traverse (node, new LinkedList<Node>(path));
}
}
}

关于algorithm - 遍历任意树结构中的每条唯一路径(从根到叶),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5691926/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com