遍历任意的树结构每一个独特的路径(从根到叶) [英] Traverse every unique path (from root to leaf) in an arbitrary tree structure
问题描述
我有几个列表:
A = [A0,A1] //名单的数量变化
B = [B0,B1,B2] //如在一个列表中的元素的数量。
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
我被破坏树本身同时穿越它以如下方式这样做
公共静态无效删除(节点node){
如果(node.isLeaf()&安培;&安培;!node.isRoot()){
节点的父= node.getParent();
parent.removeChild(节点);
删除(父);
}
}
公共静态无效移动(节点node){
如果(node.isRoot())
的System.out.println(---);
其他
的System.out.println(node.getName());
如果(node.isLeaf()){//我还在努力
如果(!node.isRoot()){//删除不必要的检查
删除(节点);
遍历(node.getRoot());
}
} 其他 {
子节点= node.firstChild();
如果(NULL!=儿)
遍历(子);
}
}
移动(节点)
始终打印树的第一个可用路径(从根到叶),而删除(节点)
的削减已经访问了移动(节点)
。
这按预期工作,但我渴望找到一个解决方案来遍历pviously描述方式不破坏它的$ P $树。 如果有一种方法可以做到这一点,然后我很想遍历此相同的结构,但在图的形式,以减少冗余。
确定。我想你实际上意味着要找到每一个路径从根到叶。
然后(一个未优化的版本)
无效移动(节点根){
//假设根!= NULL
遍历(根,新的LinkedList<节点>());
}
私人无效移动(节点根,LinkedList的<节点>路径){
path.add(根);
如果(root.isLeaf()){
打印路径;
}
其他 {
为根的每个节点{
移动(节点,新的LinkedList<节点>(路径));
}
}
}
I have several lists:
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"]
I convert this structure into a tree:
_____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
I'm printing every unique path in the tree (omitting the root):
a0 -> b0 -> c1 -> d0
a0 -> b0 -> c1 -> d1
a0 -> b1 -> c1 -> d0
...
a1 -> b2 -> c1 -> d1
I'm doing this by "destroying" the tree itself while traversing it in the following way:
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)
always prints the first available path of the tree (from root to leaf) while delete(Node)
cuts leafs of the tree that is already visited by traverse(Node)
.
This works as intended, but I'm keen to find a solution to traverse the tree in the previously described way without destroying it. If there's a way to do this then I'd be interested to traverse this same structure, but in the form of a graph to reduce redundancy.
OK. I think you actually mean that you want to find every path from root to a leaf.
Then (a un-optimized version)
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));
}
}
}
这篇关于遍历任意的树结构每一个独特的路径(从根到叶)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!