java - 高效的树排序

Question

我对在 J2ME 应用程序中构建树结构的方法不太满意。有人能指出一个更高效的方向吗？如果您需要更多代码来理解我的代码片段，请在下面发表评论。 Java版本是1.4。

非常感谢，
雷特

if(companyList != null) {
    companyList.setNodeStructure(null);

    Hashtable nodes = new Hashtable();
    for(Enumeration e = companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
        if(temp_comp.getParentCompanyId() == 0 && temp_comp.getCompanyId() > 0) {
            getSubTree(temp_comp.getCompanyId(), companyList, nodes); 
        }
    }   
    companyList.setNodeStructure(nodes);

方法

private void getSubTree(int CompanyId, CompanyList _companyList, Hashtable nodes) {
    Vector children = getChildren(CompanyId, _companyList);
    if(children.size() > 0) {
        nodes.put(new Integer(CompanyId), children);
        for(Enumeration e = children.elements(); e.hasMoreElements();) {
            Company temp_comp = (Company)e.nextElement();
            getSubTree(temp_comp.getCompanyId(), _companyList, nodes);
        }
    }
}

private Vector getChildren(int CompanyId, CompanyList _companyList) {
    Vector temp = new Vector();
    for(Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
            if(temp_comp.getParentCompanyId() == CompanyId) {
                temp.addElement(temp_comp);
            }
        }
    temp.trimToSize();
    return temp;
}

Answer 1

getChildren() 可能会更加高效。看起来，每次调用它时，您都会迭代整个 CompanyList 以查找其父级与给定 CompanyId 匹配的公司列表。这对于充满 vector 的哈希表来说简直就是尖叫。哈希表的键将是父 ID，而不是原始 ID；这些值将是包含父 ID 与给定父 ID 匹配的公司的 vector 。那么你就有了:

private Vector getChildren(int CompanyId, Hashtable companyParentLoookup) {
    return (Vector) companyParentLookup.get(CompanyId);
}

当然，看起来您编写 getSubTree 的目标实际上是构造我刚才描述的哈希表。这里的问题是您试图按公司 ID 构建它，而不是按公司 ID 构建它。您可以尝试这样做，构建 companyParentLookup:

private Hashtable calcLookupTable(CompanyList _companyList) {
    Hashtable retval = new Hashtable();
    for (Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company) e.nextElement();
        Integer parent_id = temp_comp.getParentCompanyID();

        if (retval.containsKey(parent_id) == false) {
            retval.put(parent_id, new Vector());
        }
        retval.get(parent_id).add(temp_comp);
    }
    return retval;
}

然后您可以将companyParentLookup结构直接粘贴到companyList的nodeStructure中。

编辑:这里的相关点是，您可以根据需要延迟初始化哈希表的 vector 条目；每次您都可以检查哈希表是否有所需的条目，如果没有，您只需将其放入即可。这使您可以通过将公司作为子项进行迭代而不是作为父项进行迭代来创建哈希表。如果你真的不能使用除了哈希表和 vector 之外的任何东西，那么这不是实现树的一个坏方法；它大致相当于使用邻接表保留图形数据结构。实际上，我为图​​形数据结构编写了一些看起来非常像这样的东西，尽管是使用 HashMap。

呃，这有帮助吗？