在列表中查找元素的所有父项

Question

查找列表中元素的所有父元素

public class MyNode {
    private String name;
    private List<MyNode> nodeList;
}

List<MyNode> root = new ArrayList<>();
MyNode a = new MyNode("a");
List<MyNode> aList  = new ArrayList<>();
aList.add(new MyNode("a1"));
aList.add(new MyNode("a2"));
a.setNodeList(aList);

MyNode b = new MyNode("b");
List<MyNode> bList  = new ArrayList<>();
bList.add(new MyNode("b1"));
bList.add(new MyNode("b2"));
b.setNodeList(bList);

root.add(a);
root.add(b);

示例：

输入b1到return包含b1节点和b节点的列表

如何用java实现？谢谢

Answer 1

我创建了这个程序，它使用递归并打印从父节点到节点的层次结构。

import java.util.ArrayList;
import java.util.List;

public class MyNode {
private String name;
private List<MyNode> nodeList;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public List<MyNode> getNodeList() {
    return nodeList;
}

public void setNodeList(List<MyNode> nodeList) {
    this.nodeList = nodeList;
}

public MyNode(String name) {
    super();
    this.name = name;
}

public static void main(String f[]) {
    List<MyNode> root = new ArrayList<>();
    MyNode a = new MyNode("a");
    List<MyNode> aList = new ArrayList<>();
    aList.add(new MyNode("a1"));
    aList.add(new MyNode("a2"));
    a.setNodeList(aList);

    MyNode b = new MyNode("b");
    List<MyNode> bList = new ArrayList<>();

    MyNode nodeb1 = new MyNode("b1");
    MyNode nodeb11 = new MyNode("b11");
    MyNode nodeb12 = new MyNode("b12");
    List<MyNode> b1List = new ArrayList<>();
    b1List.add(nodeb11);
    b1List.add(nodeb12);
    nodeb1.setNodeList(b1List);
    bList.add(nodeb1);
    bList.add(new MyNode("b2"));
    b.setNodeList(bList);

    root.add(a);
    root.add(b);
    List<MyNode> list = new ArrayList<>();
    for (MyNode node : root) {
        findAll(list, node, "b12");
        if (list.size() != 0)
            break;
    }
    list.stream().forEach(s -> System.out.println(s.getName()));

}

public static List<MyNode> findAll(List<MyNode> list, MyNode node, String nodeName) {

    if (node.getName().equals(nodeName)) {
        list.add(node);
        return list;
    } else if (node.getNodeList() != null) {
        for (MyNode myNode : node.getNodeList()) {
            List<MyNode> temp = new ArrayList<>();
            findAll(temp, myNode, nodeName);
            if (temp.size() != 0) {
                list.add(node);
                list.addAll(temp);
                break;
            }
        }
        return list;
    } else
        return null;

 }

}

Answer 2

您需要使用 Depth First Search，从每个根开始。这是使用递归标准实现的。如果找到一个名称与查询字符串匹配的节点，或者它有一个匹配的子节点，则将其添加到路径中。将它添加到前面会创建一条从根到叶的路径。

static boolean findPath(LinkedList<MyNode> path, MyNode node, String qry)
{
    if(node == null) return false;
    
    if(node.name.equals(qry) || findPath(path, node.nodeList, qry))
    {
        path.addFirst(node);
        return true;
    }
    return false;
}

static boolean findPath(LinkedList<MyNode> path, List<MyNode> nodeList, String qry)
{
    if(nodeList == null) return false;
    
    for(MyNode child : nodeList)
        if(findPath(path, child, qry)) return true;
    
    return false;
}

测试：

LinkedList<MyNode> path = new LinkedList<>();
for(MyNode node : root)
    if(findPath(path, node, "b1")) break;
System.out.println(path);

输出：

[b, b1]

在列表中查找元素的所有父项

Find all parents for element in list

java

algorithm

recursion

search

list