背景：在平時的開發中，我們時常會遇到下列場景

1. 公司的組織架構的資料儲存與展示
2. 資料夾層級的資料儲存與展示
3. 評論系統中，父評論與諸多子評論的資料儲存與展示
4. ......

對於這種有層級的結構化資料，就像是一棵樹一樣。在關係型資料庫中，通常將一個個的節點資訊儲存到表中，通過一個欄位（例如，pid），指向其父節點。而在資料展示的時候，我們又希望它是呈現層級的，例如：

id  name        pid
1   總公司       -1
2   上海分公司    1
3   浙江分公司    1
4   閔行區分公司  2
5   嘉興分公司    3

{
    "id": 1,
    "name": "總公司",
    "pid": -1,
    "branch":
    [
        {
            "id": 2,
            "name": "上海分公司",
            "pid": 1,
            "branch":
            [
                {
                    "id": 4,
                    "name": "閔行區分公司",
                    "pid": 2,
                    "branch":
                    []
                }
            ]
        },
        {
            "id": 3,
            "name": "浙江分公司",
            "pid": 1,
            "branch":
            [
                {
                    "id": 5,
                    "name": "嘉興分公司",
                    "pid": 3,
                    "branch":
                    []
                }
            ]
        }
    ]
}

所以，本文的主要內容就是提供幾種方案，實現這兩類資料的轉換方式。

內容導覽

儲存樹的表結構

如何在一張資料庫表中表示一顆樹結構中的所有節點資訊，這裡有一個範例：

DROP TABLE IF EXISTS zj_city;
CREATE TABLE zj_city (
    id BIGINT NOT NULL AUTO_INCREMENT,
    name VARCHAR(50) COMMENT '節點名稱',
    pid int NOT NULL COMMENT '父節點',

    create_time DATETIME DEFAULT now() COMMENT '建立時間: 年-月-日 時:分:秒',
    update_time DATETIME DEFAULT now() ON UPDATE now() COMMENT '更新時間',
    is_deleted BIT DEFAULT 0 COMMENT '是否刪除：0-false-未刪除;1-true-已刪除',
    PRIMARY KEY (id)
)COMMENT '浙江城市';

INSERT INTO zj_city(name, pid) VALUES
('浙江省',0),
('金華市',1),
('嘉興市',1),
('杭州市',1),
('寧波市',1);

INSERT INTO zj_city(name, pid) VALUES
('下城區',4),
('錢塘區',4),
('西湖區',4),
('上城區',4);

INSERT INTO zj_city(name, pid) VALUES
('南湖區',3),
('秀洲區',3),
('桐鄉市',3),
('平湖市',3),
('海寧市',3);

INSERT INTO zj_city(name, pid) VALUES
('梧桐街道',12),
('鳳鳴街道',12),
('龍翔街道',12),
('崇福鎮',12),
('烏鎮鎮',12),
('高橋鎮',12),
('河山鎮',12),
('濮院鎮',12);

SELECT * from zj_city;

扁平List轉樹形List

應用場景

• 公司組織結構
• 省市級
• 評論系統中，父評論與諸多子評論
• 其他層級展示的資料

雙層for

主要思想：外層迴圈-找父節點；內層迴圈-找子節點；因為每個元素都會找一遍，所有最終得到完整的樹

import com.alibaba.fastjson.JSON;
import com.ks.boot.entity.CityEntity;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class TreeListDemo {
    List<CityEntity> cityEntities;
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉興   1
     * 4   南湖   3
     * 5   桐鄉   3
     * 6   餘杭   2
     * 7   西湖   2
     * 8   雲南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    @BeforeEach
    public void init() {
        cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1},\n" +
                "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                "{\"id\":5,\"name\":\"桐鄉\",\"pid\":3},\n" +
                "{\"id\":6,\"name\":\"餘杭\",\"pid\":2},\n" +
                "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0},\n" +
                "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
    }

    @Test
    public void testList2Tree() {
        List<CityEntity> resultTree = list2Tree(this.cityEntities);
        System.out.println(JSON.toJSONString(resultTree));
    }

    /**
     * 雙層for，List轉Tree
     * 主要思想：外層迴圈-找父節點；內層迴圈-找子節點；因為每個元素都會找一遍，所有最終得到完整的樹
     * 時間複雜度：N^2；空間複雜度：N
     */
    public List<CityEntity> list2Tree(List<CityEntity> cityEntities) {
        List<CityEntity> resultCities = new ArrayList<>();
        for (CityEntity city : cityEntities) {
            if(0 == city.getPid()) { //根節點、頂級節點，直接放入最終返回結果的List
                resultCities.add(city);
            }
            for (CityEntity curCity : cityEntities) { //根據當前city找它的子節點
                if(city.getId().equals(curCity.getPid())) {
                    if(city.getSubCityList() == null) { //還沒有任何子節點，new一個空的放進去
                        city.setSubCityList(new ArrayList<>());
                    }
                    city.getSubCityList().add(curCity);
                }
            }
        }

        return resultCities;
    }
}

