存储树形结构是一个很常见的问题，他有好几种解决方案。主要有两种方法：邻接列表模型和改进前序遍历树算法

在本文中，我们将探讨这两种保存层次数据的方法。我将举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下：

本文包含了一些代码的例子来演示如何保存和获取数据。我选择PHP [3]来写例子，因为我常用这个语言，而且很多人也都使用或者知道这个语言。你可以很方便地把它们翻译成你自己用的语言。

邻接列表模型(The Adjacency List Model)

我们要尝试的第一个——也是最优美的——方法称为“邻接列表模型”或称为“递归方法”。它是一个很优雅的方法因为你只需要一个简单的方法来在你的树中进行迭代。在我们的食品店中，邻接列表的表格如下：

如你所见，对每个节点保存一个“父”节点。我们可以看到“Pear [4]”是“Green”的一个子节点，而后者又是“Fruit”的子节点，如此类推。根节点，“Food”，则他的父节点没有值。为了简单，我只用了“title”值来标识每个节点。当然，在实际的数据库中，你要使用数字的ID。

显示树

现在我们已经把树放入数据库中了，得写一个显示函数了。这个函数将从根节点开始——没有父节点的节点——同时要显示这个节点所有的子节点。对于这些子节点，函数也要获取并显示这个子节点的子节点。然后，对于他们的子节点，函数还要再显示所有的子节点，然后依次类推。

也许你已经注意到了，这种函数的描述，有一种普遍的模式。我们可以简单地只写一个函数，用来获得特定节点的子节点。这个函数然后要对每个子节点调用自身来再次显示他们的子节点。这就是“递归”机制，因此称这种方法叫“递归方法”。

<?php
// $parent 是我们要查看的子节点的父节点
// $level 会随着我们深入树的结构而不断增加，
//        用来显示一个清晰的缩进格式
function display_children($parent, $level) {
    // 获取$parent的全部子节点
    $result = mysql_query('SELECT title FROM tree '.
                           'WHERE parent="'.$parent.'";'); 

    // 显示每个节点
    while ($row = mysql_fetch_array($result)) {
        // 缩进并显示他的子节点的标题
        echo str_repeat('  ',$level).$row['title']."\n"; 

        // 再次调用这个函数来显着这个子节点的子节点
        display_children($row['title'], $level+1);
    }
}
?>

要实现整个树，我们只要调用函数时用一个空字符串作为$parent 和$level = 0: display_children('',0); 函数返回了我们的食品店的树状图如下：

Food
  Fruit
    Red
      Cherry
    Yellow
      Banana
  Meat
    Beef
    Pork

注意如果你只想看一个子树，你可以告诉函数从另一个节点开始。例如，要显示“Fruit”子树，你只要display_children('Fruit',0); while ($row = mysql_fetch_array($result)) { // 检查栈里面有没有元素 if (count($right)>0) { // 检查我们是否需要从栈中删除一个节点 while ($right[count($right)-1]<$row['rgt']) { array_pop($right); } } // 显示缩进的节点标题 echo str_repeat(' ',count($right)).$row['title']."\n"; // 把这个节点添加到栈中 $right[] = $row['rgt']; } } ?>

节点的路径

利用差不多的函数，我们也可以查询某个节点的路径如果你只知道这个节点的名字或者ID。例如，“Cherry”的路径是“Food”>“Fruit”>“Red”。要获得这个路径，我们的函数要获得这个路径，这个函数必须从最深的层次开始：“Cheery”。但后查找这个节点的父节点，并添加到路径中。在我们的例子中，这个父节点是“Red”。如果我们知道“Red”是“Cherry”的父节点。

<?php
// $node 是我们要查找路径的那个节点的名字
function get_path($node) {
    // 查找这个节点的父节点
    $result =