关于邻接表模式的数据结构

关于一种只包含父节点信息的树的遍历算法

 

在建立数据库或对一些具有树形结构的信息节点进行操作时，我们普遍采用的是一种方式是一个节点包含了孩子、父亲，二叉树中最普遍的方式是包含父亲、左孩子与右孩子，但现在遇到了一种数据结构，其中的节点只包含了它的父节点的信息，并且这个树是一个任意多叉树。搜集了一下网上的资料，这种类型好像有个名字叫做“邻接表模式”。下面是那篇文章：

 

产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下：

层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：

1、毗邻目录模式(adjacency list model)

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

我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。
这两个东西听着好像很吓人，其实非常容易理解。这里我用一个简单食品目录作为我们的示例数据。

我们的数据结构是这样的

以下是代码：

CODE:

Food
|
|---Fruit
|    |
|    |---Red
|    |    |
|    |    |--Cherry
|    |
|    |---Yellow
|          |
|          |--Banana
|
|---Meat
     |
     |--Beef
     |
     |--Pork

为了照顾那些英文一塌糊涂的PHP爱好者
Food:食物
Fruit:水果
Red:红色
Cherry:樱桃
Yellow:黄色
Banana:香蕉
Meat:肉类
Beef:牛肉
Pork:猪肉


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

以下是代码：

CODE:

+-----------------------+
|   parent |    name    |
+-----------------------+
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
|   Meat   |    Pork    |
+-----------------------+

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

显示多级树
如果我们需要显示这样的一个多级结构需要一个递归函数。

以下是代码：

CODE:

// $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)。将显示整个树的内容：

CODE:

Food
Fruit
Red
  Cherry
Yellow
  Banana
Meat
Beef
Pork

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

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

以下是代码：

CODE:

// $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'))，就会得到这样的一个数组了：

CODE:

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 的子孙节点

以下是代码：

CODE:

                                1 Food 18
                                    |
                +-------------------------------------------+
                |                                                       |
            2 Fruit 11                                    12 Meat 17
                |                                                       |
    +------------------------+                   +-----------------------+
    |                                |                   |                              |
3 Red 6               7 Yellow 10         13 Beef 14            15 Pork 16
    |                                |
4 Cherry 5               8 Banana 9

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

以下是代码：

CODE:

+-----------------------+-----+-----+
|   parent |    name  | lft   | rgt |
+-----------------------+-----+-----+
|          |    Food    | 1   | 18  |
|   Food   |   Fruit    | 2   | 11  |
|   Fruit  |    Red     | 3   |  6  |
|   Red    |    Cherry  | 4   |  5  |
|   Fruit  |    Yellow  | 7   | 10  |
|   Yellow |    Banana  | 8   |  9  |
|   Food   |    Meat    | 12  | 17  |
|   Meat   |    Beef    | 13  | 14  |
|   Meat   |    Pork    | 15  | 16  |
+-----------------------+-----+-----+

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

以下是代码：

CODE:

+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|    Food    | 1   | 18  |
|   Fruit    | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
|    Meat    | 12  | 17  |
|    Beef    | 13  | 14  |
|    Pork    | 15  | 16  |
+------------+-----+-----+

好了我们现在可以从数据库中获取数据了，例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个查询得到了以下的结果。

以下是代码：

CODE:

+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|   Fruit    | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
+------------+-----+-----+

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

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


剩下的问题如何显示层级的缩进了。

以下是代码：

CODE:

function display_tree($root)
{
   // 得到根节点的左右值
   $result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
   $row = mysql_fetch_array($result);

   // 准备一个空的右值堆栈
   $right = array();

   // 获得根基点的所有子孙节点
   $result = mysql_query('SELECT name, lft, rgt FROM tree '.
                          'WHERE lft BETWEEN '.$row['lft'].' AND '.
                          $row['rgt'].' ORDER BY lft ASC;');

   // 显示每一行
   while ($row = mysql_fetch_array($result))
   {
       // only check stack if there is one
       if (count($right)>;0)
   {
           // 检查我们是否应该将节点移出堆栈
           while ($right[count($right)-1]<$row['rgt'])
   {
               array_pop($right);
           }
       }

       // 缩进显示节点的名称
       echo str_repeat('  ',count($right)).$row['name']."n";

       // 将这个节点加入到堆栈中
       $right[] = $row['rgt'];
   }
}
?>;

如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。

要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;

这样就会得到以下的结果：

以下是代码：

CODE:

+------------+
|    name    |
+------------+
|   Food     |
|   Fruit    |
|    Red     |
+------------+

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2
descendants = (right – left - 1) / 2
不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。

很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。

这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。

以下是代码：

CODE:

