如何递归获取 Java 中树结构的所有叶子

Question

我有一个树节点的数据库 Table，如下所示。我想用这些树节点在 Java 中创建一个 ArrayList。 Arraylist 将以 Java 中的递归格式递归获取所有树节点。

输入：

数据库Table

Name            ID      Parent_ID
Parent          1   
Child-1         2           1
Child-1.1       3           2
Child-1.1.1     4           3
Child-2         5           1
Child-3         6           1
Child-1.1.1.1   7           4
Child-1.2       8           2

我想以下面的 Java 格式制作上面 table 的 ArrayList，其中 Sub 是 Child 节点的列表，如果没有 Child 节点则Sub 为空。

public class Node {

    private String id;
    private String name;
    private String type;
    private String value;
    private List<Node> sub;
}

输出：

Parent
- Child-1
  - Child-1.1
    - Child-1.1.1
      - Child-1.1.1.1
  - Child-1.2
- Child-2
- Child-3

有人可以帮忙在 Java 中创建一个递归函数来实现上述内容吗？

Answer 1

这是一个粗略的算法：

ArrayList<Integer> ar = new ArrayList<Integer>();

public extract(node root){
    foreach(node i : root.sub)
        extract(i);
    ar.add(i.value);
}

Answer 2

问题可以通过以下两个步骤解决，其中符号是一些 Java-ish 伪代码。首先，所有数据库行都必须放在 List<Node> Nodes 中，其中 Node 应该有一个额外的成员 ParentID 并且必须构建实际的树结构。这可以按如下时间 O(n^2) 完成，这不是最优的，但不会对节点索引做出额外的假设。

for (int i = 0; i < Nodes.Count(); i++) // iterate nodes
{
    for (int j = 0; j < Nodec.Count(); j++) // search parent of i-th node
    {
        if (Nodes[j].id.Equals(Nodes[i].ParentID)) // j-th node is parent of i-th node
        {
            Nodes[j].sub.add(Nodes[i]); // add i-th node to children of j-th node
        }
    }
}

之后，可以很容易地识别叶子，因为这些是没有子节点的节点。

for (int i = 0; i < Nodes.Count(); i++)
{
    if (Nodes[i].sub.Count() == 0) // i-th node is a leaf
    {
        // do something with a leaf
    }
}

请注意，我对Java从头顶不太熟悉，但算法思想应该是可以理解的。

Answer 3

递归函数：

public void printTree(Node tree,int num)
{
    if(tree==null || tree.getSub()==null)return;
    for(Node n : tree.getSub())
    {
    System.out.println(new String(new char[num]).replace("[=10=]", "   ")+"*"+n.getName());
printTree(n,num+1);
}
}

public void callRec(Node tree)
{
    System.out.println(tree.getName());
    printTree(tree,1);
}

结果将是：

Parent
*Child-1
  *Child-1.1
     *Child-1.1.1
        *Child-1.1.1.1
  *Child-1.2
*Child-2
*Child-3

如何递归获取 Java 中树结构的所有叶子

How to get recursively get all leaves of a Tree Structure in Java

java

tree

recursion