public class CityEntity {
    private Long id;
    private String name;
    private Long pid;

    private List<CityEntity> subCityList;

    getter/setter
}

遞迴

主要思想：獲取所有根節點、頂級節點，再從List中查詢根節點的子節點；

import com.alibaba.fastjson.JSON;
import com.ks.boot.entity.CityEntity;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class TreeListDemo {
    List<CityEntity> cityEntities;
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉興   1
     * 4   南湖   3
     * 5   桐鄉   3
     * 6   餘杭   2
     * 7   西湖   2
     * 8   雲南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    @BeforeEach
    public void init() {
        cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1},\n" +
                "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                "{\"id\":5,\"name\":\"桐鄉\",\"pid\":3},\n" +
                "{\"id\":6,\"name\":\"餘杭\",\"pid\":2},\n" +
                "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0},\n" +
                "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
    }

    /**
     * 遞迴，List轉Tree
     * 主要思想：獲取所有根節點、頂級節點，再從List中查詢根節點的子節點；
     * 時間複雜度：N*(1+N)/2，O(N^2)，因為遞迴方法中，最好是List的第一元素就是要找的子節點，最壞是
     * List的最後一個元素是子節點
     */
    @Test
    public void testList2Tree() {
        List<CityEntity> resultCities = new ArrayList<>();
        for (CityEntity city : cityEntities) {
            if(0 == city.getPid()) { //獲取所有根節點、頂級節點，再根據根節點進行遞迴
                CityEntity topCity = findChild(cityEntities, city); //此時的topCity已經包含它的所有子節點
                resultCities.add(topCity);
            }
        }

        System.out.println(JSON.toJSONString(resultCities));
    }

    /**
     *
     * @param cityEntities 在那個裡面找
     * @param curCity 找誰的子節點
     * @return curCity的子節點
     */
    public CityEntity findChild(List<CityEntity> cityEntities, CityEntity curCity) {
        for (CityEntity city : cityEntities) {
            if(curCity.getId().equals(city.getPid())) {
                if(null == curCity.getSubCityList()) {
                    curCity.setSubCityList(new ArrayList<>());
                }
                CityEntity subChild = findChild(cityEntities, city); //每次遞迴，都從頭開始查詢有沒有city的子節點
                curCity.getSubCityList().add(subChild);
            }
        }
        return curCity;
    }

}

public class CityEntity {
    private Long id;
    private String name;
    private Long pid;

    private List<CityEntity> subCityList;

    getter/setter
}

轉換為Map

主要思想：

• 在雙層for的解法中，由於內層for也需要遍歷以便List，造成時間複雜度上身為平方級
• 如果內層for不需要遍歷完整的List，而是事先預處理到Map中，尋找時直接從Map中獲取，則時間複雜度降為LogN

import com.alibaba.fastjson2.JSON;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class TreeListDemo {
    List<CityEntity> cityEntities;
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉興   1
     * 4   南湖   3
     * 5   桐鄉   3
     * 6   餘杭   2
     * 7   西湖   2
     * 8   雲南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    @BeforeEach
    public void init() {
        cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1},\n" +
                "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                "{\"id\":5,\"name\":\"桐鄉\",\"pid\":3},\n" +
                "{\"id\":6,\"name\":\"餘杭\",\"pid\":2},\n" +
                "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0},\n" +
                "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
    }

    /**
     * 在雙層for的解法中，由於內層for也需要遍歷以便List，造成時間複雜度上身為平方級
     * 如果內層for不需要遍歷完整的List，而是事先預處理到Map中，尋找時直接從Map中獲取，則時間複雜度降為LogN
     */
    @Test
    public void list2tree() {
        //收集每個PID下的節點為Map
        Map<Long, List<CityEntity>> cityMapByPid = cityEntities.stream().collect(Collectors.groupingBy(CityEntity::getPid));

        List<CityEntity> resultCityList = new ArrayList<>();
        for (CityEntity city : cityEntities) {
            if(0 == city.getPid()) { //根節點、頂點
                resultCityList.add(city);
            }

            List<CityEntity> citiesByPid = cityMapByPid.get(city.getId());
            if(null != citiesByPid && citiesByPid.size() > 0) { //有子節點
                if(null == city.getSubCityList()) {
                    city.setSubCityList(new ArrayList<>());
                }
                city.getSubCityList().addAll(citiesByPid); //塞入
            }
        }

        System.out.println(JSON.toJSONString(resultCityList));
    }

    /**
     * 簡化寫法：在收集到Map時，對於沒有子節點的節點，建立一個空的塞入到Map中
     */
    @Test
    public void list2tree4Simple() {
        List<CityEntity> resultCityList = new ArrayList<>();

        //儲存每個PID下的子節點
        Map<Long, List<CityEntity>> cityMapByPid = new HashMap<>();
        for (CityEntity city : cityEntities) { //收集每個PID下的子節點
            //獲取當前PID對應的子節點List，如果沒有則建立一個空的List塞入
            //這個設計得很巧妙
            List<CityEntity> children = cityMapByPid.getOrDefault(city.getPid(), new ArrayList<>());
            children.add(city); //插入當前元素
            cityMapByPid.put(city.getPid(), children);
        }

        for (CityEntity city : cityEntities) {
            if(0 == city.getPid()) { //根節點、頂點
                resultCityList.add(city);
            }
            city.setSubCityList(cityMapByPid.get(city.getId()));
        }

        System.out.println(JSON.toJSONString(resultCityList));
    }
}

