Java中如何将平坦的组织结构转换为树形视图

Question

I have my org structure as given below -

      T1
|''''   ''''|
T2          T3
|
T4

存储在数据库中的格式为 -

+----+---------+-----------+-----------+
| ID | TEAM_ID | PARENT_ID | TEAM_NAME |
+----+---------+-----------+-----------+
|  1 |       1 |         1 | T1        |
|  2 |       2 |         2 | T2        |
|  3 |       2 |         1 | T2        |
|  4 |       3 |         1 | T3        |
|  5 |       3 |         3 | T3        |
|  6 |       4 |         4 | T4        |
|  7 |       4 |         2 | T4        |
|  8 |       4 |         1 | T4        |
+----+---------+-----------+-----------+

我希望能够从上面表格中提供的扁平数据重新构建上述树形结构。

我的当前方法是 -

Map<Long, List<TeamHierarchy>> tree = new HashMap<>();
        for (TeamHierarchy n : flatTeamStructure) {
            if (n.getParentTeamId() == n.getTeamId()) {
                if (!tree.containsKey(n.getParentTeamId())) {
                    tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>());
                }
            } else {
                if (!tree.containsKey(n.getParentTeamId())) {
                    tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>());
                }
                tree.get(n.getParentTeamId()).add(n);
            }
        }

这并不完全正确，因为我在T1的子级中也得到了T4。我只想要直接的子级。有没有不需要递归的建议？

- Ananda

---

你们的扁平化团队结构在上表中是否足够好以构建一个良好的树形结构？例如，以T4为例，它的PARENT_ID是4、2、1，哪一个是直接父级？你如何判断？ - SomeDude

@svasa 这是个问题。我们肯定可以，但需要使用递归，并且时间复杂度为O(N^2)。 - Ananda

Answer 1

我不确定这是最有效的方法，但应该可以工作。我会尝试将每个团队ID映射到其正确的父级。这里的难点在于您的表包含冗余信息，因此必须能够将其清除。

思路是从根开始递归地构建树形结构，并在深入树形结构时修改父级节点，以找到更好的父级节点。以下是一个快速示例独立程序，应该能帮助您入门。

public class TestTree {
    private static List<Entry> entries = new ArrayList<Entry>();

    public static void main(String[] args) throws Exception {
        // simulate the DB entries
        entries.add(new Entry(1, 1, 1, "T1"));
        entries.add(new Entry(2, 2, 2, "T2"));
        entries.add(new Entry(3, 2, 1, "T2"));
        entries.add(new Entry(4, 3, 1, "T3"));
        entries.add(new Entry(5, 3, 3, "T3"));
        entries.add(new Entry(6, 4, 4, "T4"));
        entries.add(new Entry(7, 4, 2, "T4"));
        entries.add(new Entry(8, 4, 1, "T4"));

        // the root is the one entry with no parent other than self
        int root = 1;

        // map all relationships to the root
        Map<Integer, Integer> tree = new HashMap<Integer, Integer>();   // ID -> parent ID
        buildTree(tree, root);

        System.out.println(tree);

        // From this Map, it should be pretty obvious how to build the tree.
    }

    private static void buildTree(Map<Integer, Integer> tree, int parentId) {
        boolean dirty = false;
        for(Entry entry : entries) {
            if(entry.parentId == parentId && entry.teamId != parentId) {
                tree.put(entry.teamId, parentId);
                dirty = true;
            }
        }

        if(dirty) {
            // Continue building the tree from each node that was updated
            for(Integer nodeId : tree.keySet()) {
                if(tree.get(nodeId) == parentId) buildTree(tree, nodeId);
            }
        }
    }

    private static class Entry {
        int id;
        int teamId;
        int parentId;
        String teamName;

        Entry(int id, int teamId, int parentId, String teamName) {
            this.id = id;
            this.teamId = teamId;
            this.parentId = parentId;
            this.teamName = teamName;
        }
    }

更新

针对那些不喜欢递归方法的人（以及如果您的树太深，会使方法调用栈爆炸）：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class TestTree {
    private static List<Entry> entries = new ArrayList<Entry>();

    public static void main(String[] args) throws Exception {
        // simulate the DB entries
        entries.add(new Entry(1, 1, 1, "T1"));
        entries.add(new Entry(2, 2, 2, "T2"));
        entries.add(new Entry(3, 2, 1, "T2"));
        entries.add(new Entry(4, 3, 1, "T3"));
        entries.add(new Entry(5, 3, 3, "T3"));
        entries.add(new Entry(6, 4, 4, "T4"));
        entries.add(new Entry(7, 4, 2, "T4"));
        entries.add(new Entry(8, 4, 1, "T4"));

        // the root is the one entry with no parent other than self
        int root = 1;

        // map all relationships to the root
        Map<Integer, Integer> tree = new HashMap<Integer, Integer>();   //    ID -> parent ID
        Stack<Integer> stack = new Stack<Integer>();

        stack.push(root);
        do {
            int parentId = stack.pop();

            if(buildTree(tree, parentId)) {
                // Continue building the tree from each node that was updated
                for(Integer nodeId : tree.keySet()) {
                    if(tree.get(nodeId) == parentId) stack.push(nodeId);
                }
            }
        } while(!stack.isEmpty());

        System.out.println(tree);

        // From this Map, it should be pretty obvious how to build the tree.
    }

    private static boolean buildTree(Map<Integer, Integer> tree, int parentId) {
        boolean dirty = false;
        for(Entry entry : entries) {
            if(entry.parentId == parentId && entry.teamId != parentId) {
                tree.put(entry.teamId, parentId);
                dirty = true;
            }
        }

        return dirty;
    }

    private static class Entry {
        int id;
        int teamId;
        int parentId;
        String teamName;

        Entry(int id, int teamId, int parentId, String teamName) {
            this.id = id;
            this.teamId = teamId;
            this.parentId = parentId;
            this.teamName = teamName;
        }
    }
}

- mprivat

---

抱歉，我没有注意到您要求非递归方法。我编辑了我的回复并保留了两个版本。它们实际上是相同的，除了在非递归版本中，您必须跟踪自己的堆栈。 - mprivat