从 table 构建树

Question

我的数据库中有这样一个 table：

等等...

如您所见，有几个根父级（没有 parent_id 的父级），每个类别都有 n 个子级。

我想使用 class:

将其转换为 Java 中的树结构

private int id;
private String name;
private int parent;
private List<Category> children;

我通过此查询获取数据，我认为它可以改进：

SELECT c.*, ca.name, NVL(ca.parent_id, -1) AS parent_id FROM 
( 
    SELECT id, name, parent_id FROM categories 
) ca, 
( 
    SELECT LISTAGG(id || ':' || name || ':' || DECODE(parent_id, NULL, 
    DECODE(id,    NULL, NULL, -1), parent_id), ';') 
    WITHIN GROUP (ORDER BY id) AS  children, parent_id AS id 
    FROM categories 
    GROUP BY parent_id HAVING parent_id IS NOT NULL 
) c 
WHERE c.id = ca.id

我得到了每个类别（id、名称和 parent_id）和一个带有子项的字符串。

然后我循环抛出每个 ResultSet

List<Category> categories = new ArrayList<Category>();

while (rs.next()) { 
    Category c = new Category();
    c = JdbcToModel.convertToCategory(rs); //
    if (c.getParent() == -1) { // parent_id is null in database
        categories.add(c);
     else {
        categories = JdbcToModel.addCategoryToTree(categories, c);

    }
}

方法convertToCategory:

public 静态类别 convertToCategory(ResultSet rs) {

Category toRet = new Category();
List<Category> children = new ArrayList<Category>();
try {       
    children = parseCategoriesFromReview(rs.getString("children"));
    toRet.setId(rs.getInt("id"));
    toRet.setName(rs.getString("name"));
    toRet.setParent(rs.getInt("parent_id"));
    toRet.setChildren(children);

} catch (Exception e) {
    e.printStackTrace();
}
return toRet;

}

当我解析子字符串时的方法parseCategoriesFromReview:

public static List<Category> parseCategoriesFromReview(String categoriesString) {

        List<Category> toRet = new ArrayList<Category>();
        try {       
            if (!categoriesString.equals("::")) {

                String [] categs = categoriesString.split(";");
                for (String categ : categs) {
                    String [] category = categ.split(":");
                    Category c = new Category(Integer.parseInt(category[0]), category[1], Integer.parseInt(category[2]), new ArrayList<Category>());
                    toRet.add(c);
                }
            }

        } catch (Exception e) {
            e.printStackTrace();
        }

        return toRet;   
    }

和递归方法addCategoryToTree:

public static List<Category> addCategoryToTree(List<Category> categories, Category c) { 
    try {       
        for (Category ct : categories) {
            if (ct.getId() == c.getParent()) {
                ct.getChildren().add(c);
                break;
            } else {
                return addCategoryToTree(ct.getChildren(), c);
            }
        }

    } catch (Exception e) {
        e.printStackTrace();
    }
    return categories;

}

我认为最大的问题是在这个方法中......我从来没有写过一个内部有循环的递归方法，我不知道它是否正确。关键是我得到了一个树结构，但只有几个类别。最后的树没有那么多

也许我让事情变得复杂了，但我不知道如何用另一种方式来做..

有人帮忙吗？？

此致！

Answer 1

我相信你的问题出在结果的排序上。您的代码假定所有子 ID 的 ID 都高于所有父 ID，但根本不需要这样。例如。如果你有一个类别（id=5，parent=10），那么它将递归当前树（包含类别 id 的 0 到 4）。它不会找到正确的父类别，在这种情况下（取决于类别 class 中的 children 字段是否初始化为 null 或空列表）将打印堆栈跟踪一个异常，或者只是在所有叶类别中迭代一个空的 for 循环而不做任何事情。

要从这样的数据结构构建树，您可能需要采用两阶段方法。我更喜欢的一个（因为它是最简单的，虽然不是很高效）是：

初始化一个HashMap<Integer, List<Category>>
遍历您的数据库结果项并执行 mapFromAbove.get(category.getId()).add(category)（您还需要初始化这些列表）
完成后，执行mapFromAbove.get(0)，并迭代结果，对于每个结果，从同一个哈希映射中获取子节点并将其添加到它们中。然后递归地做这个。

其实很容易实现。

Answer 2

Oracle 设置:

CREATE TABLE categories ( id, name, parent_id ) AS
SELECT  1, 'Restauracion', NULL FROM DUAL UNION ALL
SELECT  2, 'Desayuno',        1 FROM DUAL UNION ALL
SELECT  3, 'Calidad',         2 FROM DUAL UNION ALL
SELECT  4, 'Organizacion',    2 FROM DUAL UNION ALL
SELECT  5, 'Variedad',        2 FROM DUAL UNION ALL
SELECT  6, 'Personal',     NULL FROM DUAL UNION ALL
SELECT  7, 'Pisos',           6 FROM DUAL UNION ALL
SELECT  8, 'Falta de Personal', 7 FROM DUAL UNION ALL
SELECT  9, 'Trato',           7 FROM DUAL UNION ALL
SELECT 10, 'Informacion',     7 FROM DUAL UNION ALL
SELECT 11, 'Idiomas',         7 FROM DUAL UNION ALL
SELECT 12, 'Otros',           7 FROM DUAL;

Java:

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.HashMap;

public class Category {
    private final String name;
    private final int id;
    private final Category parent;
    private final ArrayList<Category> children = new ArrayList<>();

    private Category(final String name, final int id, final Category parent) {
        this.name   = name;
        this.id     = id;
        this.parent = parent;
        if ( parent != null )
            parent.children.add(this);
    }

    @Override
    public String toString(){
        final StringBuffer buffer = new StringBuffer();
        buffer.append( '<' );
        buffer.append(name);
        buffer.append(':');
        buffer.append(id);
        buffer.append(':');
        buffer.append(parent == null ? "" : parent.name );
        buffer.append( '>' );
        return buffer.toString();
    }

    public String toHierarchyString(){
        return toHierarchyString(0);
    }

    private String toHierarchyString( int level ){
        final StringBuffer buffer = new StringBuffer();
        for ( int i = 0; i < level; i++ )
            buffer.append('\t');
        buffer.append( toString() );
        buffer.append( '\n' );
        for ( final Category child : children )
            buffer.append( child.toHierarchyString(level+1));
        return buffer.toString();
    }
    public static ArrayList<Category> loadCategoriesFromDatabase(){
        try{

            Class.forName("oracle.jdbc.OracleDriver");

            final Connection con = DriverManager.getConnection("jdbc:oracle:thin:@localhost:1521:XE","TEST","TEST");
            final PreparedStatement st = con.prepareStatement(
                    "SELECT id, name, parent_id " +
                    "FROM  categories " +
                    "START WITH parent_id IS NULL " +
                    "CONNECT BY PRIOR id = PARENT_ID " +
                    "ORDER SIBLINGS BY name"
            );

            final ResultSet cursor = st.executeQuery();

            final HashMap<Integer,Category> categoryMap = new HashMap<>();
            final ArrayList<Category> categories = new ArrayList<>();

            while ( cursor.next() )
            {
                final String name       = cursor.getString("NAME");
                final int id            = cursor.getInt("ID");
                final Integer parent_id = cursor.getInt("PARENT_ID");
                final Category parent   = categoryMap.get( parent_id );
                final Category category = new Category( name, id, parent );
                categoryMap.put(id, category);
                if ( parent == null )
                    categories.add(category);
            }
            return categories;
        } catch(ClassNotFoundException | SQLException e) {
            System.out.println(e);
        }
        return null;
    }

    public static void main( final String[] args ){
        ArrayList<Category> categories = loadCategoriesFromDatabase();
        for ( final Category cat : categories )
            System.out.println( cat.toHierarchyString() );
    }
}

输出:

<Personal:6:>
    <Pisos:7:Personal>
        <Falta de Personal:8:Pisos>
        <Idiomas:11:Pisos>
        <Informacion:10:Pisos>
        <Otros:12:Pisos>
        <Trato:9:Pisos>

<Restauracion:1:>
    <Desayuno:2:Restauracion>
        <Calidad:3:Desayuno>
        <Organizacion:4:Desayuno>
        <Variedad:5:Desayuno>

从 table 构建树

Contruct Tree from table

java

oracle

tree

recursion