function rebuild_tree($parent, $left) {
   // the right value of this node is the left value + 1
   $right = $left+1;

   // get all children of this node
   $result = mysql_query('SELECT name FROM tree '.
                          'WHERE parent="'.$parent.'";');
   while ($row = mysql_fetch_array($result)) {
       // recursive execution of this function for each
       // child of this node
       // $right is the current right value, which is
       // incremented by the rebuild_tree function
       $right = rebuild_tree($row['name'], $right);
   }

   // we've got the left value, and now that we've processed
   // the children of this node we also know the right value
   mysql_query('UPDATE tree SET lft='.$left.', rgt='.
                $right.' WHERE name="'.$parent.'";');

   // return the right value of this node + 1
   return $right+1;
}
?>;

当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

rebuild_tree('Food',1);

这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？

增加一个节点一般有两种方法：

第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。

第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果"Strawberry"（草莓）它将成为"Red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8，"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是"Red"最后一个子节点的右值） 加上2。 所以我们这样进行数据库操作：

UPDATE tree SET rgt=rgt+2 WHERE rgt>;5;
UPDATE tree SET lft=lft+2 WHERE lft>;5;

这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了， 它的左右值分别是6和7

INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';

再做一次查询看看吧！怎么样？很快吧。

好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。

另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。

 

 

好！shukebeita这个写得好！代码都不用看，就看你那个表和查询就知道思路了，可能比原来那个树型解决方案还要好！不过看起来暂时只是二叉树，还不是真正的任意形状的树，还得研究一阵子。

另外：shukebeita的两个翻译不准，现在我来翻译一下（主要对英文欠缺或是无专业背景人士）
1、adjacency list model   -  邻接表模式
注：adjacent list 术语为邻接表，好象是（好多年了，忘了很多）指主干节点拖的一个尾巴，与邻接矩阵有关。总之好象是每个节点都横竖两条双向链表中间，总体上被链成一个矩阵，每个节点是矩阵中的一个元素。

2、modified preorder tree traversal algorithm  -  修改过的先序遍历树算法（亦即先根遍历树算法）
注：modified  意为“修改过的”
preorder tree traversal  专业术语“先序遍历树”，preorder是“先于...的顺序”的意思，pre- 是词前缀，意为“先”，order 意为“顺序”；traversal是“遍历的”的意思。
整个算法的原则是：
从树根开始处理该树的所有节点，处理方法为——
先处理当前的节点，然后递归处理当前节点的左子节点，然后再递归处理当前节点的右子节点，如果子节点为NULL（没有节点）的话即返回。写成代码的话，一般形式为：

CODE:

function preorder(&$node, $level = 0){  // 注意是传递引用，C中也就是传递指针
    process_root($node);  // 处理本节点
   $n =& $node->;left;  // 引用赋值，以便作为参数传递
   if ($n != null){  // 如果左子节点不为空
        preorder($n, level + 1);  // 递归处理左子节点，同时层数加一
   }
     $n =& $node->;right;  // 引用赋值，以便作为参数传递
   if ($n != null){  // 如果右子节点不为空
        preorder($n, level + 1);  // 递归处理右子节点，同时层数加一
   }
}

以上之所以加了几个判断是为了防止多一次无意义的递归，引用赋值主要是减少PHP中的复制开销（PHP5是会好一些）。

而外部调用一般要先定义一个入口函数，再调用递归函数，形式如下：

CODE:

function call_preorder(){
    $root =& $tree->;root; // 引用赋值，将树的根作为遍历的入口点
   $level = 0;  // 树根是0级
    preorder($root, $level);  // 然后从树根开始遍历
}

递归函数中有一个函数是process(&$node)，用于处理该节点$node，可以实现任何你想实现的功能，如打印此节点的关键字值等。

 

 

QUOTE:

原帖由 "longnetpro" 发表：
2、modified preorder tree traversal algorithm - 修改过的先序遍历树算法（亦即先根遍历树算法）
注：modified 意为“修改过的”
preorder tree traversal 专业术语“先序遍历树”，preorder是“先于...的顺序”的意思，pre- 是词前缀，意为“先”，order 意为“顺序”；

多谢支持，这些方法也是我从外国的书里学到的，我的确不太懂这些术语，不过我对 modified preorder tree traversal algorithm 这一句还是有我的想法。

1、我不是计算级或者数学专业的，单是从字面上理解我想大概有一种算法叫做preorder tree traversal algorithm ，而这里用到的是它的一个修改版本，所以称其为modified。

2、pre是先的意思没错，但是order在这里更准确地说应该是排序，排定顺序的意思。所以就是说这个树是“预先排好序号“的树。

QUOTE:

