java - 搜索多树数据结构的最有效方法

Question

我想知道是否有比我一直在做的更有效的方法来搜索多树。我最近为一个项目构建了一个多树数据结构，如下所示。

洞穴会将各方保存在数组列表中。不同的政党将拥有不同的生物。不同的生物会持有不同的元素。

我需要一种方法来搜索整个树以将对象与其具有的属性(例如索引)相匹配。这是我的程序片段，它搜索每个 ArrayList 以查看派对、生物、宝藏或 Artifact 是否与我称为索引的 int 匹配。

编辑(解释我的代码)Party、Creature、Treasure 和Artifact 类都有索引、名称、类型等属性。多树以Cave 集为根注释。 Cave 有一个 ArrayList，它可以包含许多 Party 对象。每个 Party 都有一个 ArrayList，其中可以包含许多 Creature 对象。每个生物都有两个数组列表，一个用于保存 Artifact 对象，一个用于保存 Treasure 对象。

下面我正在搜索以查看哪个派对、生物、 Artifact 或宝藏拥有我正在搜索的特定索引。我通过遍历派对来做到这一点，我在每个派对中查看生物，并在每个生物中查看文物和宝藏。这就是为什么我在 for 循环中有这么多 for 循环的原因:(。

case 0 :
            int index =                 Integer.parseInt( stat );
            for ( Party p : SorcerersCave.theCave.parties ) {
                if ( index == p.getIndex()) {
                    generateInterface.theGame.printOutput( "\t" + p );
                    break;
                } else {
                    for ( Creature c : p.members ){
                        if ( index == c.getIndex() ){
                            generateInterface.theGame.printOutput( "\t" + c );
                            break;
                        } else {
                            for ( Treasure t : c.inventory ){
                                if ( index == t.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + t );
                                    break;
                                }
                            }
                            for ( Artifact a : c.artifacts ){
                                if ( index == a.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + a );
                                    break;
                                }
                            }
                        }
                    }
                }
            }

我觉得这段代码太复杂了，很难理解。该代码有效，但它在我原本非常好看的代码上留下了丑陋的污点。我一直在四处寻找更好的方法，甚至是改进它的方法。

注意* 项目要求禁止我们将每个对象放在同一个 ArrayList 中。

Answer 1

您的类可以实现一个公共(public)接口(interface)SearchableByIndex，它看起来像这样并且将由树中的每个类实现:

public interface SearchableByIndex {
    public SearchableByIndex searchByIndex(int index);
    public int getIndex();
}

然后 Cave、Party 和 Creature 需要此代码:

public SearchableByIndex searchByIndex(int index) {
    if (getIndex() == index) {
        return this;
    } else {
        for (Party party : parties) {    // or Creature creature : members etc.
            SearchableByIndex found = party.searchByIndex(index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

宝藏 Artifact 的版本:

public SearchableByIndex searchByIndex(int index) {
    return (getIndex() == index) ? this : null;
}

而不是你在那里的嵌套循环，你会有

case 0:
    int index = Integer.parseInt(stat);
    SearchableByIndex foundItem = SorcerersCave.theCave.searchByIndex(index);
    if (foundItem != null) {
        generateInterface.theGame.printOutput("\t" + foundItem);
    } else {
        // print out that the item was not found
    }
    break;

虽然每个类上的 searchByIndex() 方法看起来都是重复的，但这是 OOP 的实现方式。这样，每个类都会负责搜索其所有内容。在您的情况下，所有类的代码都非常相似(唯一的变化是带有 for 循环的行)，但您可以认为这是一个意外 - 任何类都可以包含它想要的任何数据，其他类不应该关心关于它如何存储数据。

将来，如果您的某个类包含更多可搜索数据(Treasure、Artifact 和 Hostage？)，或者您会想更改其数据结构(考虑 HashMap，如果可以的话!)，您只需更改特定类中的 searchByIndex() 方法即可。

此外，只有包含数据的类应该知道如何它包含它。您现在拥有它的方式，调用搜索的其他一些类确切地知道每个类中的数据存储方式 - 这不应该。如果一个类发生变化，它会破坏其他类的内部代码。例如，Cave 类应该在它的文档中说明它拥有例如不同的 Party 实例，如果您通过 searchForIndex() 搜索它，它可以给出其中的一些实例。