我正在尝试编写
java代码以返回树中的节点列表.
树看起来像
树看起来像
节点类是
class Node{
String label;
List<Node> children;
}
我正在尝试这种方式.但是无法理解如何编写循环来遍历.
public List<Node> returnAllNodes(Node node){
List<Node> listOfNodes =
new ArrayList<Node>();
boolean iterationCompleted = false;
if(node==null){
return null;
}
while(!iterationCompleted){
if(node.getChildren()==null){
listOfNodes.add(node);
break;
}
else{
//
}
}
return null;
//return traverseAndReturnAllNodes(node.getChildren().get(0));
}
请帮忙.
解决方法
如果您确定结构是树(节点不能有多个父节点),则会按深度优先顺序列出节点：
public static List<Node> returnAllNodes(Node node){
List<Node> listOfNodes = new ArrayList<Node>();
addAllNodes(node,listOfNodes);
return listOfNodes;
}
private static void addAllNodes(Node node,List<Node> listOfNodes) {
if (node != null) {
listOfNodes.add(node);
List<Node> children = node.getChildren();
if (children != null) {
for (Node child: children) {
addAllNodes(child,listOfNodes);
}
}
}
}
如果节点可以有多个父节点,请将addAllNodes的第一行更改为：
if (node != null && !listOfNodes.contains(node)) {
广度优先算法如下：
public static List<Node> returnAllNodes(Node node){
List<Node> listOfNodes = new ArrayList<Node>();
if (node != null) {
listOfNodes.add(node);
for(int i = 0; i < listOfNodes.size(); ++i) {
Node n = listOfNodes.get(i);
List<Node> children = n.getChildren();
if (children != null) {
for (Node child: children) {
if (!listOfNodes.contains(child)) {
listOfNodes.add(child);
}
}
}
}
}
return listOfNodes;
}