最主要的是目前暂只适用于二叉树，不适合于多叉树。

不知道你说的多叉树是不是说像下面的样子

CODE:

                                1 Food 20
                                    |
                +-------------------------------------------+
                |                         |                             |
            2 Fruit 11     12  Vegetable 13    14 Meat 19
                |                                                       |
    +------------------------+                   +-----------------------+
    |                                |                   |                              |
3 Red 6               7 Yellow 10         15 Beef 16            17 Pork 18
    |                                |
4 Cherry 5               8 Banana 9

如果是这样的话，你完全可以放心，这种办法没有问题，一样适用。我已经试过多次。

QUOTE:

但建树的时候还要用到递归

所以这种方法对于经常需要查询，但是很少增加和更新的数据（比如产品，书籍的多级分类）更为合适，一旦建立很少变动。

QUOTE:

有时也会影响到计算所有子节点的数目，因为数据库操作写入可能会写错。

这就是需要transaction(事务处理)的地方了。

 

别的你说的都能理解，也很容易理解。

多叉树从排序情况看是一样的，但是的确插入和更新就比较麻烦了，虽说只用到少数几个UPDATE，但是改动却是大范围的。看来什么方法都不能十全十美的。

有一点必须指出，preorder肯定是你理解错误，“预先排好序号”这个意思完全与遍历无关，与它的算法原理也一点都不相合。

首先要搞清楚遍历的意思。遍历是将一个拓朴结构上所有的节点根据一种算法按顺序全都处理到——注意是所有的节点。遍历是一个过程，在遍历的过程中，按一定的顺序处理各个节点。

preorder 遍历就是“先序遍历”，也叫“先根遍历”，之所以这样说是因为先序遍历在对子节点进行递归遍历之前先处理根节点。inorder遍历是“中序遍历”，也叫“中根遍历”，因为中序遍历是先对左子节点递归遍历，然后处理根节点，然后再对右子节点进行递归遍历。postorder遍历是“后序遍历”，也叫“后根遍历”，是左右子节点都遍历排完了最后再处理根节点。

其实我对这个英文也理解有点误，但是术语肯定是“先序”这个意思，现在想起来可能中文意思与英文原意有差别。当时学的时候就是“先序”“前序”这种说法，但到底表示什么也不是很清楚。现在想来应该是这样的：preorder应该是“在排序之前”，inorder是“在排序之中”，postorder是“在排序之后”，就和“战前”，“战后”的拼词方法类似。可能总体上理解就是“当前节点的处理在排序（即递归遍历）之前的遍历算法”，“当前节点的处理在排序（即递归遍历）之中的遍历算法”，“当前节点的处理在排序（即递归遍历）之后的遍历算法”。

 

今天终于遇到关于多级分类查询和数据设计的问题了。再次认真看了一遍楼主的文章，真是恍然大悟、茅塞顿开啊。我没读多少书，没学过离散数学，呵呵。我觉得这个问题实在讨论得太有意义了。

这个问题其实并不只是PHP的问题，更多的是数据设计的问题，精巧的数据结构实在太重要了。

我开始也只想到用递归来处理，但效率实在太差。层次越多，效率越低。如果用先序遍历树算法(modified preorder tree traversal algorithm) 。则相对来说，层次越多，表现越好。呵呵呵呵。

唯一不爽的就是在编辑节点时比较麻烦。
shuke，能不能抽空写个树构造类，以后大家都用这个算啦。呵呵。
我试试看能不能完成，等我搞好了再贴。

 

关于标记任意的级别数据，我还是赞同采取编码标记法
比如，每级数据为四位数，饱合值9999，在编号存取方面，采用VChar值
“Num.”四位作为前缀，之后是一级编码，二级编码，三级编码。。。比如一条信息在第四级13号，那其编号就是“Num.0001000100010013”
递归列树则基础于检索时的条件限制，例如用“Num.xxxx%”作为关键字检索第一级的所有数据量，如果要把某一类置于另一个父类，只需要检索“Num.xxxxxxxx...”将前面的“Num.xxxx...”替换为父类的ID就OK了
另，有两点需要注意：
第一，这张数据表要有一个Max值表辅助，也就是要通过一个Max值，来记录每一个类已经存储的最大值；
第二，删除数据时不能真的删除，而是打上删除标记，在插入新纪录时update，有效的节约资源

本标记看似采用大数标记，其实属字串操作，不会耗太多的CPU资源，而设定索引后，配合左端定制右边通配符的条件检索，可以获得很高的效率

以上是偶在做某集团财务应用时采用的分公司标记法，这样，当某家分公司被调整时，可以很方便的实现大挪移。

声明，上面的讨论没有细读，是否文不对题的嫌疑...请指正