怎么将数据库中存的树转化为树形列表

树状结构的数据保存在数据库中的常用方法有一下两种：

1、邻接表(adjacency list model)

2、预排序遍历树算法(modified preorder tree traversal algorithm)

用一下的例子讨论这两种方法的差异：

现有一棵树如下：

邻接表模式：

这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表:

我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题， 这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, description。

以下是代码：

<php

// $parent is the parent of the children we want to see

// $level is increased when we go deeper into the tree,

// used to display a nice indented tree

function display_children($parent, $level)

{

// 获得一个 父节点 $parent 的所有子节点

$result = mysql_query('SELECT name FROM tree '

'WHERE parent="'$parent'";');

// 显示每个子节点

while ($row = mysql_fetch_array($result))

{

// 缩进显示节点名称

echo str_repeat(' ',$level)$row['name']"n";

//再次调用这个函数显示子节点的子节点

display_children($row['name'], $level+1);

}

}

>

对整个结构的根节点（Food）使用这个函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children('',0)。将显示整个树的内容：

Food

Fruit

Red

Cherry

Yellow

Banana

Meat

Beef

Pork

如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children('Fruit',0);

几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是　"Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food"

以下是代码：

<php

// $node 是那个最深的节点

function get_path($node)

{

// 查询这个节点的父节点

$result = mysql_query('SELECT parent FROM tree '

'WHERE name="'$node'";');

$row = mysql_fetch_array($result);

// 用一个数组保存路径

$path = array();

// 如果不是根节点则继续向上查询

// (根节点没有父节点)

if ($row['parent']!='')

{

// the last part of the path to $node, is the name

// of the parent of $node

$path[] = $row['parent'];

// we should add the path to the parent of this node

// to the path

$path = array_merge(get_path($row['parent']), $path);

}

// return the path

return $path;

}

>

如果对"Cherry"使用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：

Array

(

[0] =>; Food

[1] =>; Fruit

[2] =>; Red

)

接下来如何把它打印成你希望的格式，就是你的事情了。

缺点：

这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

预排序遍历树算法

现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm) 这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。

我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。

这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点

这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。

注意：由于"left"和"right"在 SQL中有特殊的意义，所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。

SELECT FROM tree WHERE lft BETWEEN 2 AND 11;

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

SELECT FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2

descendants = (right – left - 1) / 2 ，如果不是很清楚这个公式，那就去翻下书，我们在上数据结构写的很清楚！

添加同一层次的节点的方法如下：

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category WHERE name = 'Cherry';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;

UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO nested_category(name, lft, rgt) VALUES('Strawberry', @myRight + 1, @myRight + 2);

UNLOCK TABLES;

添加树的子节点的方法如下：

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category WHERE name = 'Beef';

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft;

UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES('charqui', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;

每次插入节点之后都可以用以下SQL进行查看验证：

SELECT CONCAT( REPEAT( ' ', (COUNT(parentname) - 1) ), nodename) AS name

FROM nested_category AS node,

nested_category AS parent

WHERE nodelft BETWEEN parentlft AND parentrgt

GROUP BY nodename

ORDER BY nodelft;

删除节点的方法，稍微有点麻烦是有个中间变量,如下：

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1

FROM nested_category WHERE name = 'Cherry';

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;

UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

UNLOCK TABLES;

这种方式就是有点难的理解，但是适合数据量很大规模使用，查看所有的结构只需要两条SQL语句就可以了，在添加节点和删除节点的时候略显麻烦，不过相对于效率来说还是值得的。

好段：

1、Early summer is a festive time for birds In the fields, around the houses, in the barns, in the woods, in the moors - there were birds all over the place, singing, nests and eggs

初夏的日子对于小鸟来说是个喜庆的时节。田野上，房子周围，谷仓里，林子里，沼地里—到处都是小鸟的谈情说爱，在唱歌，到处是鸟窝是鸟蛋。

2、Everything on the farm was wet on a foggy morning The grass looks like a magic carpet The reed fields over there are like a forest of silver

在雾天的早晨，农场里什么东西都湿嗒嗒的。草地上看上去像一张魔毯。那边芦苇地像一片银光闪闪的森林。

3、The barn is very big It's very old It has the smell of hay, fertilizer, the sweat of tired horses, and the wonderful smell of hard-working cows

谷仓很大，它很旧了，里面有干草的气味，有肥料的气味，里面有干活累了的马的汗味，有吃苦耐劳的母牛的极好闻的气息。

4、The next day it rained and it was dark Rain fell on the top of the barn, dripping from the eaves; Rain fell into the barn yard, and it was winding and flowing down the grass path; The rain crackled on Mrs Zuckerman's kitchen window, and the water pipe gushed out; The rain fell on the back of the sheep who were grazing on the grass The sheep stood tired in the rain, and slowly walked back to the sheepskin along the path

第二天下雨，天色阴沉沉的。雨水落在谷仓顶上，不停地从屋檐上滴落下来；雨水落到谷仓院子里，弯弯曲曲地一道一道流进长着草的小路；雨水噼里啪啦地打在朱克曼太太的厨房窗上，咕咚咕咚地涌出水管；雨水落在正在草地上吃草的羊的背上。羊在雨中站累了，就沿着小路慢慢地走回羊圈。

5、On the farm, early summer is the happiest and most beautiful day of the year Cloves bloom, making the air fragrant Next, the lilacs withered, the apple tree blossomed again, and the bees flew around the apple tree It's getting warmer and warmer School holiday, the children have time to play, can go to the river fishing

在农场里，初夏的日子是一年当中最快活最美好的日子。丁香开花，让空气芳香扑鼻。接下来丁香花谢了，苹果树又紧接着开花，蜜蜂围着苹果树飞来飞去。天气越来越暖和。学校里放假了，孩子们有功夫玩了，可以到小河边去钓鱼。

好句：

1、On the farm, early summer is the happiest and best day of the year

 在农场里，初夏的日子是一年当中最快活最美好的日子。

2、Wilbur

will never forget Charlotte Although he loves his children,

grandchildren and great grandchildren, none of these new spiders can

only replace Charlotte in his heart Charlotte is incomparable

威尔伯永远忘不了夏洛它虽然热爱它的子女，孙子女，曾孙子女，可是这些新蜘蛛没有一只能取代夏洛在它心中的位置。夏洛是无可比拟的。

3、Charlotte worked so hard that she began to talk to herself, as if to cheer herself up

夏洛干得那么起劲，它开始自言自语，像是给自己打气。

4、You're going to be thin and skinny, so that we can see through it and see things on the other side

你就要瘦而又瘦，肚子瘪得我们可以看穿它看到另外一边的东西。

5、The net twinkles in the sun, forming a mysterious and lovely pattern, like a thin veil

网在阳光中闪闪烁烁，组成一个神秘可爱的图案，像一块纤细的面纱。

创作背景：

《夏洛的网》的创作灵感源于一个发生在他农场里的很特殊的事件。有一次怀特养的一头猪病了，为了救治这头猪，他费尽心血，寻医问药，与这头猪共度了三、四个十分焦虑的日子。最后这头猪还是死了。

本来这也没什么大不了的，因为这头猪没有病死，迟早也是要被宰杀的。可是怀特对此颇有感触，随即写下了散文《猪之死》，表达了他前所未有的感悟。如《猪之死》开头所写道：“春天，买上一头正在发身的猪仔，喂过夏秋，当酷寒天气来临时，宰掉--这是我非常熟稔的一种方式，自古以来一直是这样的。这是大部分农庄都一板一眼地实行的一种悲剧。

这种屠杀，因为是早有预谋，够得上一级罪愆，屠刀下去，迅疾而干脆利落，最终以烟熏火腿而隆重结束，从来就没有人对此行为存有过任何疑问。”怀特不仅对此存有疑问，而且他决心要拯救一头小猪的性命，于是便有了《夏洛的网》的故事。

咖啡的英文是coffee。

一、读音： ['kɒfi] 

二、意思是咖啡。

三、例句

He put some sugar into his coffee。

他往咖啡里加了些糖。

四、词汇用法

1、coffee的基本意思是“咖啡”，指一种可用于冲泡的饮料。

2、coffee多用作不可数名词,但在作“一杯咖啡”或“一种咖啡”解时则是可数名词，其复数形式可指各种(牌号)的咖啡。

3、可用a cup of coffee或a can of coffee(但不可用a glass of coffee)表示一杯的量。

近义词 cafe

一、读音： ['kæfeɪ] 

二、意思是咖啡馆

三、例句

This cafe keeps late into the night。

这家咖啡馆一直开到深夜。

四、词汇用法

cafe一般指供应小食品和无酒精饮料的露天餐馆或酒吧，多建于路边。

from into意思是从、、、进入；从入的意思

举例：

1

He did not answer directly, but he said Hamas militants must stop rocket attacksfrom Gaza into Israel

布什并没有直接回答，不过他说，哈马斯激进分子必须停止从加沙向以色列发射火箭。

2

Sweet dreams, is what he said as he went underground away from me into thedark

美梦，是什么他说，当他从我进入地下入黑暗。

from to

主要意思

(1) 表示“从……至……”“从……到……”。如:

How far is it from your office to the bank 从你办公室到银行有多远

We are removing from London to the country 我们正从伦敦迁往乡下。

I want a rope that will go from the top window to the ground 我要一条绳，其长度能自最上一扇窗户垂到地面。

(2) 表示“由……变成……”“将……改为……”。如:

He has moved from acting to film production 他由演员变成了制片人。

She’s been downgraded from principal to deputy 她已从校长降为副校长。

He swings from wild optimism to total despair 他由极其乐观一变而为完全绝望。

The room was converted from a kitchen to a lavatory 这房间由厨房改成了厕所。

(3) 表示“从一个……到另一个……”“一个……一个地”“逐个……”“挨个……”。如:

These people go from house to house selling goods 这些人挨家挨户兜售货物。

The ape swung along from branch to branch 那只猿猴从一根树枝汤到另一根树枝上。

He went from village to village, seeking for work 他从一个村子到另一个村子，找寻工作。

I like to hop from channel to channel when I watch TV 我看电视时喜欢不断地换频道。

Migrant workers move from country to country in search of work 流动工人从一国迁到另一国找寻工作。

The smaller animals can easily leap from tree to tree 身体较小的动物可以在树丛间轻巧地跳来跳去。

Computer viruses replicate themselves and are passed along from user to user 计算机病毒可以自我复制，然后由用户传给用户。

tree 英 [tri:]   美 [tri]  ：n 树;木料;树状图;宗谱；vt 把赶上树;使处于困境;把鞋型插入（鞋内）

短语

family tree 家族树 ; 家谱 ; 家庭树 ; 族谱

Suffix Tree [计] 后缀树 ; 后缀树实现 ; 字尾树

tree hyrax 树蹄兔属 ; 树蹄兔

Leftist tree 左偏树 ; 左倾树

Tree sitting 树坐 ; 国际常见的树坐

Tree spiking 树钉

Metric tree 度量树

Fenwick tree 树状数组

camphor tree [林] 樟树 ; [林] 樟脑树 ; 香樟树 ; 香樟

扩展资料

双语例句

1、You are absolutely correct The leaves are from a bay tree 

你说得很对，这是月桂树的叶子。

2、The peach tree is wormy 

桃树长虫了。

3、He dug a hole in our yard on Edgerton Avenue to plant a maple tree when I was born

我出生的时候，他在埃杰顿大街我们家的园圃里挖了个坑，种了棵枫树。

4、China has the world's most ancient tree species--metasequoia 

中国有世界最古老的树种--水杉。

5、A vandal with a chainsaw cut down a tree 

一个故意破坏公物的人用链锯伐倒了一棵树。

bitsCNcom

mysql的逆袭:如何做递归层次查询 最近在做一个从oracle数据库到mysql数据库的移植，遇到一个这样的问题 在Oracle 中我们知道有一个 Hierarchical Queries 通过CONNECT BY 我们可以方便的查了所有当前节点下的所有子节点。但shi，在MySQL的目前版本中还没有对应的函数！！！ 换句话来说，想要用mysql实现递归查询，根本做不到！！！ 可是经过我数天茶不思饭不想的刻苦琢磨，终于想到了一个合理的，适用于mysql和其他sql的解决方案。 方案一出，就秋风扫落叶之势，席卷整个dao层~~~所到之处，所有问题迎刃而解，让所有问题都不再为问题 都成为了我这个函数的炮灰而已。。 话不多说待我把解决方法仔细道来~~~~~ 下面是sql脚本，想要运行一下 把下边的粘贴复制下来，做一个treenodessq直接运行便是。。 / Navicat MySQL Data Transfer Source Server : mysql_demo3 Source Server Version : 50521 Source Host : localhost:3306 Source Database : test Target Server Type : MYSQL Target Server Version : 50521 File Encoding : 65001 Date: 2012-09-02 21:16:03 / SET FOREIGN_KEY_CHECKS=0; -- ---------------------------- -- Table structure for `treenodes` -- ---------------------------- DROP TABLE IF EXISTS `treenodes`; CREATE TABLE `treenodes` ( `id` int(11) NOT NULL, `nodename` varchar(20) DEFAULT NULL, `pid` int(11) DEFAULT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1; -- ---------------------------- -- Records of treenodes -- ---------------------------- INSERT INTO `treenodes` VALUES ('1', 'A', '0'); INSERT INTO `treenodes` VALUES ('2', 'B', '1'); INSERT INTO `treenodes` VALUES ('3', 'C', '1'); INSERT INTO `treenodes` VALUES ('4', 'D', '2'); INSERT INTO `treenodes` VALUES ('5', 'E', '2'); INSERT INTO `treenodes` VALUES ('6', 'F', '3'); INSERT INTO `treenodes` VALUES ('7', 'G', '6'); INSERT INTO `treenodes` VALUES ('8', 'H', '0'); INSERT INTO `treenodes` VALUES ('9', 'I', '8'); INSERT INTO `treenodes` VALUES ('10', 'J', '8'); INSERT INTO `treenodes` VALUES ('11', 'K', '8'); INSERT INTO `treenodes` VALUES ('12', 'L', '9'); INSERT INTO `treenodes` VALUES ('13', 'M', '9'); INSERT INTO `treenodes` VALUES ('14', 'N', '12'); INSERT INTO `treenodes` VALUES ('15', 'O', '12'); INSERT INTO `treenodes` VALUES ('16', 'P', '15'); INSERT INTO `treenodes` VALUES ('17', 'Q', '15'); --------------------------------------------------- 上边是sql脚本，在执行select 之后显示的结果集如下所示： mysql> select from treenodes; +----+----------+------+ | id | nodename | pid | +----+----------+------+ | 1 | A | 0 | | 2 | B | 1 | | 3 | C | 1 | | 4 | D | 2 | | 5 | E | 2 | | 6 | F | 3 | | 7 | G | 6 | | 8 | H | 0 | | 9 | I | 8 | | 10 | J | 8 | | 11 | K | 8 | | 12 | L | 9 | | 13 | M | 9 | | 14 | N | 12 | | 15 | O | 12 | | 16 | P | 15 | | 17 | Q | 15 | +----+----------+------+ 17 rows in set (000 sec) 树形图如下 1:A +-- 2:B | +-- 4:D | +-- 5:E +-- 3:C +-- 6:F +-- 7:G 8:H +-- 9:I | +-- 12:L | | +--14:N | | +--15:O | | +--16:P | | +--17:Q | +-- 13:M +-- 10:J +-- 11:K -------------------------------------------- 如果给你一个这样的table，让你查询根节点为1下的所有节点记录（注意也包括根节点），，肿麽办？？？？？ 可能有不少人想到connect by 函数，但是我灰常遗憾的告诉你，咱这儿是mysql！！！ 好，客观您勒上眼，，我的解决办法是 利用函数来得到所有子节点号。 闲话少续，看我的解决方法 创建一个function getChildLst, 得到一个由所有子节点号组成的字符串 mysql> delimiter // mysql> mysql> CREATE FUNCTION `getChildLst`(rootId INT) -> RETURNS varchar(1000) -> BEGIN -> DECLARE sTemp VARCHAR(1000); -> DECLARE sTempChd VARCHAR(1000); -> -> SET sTemp = '$'; -> SET sTempChd =cast(rootId as CHAR); -> -> WHILE sTempChd is not null DO -> SET sTemp = concat(sTemp,',',sTempChd); -> SELECT group_concat(id) INTO sTempChd FROM treeNodes where FIND_IN_SET(pid,sTempChd)>0; -> END WHILE; -> RETURN sTemp; -> END -> // Query OK, 0 rows affected (000 sec) mysql> mysql> delimiter ; 使用我们直接利用find_in_set函数配合这个getChildlst来查找 mysql> select getChildLst(1); +-----------------+ | getChildLst(1) | +-----------------+ | $,1,2,3,4,5,6,7 | +-----------------+ 1 row in set (000 sec) mysql> select from treeNodes -> where FIND_IN_SET(id, getChildLst(1)); +----+----------+------+ | id | nodename | pid | +----+----------+------+ | 1 | A | 0 | | 2 | B | 1 | | 3 | C | 1 | | 4 | D | 2 | | 5 | E | 2 | | 6 | F | 3 | | 7 | G | 6 | +----+----------+------+ 7 rows in set (001 sec) mysql> select from treeNodes -> where FIND_IN_SET(id, getChildLst(3)); +----+----------+------+ | id | nodename | pid | +----+----------+------+ | 3 | C | 1 | | 6 | F | 3 | | 7 | G | 6 | +----+----------+------+ 3 rows in set (001 sec) -------------------------------------------- 只要按我的做，百发百中弹无虚发，遇到问题万变不离其宗直接粘贴复制就是。。 补充： 还可以做嵌套查询： select id,pid from treeNodes where id in( select id from treeNodes where FIND_IN_SET(id, getChildLst(3)) ); 子查询的结果集是 +--------+ id ---- 3 6 7 +-------+ 然后经过外层查询就是 id pid 3 1 6 3 6 6 --------- 好了 Perfect bitsCNcom