背景

目录树的构造一文从真实需求出发，较为详细地阐述了目录树的构建方式。回过头来看，其实就是将id为0的节点作为根节点对树进行层序遍历，以前端友好的数据格式进行返回。但是仔细思考之下，该实现在工程上的拓展能力尚有欠缺，无法对目录树的展示顺序进行控制。

问题

从数据结构的角度来看，构造一棵树时，每个节点的结构一般如下所示：

class TreeNode:id = 0left = Noneright = Nonedef __init__(self):self.id = 0self.left = TreeNode()self.right = TreeNode()

可以看见，一般的树节点包括id、左孩子和右孩子。而在前文的实现中，作为目录中的每个节点，存储的信息其实只有id和parent_id，category_level是作为前端渲染页面的冗余字段存在，对于后端而言该字段并没有任何实际用处，根据id和parent_id就能够确定目录树的结构，抽象后每个节点的结构如下所示：

class CategoryTreeNode:id = 0parent = Nonedef __init__(self):self.val = 0self.parent = TreeNode()

那么问题来了，既然前文的实现中只要id和parent_id就可以确定一棵树的结构，为什么在一般的树算法实现中，都需要通过id、left和right来确定一棵树的结构呢？

解析

通过id、left和right来确定树结构，可以明确地知道哪个节点是左孩子，哪个节点是右孩子，换而言之，对于树中的每个层级，节点的先后顺序是被完全定义的。而在前文的构造方式中，默认了一个前提，即 category_list 中数据的出现顺序就是层级中的节点顺序。

# 将父子类别连接形成树结构
categories_tree = []
for category in category_list:# 第一层级类别直接加入数组if category["parent_id"] == 0:categories_tree.append(category)# 如果是其它层级的类别，则将当前类别添加到父类别中的sub_categories中else:categories_map[category["parent_id"]]["sub_categories"].append(category)

站在工程角度来说，也就意味着数据库中存储该条目录信息的记录id，决定着在同一父目录下，id越小的记录展示在前，id越大的记录展示在后。如果查询db时对记录进行了倒排，则反之id越小的记录展示在后，id越大的记录展示在前。在大部分场景下似乎并无不妥，但当你需要增加一个子目录，并且想要该子目录在当前层级中间时，便需要将该条数据插入到数据库中对应顺序的位置，当id冲突时，还需要将比该记录id更大的所有记录进行移动，似乎不是个很妥当的办法。

优化

说到底其实是想要有一种合适的方式记录数据的相对位置。那么直接按照数据结构中的常用方式，不使用parent_id而是通过left和right对整棵树进行构造不就行了嘛。这里存在一个数据库设计上的问题，真实场景下每个父节点并不一定只有两个子节点，而是不确定的子节点个数。

1. 如果每个子节点id占用表中的一列，则该表需要设置很大的列数以满足未来的拓展需求；
2. 如果所有子节点id作为数组存储占用表中的一列，会增加数据库的复杂度，查询和更新数据的难度提升；
3. 如果每个子节点信息作为一行进行存储，多个子结点存储为多行记录，结果依然是记录的id决定了该目录的在当前父目录下的展示顺序，并没有解决根本问题。

该问题最合理的解法，应该是在数据库中新增一个order_id字段，通过对order_id字段进行排序，确定每个节点在目录树中的相对顺序。
建表语句如下：

/*
Navicat MySQL Data TransferSource Server         : localhost_3306
Source Server Version : 50720
Source Host           : localhost:3306
Source Database       : learning_projectsTarget Server Type    : MYSQL
Target Server Version : 50720
File Encoding         : 65001Date: 2023-03-18 18:26:27
*/SET FOREIGN_KEY_CHECKS=0;-- ----------------------------
-- Table structure for `oprimize_category_info`
-- ----------------------------
DROP TABLE IF EXISTS `oprimize_category_info`;
CREATE TABLE `oprimize_category_info` (`id` int(11) NOT NULL AUTO_INCREMENT,`category_name` varchar(64) NOT NULL COMMENT '分类名称',`parent_id` int(11) NOT NULL DEFAULT '0' COMMENT '当前分类父类的id，如果无父类则为0',`category_level` int(11) NOT NULL COMMENT '分类层级',`order_id` int(11) DEFAULT NULL,PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=utf8 COMMENT='分类信息表';-- ----------------------------
-- Records of oprimize_category_info
-- ----------------------------
INSERT INTO `oprimize_category_info` VALUES ('1', 'level-1', '0', '1', '2');
INSERT INTO `oprimize_category_info` VALUES ('2', 'level-2', '0', '1', '3');
INSERT INTO `oprimize_category_info` VALUES ('3', 'level-3', '0', '1', '1');
INSERT INTO `oprimize_category_info` VALUES ('4', 'level-2.1', '2', '2', '4');
INSERT INTO `oprimize_category_info` VALUES ('5', 'level-2.2', '2', '2', '5');
INSERT INTO `oprimize_category_info` VALUES ('6', 'level-3.1', '3', '2', '6');
INSERT INTO `oprimize_category_info` VALUES ('7', 'level-2.2.1', '5', '3', '8');
INSERT INTO `oprimize_category_info` VALUES ('8', 'level-2.2.2', '5', '3', '7');

操作代码如下：

import jsonfrom db_utils.sync_db_connector import get_mysql_connectordef get_all_categories():# categories_list从db获取db, cursor = get_mysql_connector()cursor.execute("select * from optimize_category_info order by order_id")category_tuples = cursor.fetchall()# tuple转dictcategory_list = []for tuple in category_tuples:tmp_category = {"id": tuple[0],"category_name": tuple[1],"parent_id": tuple[2],"category_level": tuple[3]}category_list.append(tmp_category)db.close()return category_listdef get_categories_tree():# 从db读取category数据category_list = get_all_categories()# 构建map: category_id -> category对象categories_map = {}for category in category_list:category["sub_categories"] = []categories_map[category["id"]] = category# 将父子类别连接形成树结构categories_tree = []for category in category_list:# 第一层级类别直接加入数组if category["parent_id"] == 0:categories_tree.append(category)# 如果是其它层级的类别，则将当前类别添加到父类别中的sub_categories中else:categories_map[category["parent_id"]]["sub_categories"].append(category)return categories_treeif __name__ == '__main__':category_tree = get_categories_tree()print(json.dumps(category_tree))

最终的效果为：

[{"id":3,"category_name":"level-3","parent_id":0,"category_level":1,"sub_categories":Array[1]},{"id":1,"category_name":"level-1","parent_id":0,"category_level":1,"sub_categories":Array[0]},{"id":2,"category_name":"level-2","parent_id":0,"category_level":1,"sub_categories":[{"id":4,"category_name":"level-2.1","parent_id":2,"category_level":2,"sub_categories":Array[0]},{"id":5,"category_name":"level-2.2","parent_id":2,"category_level":2,"sub_categories":[{"id":8,"category_name":"level-2.2.2","parent_id":5,"category_level":3,"sub_categories":Array[0]},{"id":7,"category_name":"level-2.2.1","parent_id":5,"category_level":3,"sub_categories":Array[0]}]}]}
]

后续需要添加目录信息，只需要对order_id字段进行变更，不需要对数据进行整体移动即可完成有序目录树的构造。为了排序更加灵活，可以在初始化order_id时设置更大步长，以便在当前的目录顺序中新增中间数据。