1

我目前正在开发一个类别层次结构，并且我认为我得到了创建树遍历的目的。但是我需要使用 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 函数将新节点添加到该树中？

4

4 回答 4

2

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

于 2011-03-07T18:31:54.417 回答
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
于 2011-03-07T18:34:08.980 回答
0

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

于 2011-03-07T20:23:30.557 回答
0

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

MySQL：创建表t_categories（ keyid整数无符号非空， titleVARCHAR（45）非空， parentid整数无符号非空， sortorder整数无符号非空，主键（id））；

PHP函数头：

// globar var，就像一个类型 /* typedef */ treeNodeType = array( "keyid" => 0, "title" => "", "parentid" => 0, "sortorder" => 0, )

// globar var, 就像一个类型 /* typedef */ treeType = array( "root" => nil, "whatever" => "", )

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

// --> 主 main();

/* void */ function main() { // treeType myTree; 我的树 = 树类型；

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

... }

于 2011-03-08T16:19:48.920 回答