如何實作數組轉樹結構（List to Tree）

1，編碼實作

該方法來自一位國外大神的部落格，通過`Map`以及Java對象在記憶體中的狀态來實作樹結構的組裝，相比較使用遞歸的方法，該方法的時間複雜度和空間複雜度都會低一些。

如果要實作按原來順序排列，可以使用`LinkedHashMap`

結構

// 方法體
private static void createTree(List<Node> nodes) {
        System.err.println("開始");
        Map<Integer, Node> mapTmp = new HashMap<>(nodes.size());
        // put all node to map
        for (Node node : nodes) {
            mapTmp.put(node.getId(), node);
        }

        //loop and assign parent/child relationships
        for (Node node : nodes) {
            Integer parentId = node.getParentId();
            // 如果是父級标簽，則不做處理
            if (parentId == null) {
                continue;
            }
            Node parentNode = mapTmp.get(parentId);
            if (parentNode == null) {
                continue;
            }
            // 将值賦給父級的子集中
            List<Node> children = parentNode.getChildren();
            if (children == null) {
                children = new ArrayList<>();
            }
            children.add(node);
            parentNode.setChildren(children);
            mapTmp.put(parentId, parentNode);
        }

        //extract root node
        List<Node> trees = new ArrayList<>();
        for (Node node :mapTmp.values()) {
            if (node.getParentId() == null) {
                trees.add(node);
            }
        }

        System.err.println(trees);
        System.err.println("結束");
    }
           

DEMO

如下是代碼實作及測試

class Node {

    private String name;
    private Integer id;
    private Integer parentId;
    private List<Node> children;

    // getter and setter
}

public class CreateTree {
    
    public static void main(String[] args) {
        //Create a List of nodes
        Node node1 = new Node("Five", 5, 4);
        Node node2 = new Node("Four", 4, 2);
        Node node3 = new Node("Two",  2, 1);
        Node node4 = new Node("Three", 3, 2);
        Node node5 = new Node("One",   1, null);
        // root as parentId is null

        List<Node> nodes = new ArrayList<>();
        nodes.add(node1);
        nodes.add(node2);
        nodes.add(node3);
        nodes.add(node4);
        nodes.add(node5);

        //convert to a tree
        createTree(nodes);
    }
    
    private static void createTree(List<Node> nodes) {
        System.err.println("開始");
        Map<Integer, Node> mapTmp = new HashMap<>(nodes.size());
        // put all node to map
        for (Node node : nodes) {
            mapTmp.put(node.getId(), node);
        }

        //loop and assign parent/child relationships
        for (Node node : nodes) {
            Integer parentId = node.getParentId();
            if (parentId == null) {
                continue;
            }
            Node parentNode = mapTmp.get(parentId);
            if (parentNode == null) {
                continue;
            }
            List<Node> children = parentNode.getChildren();
            if (children == null) {
                children = new ArrayList<>();
            }
            children.add(node);
            parentNode.setChildren(children);
            mapTmp.put(parentId, parentNode);
        }

        //extract root node
        List<Node> trees = new ArrayList<>();
        for (Node node :mapTmp.values()) {
            if (node.getParentId() == null) {
                trees.add(node);
            }
        }

        System.err.println(trees);
        System.err.println("結束");
    }
}
           

2，原了解析

map中儲存的value為對象的指針，而對象儲存在堆記憶體中；當給該對象的children指派的時候，也是将`children對象`的指針指派給目前對象；是以程式中看似是對單個對象進行操作，實際上對象本身的結構已經發生了較大的改變。

是以實際原理就是通過記憶體和指針的運用來實作樹結構的組裝。

另一方面HashMap的hash算法的使用是比循環要節省性能和時間的；