使用 PHP/MySQL 从头开始​​创建树遍历层次结构

Question

我目前正在开发一个类别层次结构，我认为我得到了创建树遍历的要点。但我需要使用 PHP 函数向该层次结构添加一个新节点。

问题是rebuild_tree函数就足够好了（换句话说，对于大树来说效率很高）。

示例查询：

 CREATE TABLE `t_categories`(
   `id` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
   `title` VARCHAR(45) NOT NULL,
   `lft` INTEGER UNSIGNED NOT NULL,
   `rght` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 1',1,16);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 2',2,3);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 3',4,7);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 4',5,6);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 5',8,13);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 6',9,12);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 7',10,11);
 INSERT INTO t_categories (title, lft, rght) VALUES ('Cat 8',14,15);

表结果如下所示：

 ID    TITLE   LFT    RGHT
 1     Cat1    1      16
 2     Cat2    2      3
 3     Cat3    4      7
 4     Cat4    5      6
 5     Cat5    8      13
 6     Cat6    9      12
 7     Cat7    10     11
 8     Cat8    14     15

我在上面提供了示例数据，但我还需要从头开始创建全新的节点。

那么，如何使用 PHP 函数将新节点添加到这棵树中，以提高大型树的效率？

Answer 1

这是一棵celko树。最简单的方法是深度优先遍历树，仅更新左值，然后以递归方式更新右值。插入的成本要高得多。

Answer 2

我建议您在表结构中添加“父 ID”字段，而不是“左”和“右”字段。如果子项目的订单对您很重要，也可以使用“localorder”int 字段。

在当前的结构中，每次要添加一个项目时，对于第一个项目，都必须检查是否存在前一个项目，对于最后一个项目，必须检查是否存在最终项目。

CREATE TABLE `t_categories`(
   `keyid` INTEGER UNSIGNED NOT NULL,
   `title` VARCHAR(45) NOT NULL,
   `parentid` INTEGER UNSIGNED NOT NULL,
   `sortorder` INTEGER UNSIGNED NOT NULL,
   PRIMARY KEY (`id`)
 );

-- root item, no parent
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (1, 'Root', 0, 0);

-- first level
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (2, 'a:', 1, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'b:', 1, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (3, 'c:', 1, 3);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (4, 'd:', 1, 4);

-- second level

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (5, 'a:\temp', 2, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (6, 'a:\docs'', 2, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (7, 'a:\music', 2, 3);

 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (8, 'c:\temp', 4, 1);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (9, 'c:\docs'', 4, 2);
 INSERT INTO t_categories (keyid, title, parentid, sortorder) VALUES (10, 'c:\music', 4, 3);

-- and so on

Answer 3

霍夫曼压缩使用同一棵树来计算给定文档中字母的出现次数。我认为对字符串进行编码，然后算法还使用深度优先遍历，以便使用尽可能少的位对出现次数最多的字母进行编码。我不知道它在这里是否有用，但使用香农定理 -log(x)+log(2) 可以找到文本的最低熵，其中 x 是字母，log(2) 是位的基数，它始终是2.

Answer 4

我之前的回答不完整。这是一个摘要，整个代码太长了，无法在论坛帖子中发表。忘了问，程序化 PHP，还是面向对象 PHP？

MySQL：
创建表t_categories(
keyid 整数无符号非空，
标题 VARCHAR(45) NOT NULL,
parentid 整数无符号非空，
sortorder 整数无符号非空，
主键（id）
）；

PHP 函数头：

// globar var，作用类似于类型
/* typedef */ treeNodeType = array(
“密钥ID”=> 0,
“标题”=> "",
“父代” => 0,
“排序顺序”=> 0,
)

// globar var，作用类似于类型
/* typedef */ treeType = array(
“根” =>零，
“无论如何” => "",
)

/* treeNodeType / function insertNode(/ treeType / ATree, AParentId, ATitle) { ... }
/ void / function deleteNode(/ treeType */ ATree, AKeyId) { ... }

// -->主要的
主要的（）;

/* 无效 */ 函数 main() {
// 树类型 myTree;
myTree = 树类型；

// 插入根=0
rootNode = insertNode(myTree, 0, '[PC]');

...
}