棧

主要思想

• 收集根節點、頂級節點，存入resultList，並且壓棧
• 迴圈出棧，棧元素Cur
  • 找Cur的所有子元素為child
  • 如果child不為空，則再壓入棧中。這一步的目的是，再一次找child的子元素

import com.alibaba.fastjson2.JSON;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

public class TreeListDemo {
    List<CityEntity> cityEntities;
    /**
     * id  name  pid
     * 1   浙江   0
     * 2   杭州   1
     * 3   嘉興   1
     * 4   南湖   3
     * 5   桐鄉   3
     * 6   餘杭   2
     * 7   西湖   2
     * 8   雲南   0
     * 9   昆明   8
     * 10  昭通   8
     */
    @BeforeEach
    public void init() {
        cityEntities = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0},\n" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1},\n" +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1},\n" +
                "{\"id\":4,\"name\":\"南湖\",\"pid\":3},\n" +
                "{\"id\":5,\"name\":\"桐鄉\",\"pid\":3},\n" +
                "{\"id\":6,\"name\":\"餘杭\",\"pid\":2},\n" +
                "{\"id\":7,\"name\":\"西湖\",\"pid\":2},\n" +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0},\n" +
                "{\"id\":9,\"name\":\"昆明\",\"pid\":8},\n" +
                "{\"id\":10,\"name\":\"昭通\",\"pid\":8}]", CityEntity.class);
    }

    /**
     * 主要思想：
     *  收集根節點、頂級節點，存入resultList，並且壓棧
     *  迴圈出棧，棧元素Cur
     *      找Cur的所有子元素為child
     *      如果child不為空，則再壓入棧中。這一步的目的是，再一次找child的子元素
     * 時間複雜度：N(過濾出所有跟節點) + 常數(出棧) * N(遍歷List找當前節點的子元素)
     */
    @Test
    public void list2tree() {
        List<CityEntity> resultCityList = new ArrayList<>();

        Stack<CityEntity> stack = new Stack<>();
        resultCityList = cityEntities.stream().filter(ele -> 0 == ele.getPid()).collect(Collectors.toList());
        stack.addAll(resultCityList); //根節點、頂點入棧

        while(!stack.isEmpty()) {
            CityEntity curCity = stack.pop();
            List<CityEntity> child = cityEntities.stream().filter(ele -> curCity.getId().equals(ele.getPid())).collect(Collectors.toList());
            if(!child.isEmpty()) { //這一步處理的原因是：當沒有子元素，不顯示該個欄位。流處理後沒有元素只會返回空List，不會返回null
                curCity.setSubCityList(child);
            }
            if(!child.isEmpty()) {
                stack.addAll(child);
            }
        }

        System.out.println(JSON.toJSONString(resultCityList));
    }
}

樹形List轉扁平List

遞迴

主要思想：遍歷樹節點，一個樹節點如果有子樹，則再次遞迴此子樹，直到沒有子樹為止

import com.alibaba.fastjson2.JSON;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * id  name  pid
 * 1   浙江   0
 * 2   杭州   1
 * 3   嘉興   1
 * 4   南湖   3
 * 5   桐鄉   3
 * 6   餘杭   2
 * 7   西湖   2
 * 8   雲南   0
 * 9   昆明   8
 * 10  昭通   8
 */
public class ListTreeDemo {
    List<CityEntity> treeList;

