大家好，我是一航；
不管你是做前端還是後端的開發，那我相信樹形結構的需求一定有遇到過，特别是管理平台類型的項目，一般都會有一個樹形結構的菜單欄，再比如說，公司組織架構，層級關系、歸屬關系等等需求，本質上都是樹形結構的一種展現；
遇到這種需求，最常見也最容易想到的設計思路就是：父子關系的方式，子項通過一個字段來儲存他的父ID，然後通過遞歸的方式得到層級關系；
前幾天，技術交流群裡面有小夥伴在問，實際的業務中，樹形結構的資料太多、層級還深，查詢過程一頓遞歸之後，性能表現的比較差，問有沒有什麼好的設計思路，讓查詢、統計更加的便捷高效；
今天就給大家介紹一種新的樹形結構設計方案：改進後的先序樹方式，在查詢、統計方面的優勢，要遠大于父子關系的遞歸設計方案；
本文就來詳細的講解并對比一下兩個方案的實作方式以及優缺點。
文章目錄：
對于樹形結構的需求，不管是采用什麼方式，要處理的問題都是差不多的，下面先列舉一下樹形結構常見的問題點那些：
- 節點的增删改
- 是否存在子節點（葉子節點）
- 查詢出所有的子節點
- 查詢所有的孫節點
- 查詢所有的子孫節點
- 父節點查詢
- 祖先節點查詢
- 統計所有子孫部門的數量
針對上面的這些問題，就以一個簡單的公司組織架構示例，一起來看看，兩種方案都是如何實作和解決的？
本文所有的示例都是采用的MySQL+Java實作，核心思路都類似，實際使用，可根據語言特性以及自己習慣的方式調整即可。
1父子關系方案
父子關系，顧名思義，就是目前節點隻關注自己的父節點是誰，并将其儲存起來即可，查詢我的子節點有那些，隻需要全局找到所有父ID是和我的ID一緻的項；
如下圖所示：
方案特點
- 優點
- 方案簡單易懂
- 資料結構簡單清晰
- 層級直覺、鮮明
-
易維護
層級關系隻需要關注自己的父ID，是以在添加、修改的時候，一旦關系發生變化，調整對應的父ID即可。
- 缺點
-
查找麻煩、統計麻煩
根據目前節點的資料，隻能擷取到子節點的資料，一旦查詢、統計超出父子範圍，就隻能通過遞歸逐層查找了；
-
示例
根據上面的圖示示例，與其對應的表結構如下：
| ID | dep_name(部門名稱) | level(層級) | parent_id(父ID) |
|---|---|---|---|
| 1 | 董事會 | 1 | |
| 2 | 總經理 | 2 | 1 |
| 3 | 董事會秘書 | 2 | 1 |
| 4 | 産品部 | 3 | 2 |
| 5 | 行政總監 | 3 | 2 |
| 6 | 設計部 | 4 | 4 |
| 7 | 技術部 | 4 | 4 |
| 8 | 财務部 | 4 | 5 |
| 9 | 行政部 | 4 | 5 |
| 10 | 用戶端 | 5 | 7 |
| 11 | 服務端 | 5 | 7 |
SQL腳本：
DROP TABLE IF EXISTS `department_info`;
CREATE TABLE `department_info` (
`id` int(11) NOT NULL,
`dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NULL DEFAULT NULL COMMENT '名稱',
`level` int(11) NULL DEFAULT NULL,
`parent_id` int(11) NULL DEFAULT NULL COMMENT '父ID',
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;
INSERT INTO `department_info` VALUES (1, '董事會', 1, 0);
INSERT INTO `department_info` VALUES (2, '總經理', 2, 1);
INSERT INTO `department_info` VALUES (3, '董事會秘書', 2, 1);
INSERT INTO `department_info` VALUES (4, '産品部', 3, 2);
INSERT INTO `department_info` VALUES (5, '行政總監', 3, 2);
INSERT INTO `department_info` VALUES (6, '設計部', 4, 4);
INSERT INTO `department_info` VALUES (7, '技術部', 4, 4);
INSERT INTO `department_info` VALUES (8, '财務部', 4, 5);
INSERT INTO `department_info` VALUES (9, '行政部', 4, 5);
INSERT INTO `department_info` VALUES (10, '用戶端', 5, 7);
INSERT INTO `department_info` VALUES (11, '服務端', 5, 7);
複制
函數的建立
由于父子節點的查詢，需要依賴遞歸，為了查詢友善，這裡建立兩個函數：
遞歸查詢子孫節點ID的函數
DROP FUNCTION IF EXISTS queryChildrenDepInfo;
DELIMITER ;;
CREATE FUNCTION queryChildrenDepInfo(dep_id INT)
RETURNS VARCHAR(4000)
BEGIN
DECLARE sTemp VARCHAR(4000);
DECLARE sTempChd VARCHAR(4000);
SET sTemp='$';
SET sTempChd = CAST(dep_id AS CHAR);
WHILE sTempChd IS NOT NULL DO
SET sTemp= CONCAT(sTemp,',',sTempChd);
SELECT GROUP_CONCAT(id) INTO sTempChd FROM department_info WHERE FIND_IN_SET(parent_id,sTempChd)>0;
END WHILE;
RETURN sTemp;
END
;;
DELIMITER ;
複制
測試：查詢技術部下的所有孫節點？
SELECT queryChildrenDepInfo(4);
複制
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(4));
複制
遞歸查詢祖先節點ID的函數
DROP FUNCTION IF EXISTS queryParentDepInfo;
DELIMITER;;
CREATE FUNCTION queryParentDepInfo(dep_id INT)
RETURNS VARCHAR(4000)
BEGIN
DECLARE sTemp VARCHAR(4000);
DECLARE sTempChd VARCHAR(4000);
SET sTemp='$';
SET sTempChd = CAST(dep_id AS CHAR);
SET sTemp = CONCAT(sTemp,',',sTempChd);
SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;
WHILE sTempChd <> 0 DO
SET sTemp = CONCAT(sTemp,',',sTempChd);
SELECT parent_id INTO sTempChd FROM department_info WHERE id = sTempChd;
END WHILE;
RETURN sTemp;
END
;;
DELIMITER ;
複制
測試：查詢技術部所有的祖先節點？
SELECT queryParentDepInfo(7);
複制
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(7));
複制
節點的增删改
增加節點
比如要在技術部下添加一個測試部門
INSERT INTO department_info(`id`, `dep_name`, `level`, `parent_id`) VALUES (12, '測試部', 5, 7);
複制
修改節點
比如：将測試部（ID = 12）提出來，放到産品部（ID = 4）下；就隻需要将測試部對應的父節點ID修改為4即可
SET @id = 12;
SET @pid = 4;
UPDATE department_info SET `parent_id` = @pid WHERE `id` = @id;
複制
删除節點
删除相比于添加修改，情況就會特殊一些，如果删除的節點存在子節點，意味着子節點也需要同步删除掉；
是以這裡就需要用到上面建立的遞歸查詢子孫節點ID的函數（queryChildrenDepInfo）
比如：删除技術部門；
DELETE FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(7));
複制
是否存在子節點（葉子節點）
在該方案下，要想判斷是否是葉子節點，有兩種實作方式：
統計目前節點以及子孫節點的數量
遞歸查詢所有子節點的ID，并統計數量，由于函數查詢包含了節點自身，是以這裡使用了
COUNT(*)-1
來計算子節點的數量，如果等于0就是葉子節點，大于0說明不是葉子節點；
-- 檢視設計部（ID=6）是不是葉子節點
SET @id = 6;
-- 由于數量包含了自身，由于統計的是子節點的數量，是以這裡需要-1将自己去掉
SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));
複制
添加葉子節點的标記
在表中添加一個isLeaf字段，當節點增删改操作的時候，用這個字段來标記一下目前是否是葉子節點
查詢出所有的下級部門（子節點）
查詢所有的下級部門，此時就需要借助目前節點的id和level字段
例：查詢産品部（id = 4，level = 3）的子節點
SET @id = 4;
SET @lv = 3;
SELECT * from department_info where parent_id = @id AND `level` = @lv + 1;
複制
查詢所有的下下級部門（孫節點）
實際業務場景下，這種需求很少，這裡主要用來示範可操作性，不排除特殊的場合下用的上；
查詢孫節點相比與子節點就麻煩很多了，因為目前節點和孫節點是沒有任何資料上的關聯，是以需要借助子節點才能找到孫節點，是以這裡又必須得用上遞歸查詢子孫節點ID的函數了；
例：查詢産品部（id = 4，level = 3）的孫節點
-- 查詢孫節點
SET @id = 4;
SET @lv = 3;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id)) AND `level` = @lv + 2;
複制
查詢所有的下屬部門
查詢下屬部門就和查詢下下級部門（孫節點）類似，隻是不用校驗層級即可；
例：查詢産品部下所有的下屬部門？
SET @id = 4;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));
複制
查詢隸屬部門
也就是查詢父節點；在該方案下，節點中已經儲存了父節點的ID，通過ID就能直接擷取到父節點
查詢所有上級部門
由于目前節點隻儲存了父級節點ID，更上一級的資訊隻能通過遞歸逐級擷取；
例：查詢技術部（id = 7）的所有上級部門；
SET @id = 7;
SELECT * FROM department_info WHERE FIND_IN_SET(id,queryParentDepInfo(@id));
複制
統計所有下屬部門的數量
和查詢是否是葉子節點方式一樣，隻是對得到的資料解讀的方式不同而已；
例：統計技術部的下屬部門數量？
SET @id = 7;
SELECT COUNT(*)-1 FROM department_info WHERE FIND_IN_SET(id,queryChildrenDepInfo(@id));
複制
2改進後的先序樹方案
上述的父子關系方案可以看出，大部分的操作，都需要遞歸查詢出所有的子孫節點後才行，如果出現文章開始說的，層級多，深度深的話，遞歸的過程，就會大大影響查詢、統計的性能；
下面就來介紹一下改進後的先序樹的樹形結構方案，節點不再儲存父節點的ID，而是為每個節點增加左值和右值：
如下圖示：
對應的表資料如下：
| id | dep_name(部門名稱) | lt(左值) | rt(右值) | lv(層級) |
|---|---|---|---|---|
| 1 | 董事會 | 1 | 22 | 1 |
| 2 | 總經理 | 2 | 19 | 2 |
| 3 | 董事會秘書 | 20 | 21 | 2 |
| 4 | 産品部 | 3 | 12 | 3 |
| 5 | 行政總監 | 13 | 18 | 3 |
| 6 | 設計部 | 4 | 5 | 4 |
| 7 | 技術部 | 6 | 11 | 4 |
| 8 | 财務部 | 14 | 15 | 4 |
| 9 | 行政部 | 16 | 17 | 4 |
| 10 | 用戶端 | 7 | 8 | 5 |
| 11 | 服務端 | 9 | 10 | 5 |
SQL語句：
DROP TABLE IF EXISTS `department_info2`;
CREATE TABLE `department_info2` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`dep_name` varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci NOT NULL COMMENT '名稱',
`lt` int(11) NOT NULL COMMENT '節點左數',
`rt` int(11) NOT NULL COMMENT '節點右數',
`lv` int(11) NOT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 12 CHARACTER SET = utf8mb4 COLLATE = utf8mb4_general_ci ROW_FORMAT = Dynamic;
INSERT INTO `department_info2` VALUES (1, '董事會', 1, 22, 1);
INSERT INTO `department_info2` VALUES (2, '總經理', 2, 19, 2);
INSERT INTO `department_info2` VALUES (3, '董事會秘書', 20, 21, 2);
INSERT INTO `department_info2` VALUES (4, '産品部', 3, 12, 3);
INSERT INTO `department_info2` VALUES (5, '行政總監', 13, 18, 3);
INSERT INTO `department_info2` VALUES (6, '設計部', 4, 5, 4);
INSERT INTO `department_info2` VALUES (7, '技術部', 6, 11, 4);
INSERT INTO `department_info2` VALUES (8, '财務部', 14, 15, 4);
INSERT INTO `department_info2` VALUES (9, '行政部', 16, 17, 4);
INSERT INTO `department_info2` VALUES (10, '用戶端', 7, 8, 5);
INSERT INTO `department_info2` VALUES (11, '服務端', 9, 10, 5);
複制
方案特點
- 優點
- 查詢彙總簡單高效
- 無需遞歸查詢，性能高
- 缺點
- 結構相對複雜，資料層面了解難度較高
-
不易維護
以為左右值的存在，會直接影響到後續的節點，是以，目前節點增删改時，都會對後續的節點産業影響；
示例
節點的增删改
新增
如下圖：在技術部下新增一個測試部，新增節點對應的左右值分别為11、12；
過程分析：
第一步，所有比11（新增節點的左數）大的左數全部+2（紫色部分）
第二步，所有比12（新增節點的右數）大的右數全部+2（橙色部分）
第三步，添加左右數分别為11、12的部門節點
由于這裡涉及到多個步驟，我們需要保證資料庫操作的原子性，是以需要做事務操作，這裡為了友善，建立一個存儲過程；存儲過程并不式必須的，同樣也可以以代碼的形式來保證事務操作；隻是使用存儲過程，可靠性會高一些；
添加節點存儲過程：
DROP PROCEDURE IF EXISTS insertDepartment;
CREATE PROCEDURE insertDepartment(IN lt_i INT,IN rt_i INT,IN lv_i INT,IN dn VARCHAR(256))
BEGIN
DECLARE d_error INTEGER DEFAULT 0;
DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設定為1
DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條資料則置為2
START TRANSACTION;
-- 将所有左值大于新增左值的部門全部+2
UPDATE department_info2 SET lt=lt+2 WHERE lt > lt_i;
-- 将所有右值大于新增右值的部門全部+2
UPDATE department_info2 SET rt=rt+2 WHERE rt >= lt_i;
-- 新增部門
INSERT INTO department_info2(dep_name,lt,rt,lv) VALUES(dn,lt_i,rt_i,lv_i);
SET d_error= ROW_COUNT();
IF d_error != 1 THEN
ROLLBACK;-- 結果不等于1 的時候，說明新增失敗，復原操作
ELSE
COMMIT; -- 等于1的時候，說明添加成功，送出
END IF;
select d_error;
END
複制
輸入參數
lt_i ：新增部門的左值
rt_i：新增部門的右值
lv_i：行政部門的層級
dn：部門名稱
如上圖的示例，就可以調用新增的存儲過程添加：
call insertDepartment(11, 12, 5,"測試部");
複制
修改
普通的節點資訊修改，這裡就不多多說了，很簡單；
節點移動是此方案下，最複雜的修改操作，因為整個過程涉及到位置的變化，層級的變化等多個次元的調整，而且還得保證事務操作；
例：我們要将技術部（id = 4）交由總經理（id = 2）直接負責，也就是移動到總經理之下；
過程分析：
第一步，計算技術部的左右數內插補點
第二步，計算與移動後的上級節點之間的內插補點
第三步，确定是左移還是右移
第四步，将本節點與目标節點之間的內插補點減去（左移）/加上（右移）
第五步，将移動的節點以及子孫的節點與父節點之間的內插補點減去（左移）/加上（右移）
第六步，調整層級
整個過程如下圖所示，稍微有點點複雜，可以結合圖示以及存儲過程的代碼，仔細的了解一下：
為了友善操作，避免出錯，這裡同樣以存儲過程的方式來實作核心邏輯，降低出錯風險：
DROP PROCEDURE IF EXISTS moveDepartment;
CREATE PROCEDURE moveDepartment(IN fid INT,IN tid INT)
BEGIN
DECLARE d_error INTEGER DEFAULT 0;
DECLARE num INTEGER DEFAULT 0; -- 删除節點左右值之間的內插補點
DECLARE mnum INTEGER DEFAULT 0; -- 移動階段與上級節點之間的內插補點
DECLARE ids VARCHAR(1000); -- 儲存所有正在移動的id集合，保證多個節點移動時也能正常
DECLARE blt INT; -- 需要移動節點的左數
DECLARE brt INT; -- 需要移動節點的右數
DECLARE blv INT; -- 需要移動節點的層級
DECLARE tlt INT; -- 目标節點的左數
DECLARE trt INT; -- 目标節點的右數
DECLARE tlv INT; -- 目标節點的層級
DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設定為1
DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條資料則置為2
START TRANSACTION;
-- 查詢待移動的節點的左右數以及層級
SELECT lt,rt,lv INTO blt, brt,blv FROM department_info2 WHERE id = fid;
-- 查詢目标節點的左右數以及層級
SELECT lt,rt,lv INTO tlt, trt,tlv FROM department_info2 WHERE id = tid;
-- 查詢所有要一定的節點，目前節點以及其子孫節點
SELECT GROUP_CONCAT(id) INTO ids FROM department_info2 WHERE lt>=blt AND rt <=brt;
IF tlt > blt AND trt < brt THEN
-- 将自己移動到自己的下屬節點 暫時不允許 如果要如此操作，需要将下級調整為平級 再移動
SET d_error = -4;
ELSEIF blt > tlt AND brt < trt AND blv = tlv + 1 THEN
-- 說明本身就已經是目标節點在子節點了，不需要處理，直接成功
SET d_error = 0;
ELSE
-- 計算移動節點與上級節點之間的內插補點
SET mnum = trt - brt -1;
-- 計算目前節點及其子節點的內插補點
SET num = brt - blt + 1;
-- 首先将移動前的節點整個元素表中移除掉
IF trt > brt THEN
-- 左往右移動
UPDATE department_info2 SET lt=lt-num WHERE lt > brt AND lt < trt;
UPDATE department_info2 SET rt=rt-num WHERE rt > brt AND rt < trt;
ELSE
-- 從右往左移動 将系數全部變為負值，-負數就等于+正數
SET mnum = -mnum;
SET num = -num;
UPDATE department_info2 SET lt=lt-num WHERE lt >= trt AND lt < blt;
UPDATE department_info2 SET rt=rt-num WHERE rt >= trt AND rt < blt;
END IF;
-- 調整移動的節點以及下屬節點
UPDATE department_info2 SET lt=lt+mnum,rt=rt+mnum,lv = lv - (blv - tlv -1) WHERE FIND_IN_SET(id,ids);
SET d_error= ROW_COUNT();
IF d_error <= 0 THEN
ROLLBACK;
ELSE
COMMIT;
END IF;
END IF;
select d_error;
END
複制
輸入參數
fid：移動的節點id
tid：目标節點id
測試：
CALL moveDepartment(7,2)
複制
删除
删除的過程正好與新增相反，在删除節點及其自己點的時候，大于删除節點的所有左右值都需要減去删除節點的左右內插補點+1；
如下圖示例：删除技術部
過程：
第一步，計算出删除節點的左右內插補點+1；技術部的左右值分别時6和11，內插補點+1：11 - 6 + 1
第二步，删除節點機器所有子節點
第三步，所有大于删除節點左右值的節點，全部減去內插補點
同樣為了友善操作，我們也建立一個存儲過程：
DROP PROCEDURE IF EXISTS removeDepartment;
CREATE PROCEDURE removeDepartment(IN did INT)
BEGIN
DECLARE d_error INTEGER DEFAULT 0;
DECLARE num INTEGER DEFAULT 0; -- 删除節點左右值之間的內插補點
DECLARE dlt INT; -- 删除節點的左值
DECLARE drt INT; -- 删除節點的右值值
DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET d_error= -2;-- 異常時設定為1
DECLARE CONTINUE HANDLER FOR NOT FOUND SET d_error = -3; -- 如果表中沒有下一條資料則置為2
START TRANSACTION;
-- 查詢删除節點的左右值
SELECT lt,rt INTO dlt, drt FROM department_info2 WHERE id = did;
-- 計算目前節點及其子節點的內插補點
SET num = drt - dlt + 1;
-- 删除目前節點及其子節點
DELETE FROM department_info2 WHERE lt>=dlt AND rt<=drt;
SET d_error= ROW_COUNT();
-- 左右值減少對應的插值
UPDATE department_info2 SET lt=lt-num WHERE lt > dlt;
UPDATE department_info2 SET rt=rt-num WHERE rt > drt;
IF d_error != num/2 THEN -- 判斷删除的數量與目前節點+子孫節點的數量是否一緻；不一緻的話，直接復原
ROLLBACK;
ELSE
COMMIT;
END IF;
select d_error;
END
複制
測試：
-- 設計部的id = 7
SET @id=7;
call removeDepartment(@id);
複制
是否存在子節點（葉子節點）
無需額外的查詢，直接通過節點的左右數，即可判斷是否是葉子節點了；當右數 - 左數 = 1時，說明目前節點就屬于葉子節點，否則就不是；
查詢所有的下級部門
等價于：查詢左數比目前節點大，右數比目前節點小，且層比目前節點大1的所有節點；
例：查詢産品部（lt = 3，rt = 12，lv = 3）的所有下級部門：
SET @lt = 3; -- 節點左數
SET @rt = 12; -- 節點右數
SET @lv = 3; -- 當先的層級
SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 1
複制
查詢所有的下下級部門（孫節點）
實際業務中很少會出現此需求，這裡僅僅用于可行性示範；
孫節點的查詢和子節點類似，僅僅層級由+1變為了+2
例：查詢産品部（lt = 3，rt = 12，lv = 3）的所有下下級部門：
SET @lt = 3; -- 節點左數
SET @rt = 12; -- 節點右數
SET @lv = 3; -- 當先的層級
SELECT * from department_info2 where lt > @lt AND rt < @rt AND `lv` = @lv + 2;
複制
查詢所有下屬部門
等價于：比目前節點左數大，右數小的節點，全部是子孫節點；
例，查詢産品部（lt = 3，rt = 12）的所有下屬部門：
SET @lt = 3; -- 節點左數
SET @rt = 12; -- 節點右數
SELECT * from department_info2 where lt > @lt AND rt < @rt;
複制
查詢隸屬部門
等價于：左數比自己小，右數比自己大，且層級-1的節點，也就是父節點
例，查詢技術部（lt = 6 ， rt = 11）的隸屬部門：
SET @lt = 6; -- 節點左數
SET @rt = 11; -- 節點右數
SET @lv = 4; -- 當先的層級
SELECT * from department_info2 where lt < @lt AND rt > @rt AND `lv` = @lv - 1 ;
複制
查詢所有的上級部門
與查詢父節點類似，隻是不再需要校驗層級了，所有左數比自己小，右數比自己大都是自己的祖先節點；
例，查詢産品部（lt = 3，rt = 12）的所有上級部門
SET @lt = 3; -- 節點左數
SET @rt = 12; -- 節點右數
SELECT * from department_info2 where lt < @lt AND rt > @rt;
複制
統計所有下屬部門的數量
統計子孫節點數量，無需額外查詢，隻需根據自己的左右數，即可計算出子節點的數量；
計算公式：（右數 - 左數 - 1 ）/ 2；
例，計算産品部（id = 4）的下屬部門的數量：
SELECT dep_name,(rt - lt - 1) / 2 as num FROM department_info2 where id = 4
複制
3格式化資料
不管是那種方案，資料層面都是扁平的，隻是通過字段邏輯表達了結構化的關系，那查詢出來之後，要如何将資料結構化成樹形結構之後展示呢，下面介紹遞歸和非遞歸的兩種方式實作方式:
基礎的對象
@Data
@RequiredArgsConstructor
public class LrItem {
@NonNull
private Integer id;
@NonNull
private String depName;
@NonNull
private Integer left;
@NonNull
private Integer right;
private Integer level;
private Integer parentId;
/**
* 是否是葉子
*/
private Boolean isLeaf;
private List<LrItem> childItem;
}
複制
測試資料
這裡隻是示範格式化資料，就不整那麼複雜了；實際業務場景，這批資料一般都是從資料庫中查詢出來的。
List<LrItem> deps = new ArrayList<>();
deps.add(new LrItem(1, "董事會", 1, 22));
deps.add(new LrItem(2, "總經理", 2, 19));
deps.add(new LrItem(3, "董事會秘書", 20, 21));
deps.add(new LrItem(4, "産品部", 3, 12));
deps.add(new LrItem(5, "行政總監", 13, 18));
deps.add(new LrItem(6, "設計部", 4, 5));
deps.add(new LrItem(7, "技術部", 6, 11));
deps.add(new LrItem(8, "财務部", 14, 15));
deps.add(new LrItem(9, "行政部", 16, 17));
deps.add(new LrItem(10, "用戶端", 7, 8));
deps.add(new LrItem(11, "服務端", 9, 10));
複制
整理資料
public static void init(List<LrItem> deps) {
// 如果資料庫排序過了之後 這裡就不用排序了
deps.sort(Comparator.comparing(LrItem::getLeft));
// 為計算層級 緩存節點右側的值
List<Integer> rights = new ArrayList<>();
Map<Integer, Integer> mp = new HashMap<>();
// 初始化節點的層級，葉子節點 以及 父節點ID 對應的資料
deps.forEach(item -> {
if (rights.size() > 0) {
// 一旦發現本次節點右側的值比前一次的大，說明出現層級上移了 需要移除前一個底層及的值
// 這裡大部分情況下隻存在移除前面一個值情況
while (rights.get(rights.size() - 1) < item.getRight()) {
rights.remove(rights.size() - 1);//從rights末尾去除
}
}
Integer _level = rights.size() + 1;
item.setLevel(_level);
mp.put(_level, item.getId());
item.setParentId(mp.containsKey(_level - 1) ? mp.get(_level - 1) : 0); //計算出上級部門編号
item.setIsLeaf(item.getLeft() == item.getRight() - 1);//判斷是否葉子部門
rights.add(item.getRight());
});
System.out.println(rights);
System.out.println(mp);
}
複制
遞歸整理
遞歸的思路比較簡單清晰，就是拿到目前節點之後，在所有是節點中找自己的子節點，當所有節點都找過一遍之後，整個樹形結構話的過程就完了；
我們可以結合Java 8 Stream新特性，讓整個遞歸代碼相對簡單清晰；
/**
* @param deps 所有資料
*/
public static void recursive(List<LrItem> deps) {
init(deps);
//擷取父節點
List<LrItem> collect = deps.stream()
.filter(m -> m.getParentId() == 0)
.map(m ->
{
m.setChildItem(getChildrens(m, deps));
return m;
}
).collect(Collectors.toList());
// 普遍請求下，根節點隻會有一個，是以這裡取出第一個元素，如果由多個，可根據需求調整，這裡僅做測試使用
System.out.println(JSON.toJSON(collect.get(0)));
}
/**
* 遞歸查詢子節點
*
* @param root 根節點
* @param all 所有節點
* @return 根節點資訊
*/
private static List<LrItem> getChildrens(LrItem root, List<LrItem> all) {
List<LrItem> children = all.stream()
.filter(m -> Objects.equals(m.getParentId(), root.getId()))
.map(m -> {
m.setChildItem(getChildrens(m, all));
return m;
}
).collect(Collectors.toList());
return children;
}
複制
非遞歸倒序整理
這是一個以空間換時間的方案；
此方式的特點：按層級排序後的資料，隻需要一次for循環，就能整理出結構化的資料。
- 第一步，計算出層級以及父節點ID
- 第二步，按層級進行排序
-
第三步，倒序從最深的節點讓root節點周遊
周遊過程以
Map<Integer, List<LrItem>>
childItem
public static void reverseFormat(List<LrItem> deps) {
init(deps);
deps.sort(Comparator.comparing(LrItem::getLevel));
deps.forEach(item -> System.out.println(JSON.toJSONString(item)));
// 臨時緩存各自節點的容器
Map<Integer, List<LrItem>> childCache = new HashMap<>();
// 目前節點
LrItem lrItem = null;
//int level = 0;
// 采用倒序周遊，整理各個子節點的集合
for (int i = deps.size() - 1; i >= 0; i--) {
lrItem = deps.get(i);
Integer parentId = lrItem.getParentId();
if (null == lrItem || null == parentId) {
continue;
}
List<LrItem> childItems = childCache.get(parentId);
if (null == childItems) {
childCache.put(parentId, childItems = new ArrayList<>());
}
childItems.add(lrItem);
// 如果不是葉子節點的時候，說明他肯定有子節點，去緩存中找到，回填回去
if (!lrItem.getIsLeaf()) {
childItems = childCache.get(lrItem.getId());
childItems.sort(Comparator.comparing(LrItem::getId));
lrItem.setChildItem(childItems);
childCache.remove(lrItem.getId());
}
}
System.out.println(JSON.toJSONString(lrItem));
}
複制
格式化後的資料
不管那種方式，最終都會得到以下的結構化資料；
{
"depName": "董事會",
"id": 1,
"isLeaf": false,
"left": 1,
"level": 1,
"prientId": 0,
"right": 22,
"childItem": [
{
"depName": "總經理",
"id": 2,
"isLeaf": false,
"left": 2,
"level": 2,
"prientId": 1,
"right": 19,
"childItem": [
{
"depName": "行政總監",
"id": 5,
"isLeaf": false,
"left": 13,
"level": 3,
"prientId": 2,
"right": 18,
"childItem": [
{
"depName": "設計部",
"id": 6,
"isLeaf": true,
"left": 4,
"level": 4,
"prientId": 4,
"right": 5
},
{
"depName": "技術部",
"id": 7,
"isLeaf": false,
"left": 6,
"level": 4,
"prientId": 4,
"right": 11,
"childItem": [
{
"depName": "用戶端",
"id": 10,
"isLeaf": true,
"left": 7,
"level": 5,
"prientId": 7,
"right": 8
},
{
"depName": "服務端",
"id": 11,
"isLeaf": true,
"left": 9,
"level": 5,
"prientId": 7,
"right": 10
}
]
}
],
"depName": "産品部",
"id": 4,
"isLeaf": false,
"left": 3,
"level": 3,
"prientId": 2,
"right": 12
},
{
"childItem": [
{
"depName": "财務部",
"id": 8,
"isLeaf": true,
"left": 14,
"level": 4,
"prientId": 5,
"right": 15
},
{
"depName": "行政部",
"id": 9,
"isLeaf": true,
"left": 16,
"level": 4,
"prientId": 5,
"right": 17
}
]
}
]
},
{
"depName": "董事會秘書",
"id": 3,
"isLeaf": true,
"left": 20,
"level": 2,
"prientId": 1,
"right": 21
}
]
}
複制
4比較
針對上面的詳解，下來以表格的形式來更直覺的對兩者做一下對比：
| 功能 | 父子關系方案 | 先序數方案 |
|---|---|---|
| 新增 | 簡單 | 複雜 |
| 修改 | 簡單 | 複雜 |
| 删除 | 複雜 | 複雜 |
| 判斷葉子節點 | 複雜（除非增加編輯難度，提前整理好） | 簡單 |
| 查詢子節點 | 簡單 | 簡單 |
| 查詢孫節點 | 複雜 | 簡單 |
| 查詢父節點 | 簡單 | 簡單 |
| 查詢祖先節點 | 複雜 | 簡單 |
| 統計子孫節點數量 | 複雜 | 簡單 |
| 适用場景 | 結構簡單，層級少，統計少，頻繁改動 | 結構複雜，改動少，層級深，需要複雜統計 |
5總結
經過對兩種方案常用場景的分析，發現其實各自都有自己的優缺點，是以原諒我标題稍微有點點标題黨；相比起來，個人還是比較喜歡改進的先序數方案
父子關系方案适合結構相對簡單、層級少的需求；
而先序數方案就更适合結構複雜，改動少，層級深，需要頻繁彙總統計的需求了；
是以說，還是那句話，沒有絕對好的方案，隻有合不合适的場景；需要更具自己業務的實際情況，酌情挑選對項目最有利的方案。
好了，今天的分享就到這裡；如果有任何問題，歡迎随時交流指正！