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

本文介绍了遍历任意树结构中的每条唯一路径(从根到叶)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有几个列表:

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) 总是打印树的第一个可用路径(从根到叶子)，而 delete(Node) 切割已经访问过的树的叶子通过 traverse(Node).

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.

然后(未优化的版本)

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)); } } }