    @BeforeEach
    public void init() {
        treeList = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0,\"subCityList\":[" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1,\"subCityList\":[{\"id\":6,\"name\":\"餘杭\",\"pid\":2},{\"id\":7,\"name\":\"西湖\",\"pid\":2}]}," +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1,\"subCityList\":[{\"id\":4,\"name\":\"南湖\",\"pid\":3},{\"id\":5,\"name\":\"桐鄉\",\"pid\":3}]}]}," +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0,\"subCityList\":[{\"id\":9,\"name\":\"昆明\",\"pid\":8},{\"id\":10,\"name\":\"昭通\",\"pid\":8}]}]", CityEntity.class);
    }

    @Test
    public void tree2list() {
        List<CityEntity> resList = new ArrayList<>();

        //這一層for的目的是：遍歷根節點
        for (CityEntity city : treeList) {
            reversion(city,resList);
        }
        System.out.println(JSON.toJSONString(resList));
    }
    public void reversion(CityEntity curNode, List<CityEntity> resList) {
        resList.add(beanCopy(curNode));

        List<CityEntity> subCityList = curNode.getSubCityList();
        if(subCityList != null && !subCityList.isEmpty()) {
            for (CityEntity city : subCityList) { //遞迴尋找子節點的子節點們
                reversion(city, resList);
            }
        }
        
        //遞迴的出口就是subCityList為null或者empty
    }

    private CityEntity beanCopy(CityEntity source) {
        CityEntity res = new CityEntity();
        res.setId(source.getId());
        res.setName(source.getName());
        res.setPid(source.getPid());
        return res;
    }
}

棧

主要思想

1. 依次遍歷樹形List，當前節點為Cur
   1. 將Cur收集到某個儲存結果的List
   2. 如果Cur有子樹，壓入某個棧中
2. 依次彈出棧元素，當前彈出的元素為StackSubTree
   1. 如果StackSubTree還有子樹，繼續壓棧
   2. 如果StackSubTree沒有子樹，則放入結果List

import com.alibaba.fastjson2.JSON;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

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

/**
 * id  name  pid
 * 1   浙江   0
 * 2   杭州   1
 * 3   嘉興   1
 * 4   南湖   3
 * 5   桐鄉   3
 * 6   餘杭   2
 * 7   西湖   2
 * 8   雲南   0
 * 9   昆明   8
 * 10  昭通   8
 */
public class ListTreeDemo {
    List<CityEntity> treeList;

    @BeforeEach
    public void init() {
        treeList = JSON.parseArray("[{\"id\":1,\"name\":\"浙江\",\"pid\":0,\"subCityList\":[" +
                "{\"id\":2,\"name\":\"杭州\",\"pid\":1,\"subCityList\":[{\"id\":6,\"name\":\"餘杭\",\"pid\":2},{\"id\":7,\"name\":\"西湖\",\"pid\":2}]}," +
                "{\"id\":3,\"name\":\"嘉興\",\"pid\":1,\"subCityList\":[{\"id\":4,\"name\":\"南湖\",\"pid\":3},{\"id\":5,\"name\":\"桐鄉\",\"pid\":3}]}]}," +
                "{\"id\":8,\"name\":\"雲南\",\"pid\":0,\"subCityList\":[{\"id\":9,\"name\":\"昆明\",\"pid\":8},{\"id\":10,\"name\":\"昭通\",\"pid\":8}]}]", CityEntity.class);
    }

    /**
     * 1. 依次遍歷樹形List，當前節點為Cur
     *   a) 將Cur收集到某個儲存結果的List
     *   b) 如果Cur有子樹，壓入某個棧中
     * 2. 依次彈出棧元素，當前彈出的元素為StackSubTree
     *   a) 如果StackSubTree還有子樹，繼續壓棧
     *   b) 如果StackSubTree沒有子樹，則放入結果List
     */
    @Test
    public void tree2list() {
        List<CityEntity> resList = new ArrayList<>();

        Stack<List<CityEntity>> stack = new Stack<>();

        for (CityEntity curCity : treeList) {
            resList.add(beanCopy(curCity));
            if (curCity.getSubCityList() != null && !curCity.getSubCityList().isEmpty()) {
                stack.push(curCity.getSubCityList());
            }
        }

        while (!stack.isEmpty()) {
            List<CityEntity> subTree = stack.pop();
            for (CityEntity city : subTree) {
                if (city.getSubCityList() != null && !city.getSubCityList().isEmpty()) {
                    stack.push(city.getSubCityList());
                } else {
                    resList.add(beanCopy(city));
                }
            }
        }

        System.out.println(JSON.toJSONString(resList));
    }

    private CityEntity beanCopy(CityEntity source) {
        CityEntity res = new CityEntity();
        res.setId(source.getId());
        res.setName(source.getName());
        res.setPid(source.getPid());
        return res;
    }
}