自动化树遍历
现在你对这个表做一些事情，我们应该学习如何自动的建立表了。这是一个不错的练习，首先用一个小的树，我们也需要一个脚本来帮我们完成对节点的计数。
让我们先写一个脚本用来把一个邻接列表转换成前序遍历树表格。
这是一个递归函数。你要从rebuild_tree('Food',1); 开始，这个函数就会获取所有的“Food”节点的子节点。
如果没有子节点，他就直接设置它的左值和右值。左值已经给出了，1，右值则是左值加1。如果有子节点，函数重复并且返回最后一个右值。这个右值用来作为“Food”的右值。
递归让这个函数有点复杂难于理解。然而，这个函数确实得到了同样的结果。他沿着树走，添加每一个他看见的节点。你运行了这个函数之后，你会发现左值和右值和预期的是一样的（一个快速检验的方法：根节点的右值应该是节点数量的两倍）。
添加一个节点
我们如何给这棵树添加一个节点？有两种方式：在表中保留“parent”列并且重新运行rebuild_tree() 函数——一个很简单但却不是很优雅的函数；或者你可以更新所有新节点右边的节点的左值和右值。
第一个想法比较简单。你使用邻接列表方法来更新，同时使用改进前序遍历树来查询。如果你想添加一个新的节点，你只需要把节点插入表格，并且设置好parent列。然后，你只需要重新运行rebuild_tree() 函数。这做起来很简单，但是对大的树效率不高。
第二种添加和删除节点的方法是更新新节点右边的所有节点。让我们看一下例子。我们要添加一种新的水果——“Strawberry”，作为“Red” 的最后一个子节点。首先，我们要腾出一个空间。“Red”的右值要从6变成8，7-10的“Yellow”节点要变成9-12，如此类推。更新“Red” 节点意味着我们要把所有左值和右值大于5的节点加上2。
我们用一下查询：
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
现在我们可以添加一个新的节点“Strawberry”来填补这个新的空间。这个节点左值为6右值为7。
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
如果我们运行display_tree() 函数，我们将发现我们新的“Strawberry”节点已经成功地插入了树中：Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork
缺点
首先，改进前序遍历树算法看上去很难理解。它当然没有邻接列表方法简单。然而，一旦你习惯了左值和右值这两个属性，他就会变得清晰起来，你可以用这个技术来完成临街列表能完成的所有事情，同时改进前序遍历树算法更快。当然，更新树需要很多查询，要慢一点，但是取得节点却可以只用一个查询。
你现在已经对两种在数据库存储树方式熟悉了吧。虽然在我这儿改进前序遍历树算法性能更好，但是也许在你特殊的情况下邻接列表方法可能表现更好一些。这个就留给你自己决定了
最后一点：就像我已经说得我部推荐你使用节点的标题来引用这个节点。你应该遵循数据库标准化的基本规则。我没有使用数字标识是因为用了之后例子就比较难读。
算法3
在MYSQL中，数据表大致上是
CREATE TABLE Table_Types
(
id INTEGER NOT NULL AUTO_INCREMENT,
parent_id INTEGER,
node VARCHAR(255),
PRIMARY KEY (id)
)
如上图，紫色的是数据记录的ID号，框内的数字是每条记录的node字段，记录了该记录的父ID和父ID的父ID和...
这样，假如我们要在ID为7的记录下，插入一条新ID为13的记录，新记录的node就是1,2,7,13
要找一个节点下的所有子节点，就无需用递归，只要一个SQL。
如“查ID为2记录下所有子节点”
select * from Table_Types where node like "1,2,%"
大家探讨一下，该算法的有效性和不足！
上次看到的左右值的算法，虽然在搜索方面很不错，但是如果是插入频繁的应用，性能就很差了，因为每次插入新节点都需要update该父节点以下 的所有记录。的右值。而上面这个算法，对插入操作尤其简单，只要找到父ID的根下来就可以了。搜索方面好像也还不错，都是避免了递归.
您可能感兴趣的文章: