java - 在嵌套列表中搜索项目

Question

假设我有一个类型为 T 的对象，其中有一个带有 ArrayList 的字段，该字段保存类型为 T 的对象，我将其称为列表。我还有另一个 T 类型的对象，我将其称为目标。我正在努力寻找目标。为此，我想首先遍历列表以查看目标是否存在。如果是，我想返回原始对象。如果不是，那么我想通过列表逐个对象进行检查，并检查每个列表的目标(如果找到则返回对象)。我想递归地继续此搜索，直到找到匹配项。

我不知道如何实现这一点。我能想到的两个选择是 while 循环和递归。然而，当我检查各种列表时，我必须在各个级别之间 Swing ，但我不知道如何做到这一点。

我的另一个想法是，我想做的事情与树的层序遍历是一样的。然而，到目前为止我只了解了二叉树，我不知道如何或是否可以将其转换为一棵树，如果可以在不遍历整个树的情况下进行级别顺序遍历。

下面，请参阅我迄今为止编写的代码。这只会检查第一个列表是否匹配，并且不会更深入，这正是我所需要的。

/**
     * Searches for the shortest path between start and end points in the graph.
     * @param start
     * @param end
     * @return a list of data, starting with start and ending with end, that gives the path through
     * the graph, or null if no such path is found.  
     */
    public List<T> shortestPath(T startLabel, T endLabel){
        List<T> list = new ArrayList<>();
        list.add(startLabel);
        while(true){
            List<T> successors = successorList(startLabel);
            if (containsMatch(successors, endLabel)) {
                findMatch(successors, endLabel);
            }
        }
    }

这种情况有意义吗？如果是这样，有什么想法吗？有可能吗？ (我尝试搜索，但所有查询都没有任何有用的结果)

预先感谢您的帮助。干杯!

Answer 1

T 听起来确实像代表一棵树，但这仅当对于其 ArrayList 中的每个 T(以及每个 ArrayList 中的每个 T 等)，所有 T 都是唯一的。否则，当它不是一棵树时，像一棵树一样遍历它可能会导致无限循环。

我不明白你所说的“是否可以在不遍历整棵树的情况下进行级别顺序遍历”是什么意思。如果你的树 T 没有顺序感，那么你将不得不遍历整棵树，因为目标 T 可能在任何地方。这正是您想做的，不是吗？

将此问题视为两个相互递归函数可能在概念上有所帮助。一个函数可以称为SearchT，另一个函数可以称为SearchArrayListT。 SearchT 检查 T 是否是“目标”T。如果不是，它会在 T 的 ArrayList 的字段上调用 ​​SearchArrayListT。

如果传入的 ArrayList 为空，SearchArrayListT 会生成“false”(即，您表示尚未找到目标这一事实。)否则，SearchArrayListT 对 ArrayList 的每个元素调用 SearchT，在每个元素后检查是否“true”被返回(或者无论如何你代表找到目标的事实)。这实际上是深度优先搜索，但您应该得到相同的结果。您可以在维基百科页面上看到如何对它们进行广度优先搜索:https://en.wikipedia.org/wiki/Breadth-first_search

具体来说，对于您的问题，您似乎正在找到从“根”T 到“目标”T 的路径，因此在这个相互递归期间，您希望传递“到目前为止的路径”，并且沿着递归附加到“到目前为止的路径”。更具体地说，SearchT 将附加在 pathSoFar 中，然后调用 SearchArrayListT，其中 pathSoFar 附加有 SearchT 也作为参数接收的“T”。像这样的事情:

SearchT(T t, List<T> pathSoFar) //append t to pathSoFar, check if 
//t is the goal; if it is not call SearchArrayListT(t.list, pathSoFar.add(t)); 

SearchArrayListT(ArrayList<T>, List<T> pathSoFar)