Whether you want to build your own forum, publish the messages from a mailing list on your Website, or write your own cms: there will be a moment that yoursquo;ll want to store hierarchical data in a database. And, unless yoursquo;re using a XML-like database, tables arenrsquo;t hierarchical; theyrsquo;re just a flat list. Yoursquo;ll have to find a way to translate the hierarchy in a flat file.
Storing trees is a common problem, with multiple solutions. There are two major approaches: the adjacency list model, and the modified preorder tree traversal algorithm.
In this article, wersquo;ll explore these two methods of saving hierarchical data. Irsquo;ll use the tree from a fictional online food store as an example. This food store organizes its food by category, by colour and by type. The tree looks like this:
This article contains a number of code examples that show how to save and retrieve data. Because I use that language myself, and many other people use or know that language too, I chose to write the examples in PHP. You can probably easily translate them to your own language of choice.
The Adjacency List Model
The first, and most elegant, approach wersquo;ll try is called the lsquo;adjacency list modelrsquo; or the lsquo;recursion methodrsquo;. Itrsquo;s an elegant approach because yoursquo;ll need just one, simple function to iterate through your tree. In our food store, the table for an adjacency list looks like this:
As you can see, in the adjacency list method, you save the lsquo;parentrsquo; of each node. We can see that lsquo;Pearrsquo; is a child of lsquo;Greenrsquo;, which is a child of lsquo;Fruitrsquo; and so on. The root node, lsquo;Foodrsquo;, doesnrsquo;t have a parent value. For simplicity, Irsquo;ve used the lsquo;titlersquo; value to identify each node. Of course, in a real database, yoursquo;d use the numerical id of each node.
Give Me the Tree
Now that wersquo;ve inserted our tree in the database, itrsquo;s time to write a display function. This function will have to start at the root node — the node with no parent — and should then display all children of that node. For each of these children, the function should retrieve and display all the child nodes of that child. For these children, the function should again display all children, and so on.
As you might have noticed, therersquo;s a regular pattern in the description of this function. We can simply write one function, which retrieves the children of a certain parent node. That function should then start another instance of itself for each of these children, to display all their children. This is the recursive mechanism that gives the lsquo;recursion methodrsquo; its name.
lt;?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) {
// retrieve all children of $parent
$result = mysql_query(SELECT title FROM tree .
WHERE parent='.$parent.';);
// display each child
while ($row = mysql_fetch_array($result)) {
// indent and display the title of this child
echo str_repeat( ,$level).$row[title].'n';
// call this function again to display this
// childs children
display_children($row[title], $level 1);
}
}
?gt;
To display our whole tree, wersquo;ll run the function with an empty string as $parent and$level = 0: display_children(,0); For our food store tree, the function returns:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
Note that if you just want to see a subtree, you can tell the function to start with another node. For example, to display the lsquo;Fruitrsquo; subtree, you would run display_children(Fruit,0);
The Path to a Node
With almost the same function, itrsquo;s possible to look up the path to a node if you only know the name or id of that node. For instance, the path to lsquo;Cherryrsquo; is lsquo;Foodrsquo; gt; lsquo;Fruitrsquo; gt; lsquo;Redrsquo;. To get this path, our function will have to start at the deepest level: lsquo;Cherryrsquo;. It then looks up the parent of this node and adds this to the path. In our example, this would be lsquo;Redrsquo;. If we know that lsquo;Redrsquo; is the parent of lsquo;Cherryrsquo;, we can calculate the path to lsquo;Cherryrsquo; by using the path to lsquo;Redrsquo;. And thatrsquo;s given by the function wersquo;ve just used: by recursively looking up parents, wersquo;ll get the path to any node in the tree.
lt;?php
// $node is the name of the node we want the path of
function get_path($node) {
// look up the parent of this node
$result = mysql_query(SELECT parent FROM tree .
WHERE title='.$node.';);
$row = mysql_fetch_array($result);
// save the path in this array
$path = array();
// only continue if this $node isnt the root node
// (thats the node with no parent)
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;
}
?gt;
This function now returns the path to
剩余内容已隐藏，支付完成后下载完整资料
无论你是否想要建立自己的论坛，将邮件从你的网站上发布邮件列表，或者写你自己的项目：有一个时刻，你会想要在一个数据库中存储分层的数据。而且，除非你使用了一个类似的数据库，表是不分层的，它们只是一个列表。你必须找到一种方法来将层次结构转换为一个平面文件。
存储树是一个常见的问题，有多个解决方案。有两种主要的方法：邻接列表模型和改进前序遍历树算法。
在这篇文章中，我们将探讨这2种节省层次数据的方法。我将用一个虚构的网上商店的树作为一个例子。这家食品店按颜色分类，按类别分类。树看起来像这样：
本文包含了一些代码示例，该示例显示如何保存和检索数据。因为我使用自己的语言，和许多其他人使用或熟悉的那种语言，我选择用PHP编写的例子。你可以很容易地把他们翻译成你自己的语言。
邻接表模型
首先，最优雅的，我们会尝试的方法叫做“邻接表模型”或“递归方法”。这是一个优雅的方法，因为你只需要一个，遍历树的简单功能。在我们的食品店，一个邻接表的表看起来像这样：
正如你所看到的，在邻接表的方法中，你保存了每个节点的“父节点”。我们可以看到，梨是绿色的孩子节点，这是水果的孩子节点等。根节点，“食物”，没有一个父值。为了简单起见，我使用了“标题”值来识别每个节点。当然，在一个真实的数据库中，你会使用每个节点的数字标识。
给出树
现在，我们已经将树插入到数据库中，现在是时候写一个显示函数了。此功能将在根节点-没有父节点的节点上，然后显示该节点的所有子节点。对于每一个孩子，功能应该检索和显示所有的孩子节点的那个孩子。对于这些孩子，功能应再次显示所有的孩子，等等。
正如你可能已经注意到的，在这个函数的描述中有一个规则的模式。我们可以简单地写一个函数，它可以检索某个父节点的子节点。这一功能应为每一个孩子开始另一个实例，以显示他们所有的孩子。这是递归机制，给出了“递归方法”的名称。
lt;?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) {
// retrieve all children of $parent
$result = mysql_query(SELECT title FROM tree .
WHERE parent='.$parent.';);
// display each child
while ($row = mysql_fetch_array($result)) {
// indent and display the title of this child
echo str_repeat( ,$level).$row[title].'n';
// call this function again to display this
// childs children
display_children($row[title], $level 1);
}
}
?gt;
为了显示我们的整棵树，我们要运行的函数用一个空字符串作为 $parent and$level = 0: display_children(,0);我们的食品店树，函数返回：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
注意，如果你只想看子树，你可以告诉函数启动另一个节点。例如，要显示的水果树，你就运行display_children(Fruit,0);
节点的路径
几乎相同的功能，如果你只知道该节点的名称或标识，就可以查找一个节点的路径。例如，“樱桃”的路径是“食物”gt;“水果”gt;“红色”。要获得这条道路，我们的功能将必须从最深层次开始：“樱桃”。然后，它查找该节点的父节点，并将此添加到路径中。在我们的例子中，这将是“红色”。如果我们知道红色是樱桃的父母，我们可以通过使用“红色”的路径计算出樱桃的路径。这是由我们所使用的功能给出的：通过递归查找的父母，我们将得到的路径中的任何节点的树。
lt;?php
// $node is the name of the node we want the path of
function get_path($node) {
// look up the parent of this node
$result = mysql_query(SELECT parent FROM tree .
WHERE title='.$node.';);
$row = mysql_fetch_array($result);
// save the path in this array
$path = array();
// only continue if this $node isnt the root node
// (thats the node with no parent)
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;
}
?gt;
这个函数现在返回给定节点的路径。它返回的路径作为一个数组，所以要显示的路径我们可以用print_r（get_path（cherry ））；如果你这样做的“樱桃”，你会看到：
Array
(
[0] =gt; Food
[1] =gt; Fruit
[2] =gt; Red
)
缺点
正如我们刚刚看到的，这是一个伟大的方法。这很容易理解，我们需要的代码是简单的。那么，是邻接列表模型的缺点？在大多数编程语言中，它的速度慢，效率低。这主要是由递归造成的。我们需要一个数据库查询树中的每个节点。
由于每个查询需要一段时间，这使得处理大树时的功能非常慢。
其次这个方法不是很快，你很可能会使用编程语言。不像如LISP语言，大多数语言的设计不是递归函数。对于每个节点，该函数开始另一个实例。所以，对于一个有四个层次的树，你将在同一时间运行四个功能的实例。由于每个函数占用一片内存，并且需要一段时间来启动，当应用到大的树时，递归是很慢的。
现在，让我们来看看另一种储存树的方法吧。递归可能很慢，所以我们宁愿不使用递归函数。我们也想尽量减少数据库查询的数量。最好，我们只对每一个活动都有一个查询。
我们将以一种水平的方式开始我们的树。在根节点开始（food ），写一个1左。按照树的“水果”，写下2个旁边。这样，你就沿着树的边走（遍历），同时在每个节点的左、右侧写一个数字。最后一个数字是在“食物”节点的右边写的。在这个图像中，你可以看到整个数字的树，和几个箭头表示编号顺序。
我们会把这些数字称为左，右（如食物的左值为1，正确值为18）。正如你所看到的，这些数字表明了每个节点之间的关系。因为“红色”有数字3和6，它的“食物”结子1-18。以同样的方式，我们可以说，所有节点的左值大于2和右边的值小于11，是2-11水果后裔。树结构现在存储在左，右值。该走的树和计算节点的方法称为先根遍历树算法。
在我们继续之前，让我们看看这些值在我们的表：
注意单词“左”和“右”有SQL中的特殊意义。因此，我们必须用“lft”和“rgt”来识别柱。还请注意，我们不需要“parent”栏了。我们现在有了LFT和RGT值存储树结构。
检索树
如果你想使用一个带有左、右值的表来显示树，你首先必须确定要检索的节点。例如，如果你想要的水果树，你必须只选择节点2和11之间的左的价值。在SQL中，那将是：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
结果返回
好的，有一个完整的树在一个查询。要显示这棵树，就像我们做递归函数一样，我们必须在这个查询中添加一个命令。如果您在表中添加和删除行，您的表可能不会是正确的。因此，我们应该以其左值的顺序排列成行。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
留下的唯一问题是缩进。
要显示的树结构，孩子节点应缩进比它们的父母节点稍多。我们可以通过保持正确的价值观一叠做到这一点。每次启动一个节点的孩子时，您添加节点堆栈的权值。你知道该节点的所有孩子有正确的价值小于父权价值，因此通过比较堆栈中的最后一个右节点当前节点的正确的价值，你可以看到，如果你还在显示该家长的孩子。当您完成显示节点，从栈中删除其正确的价值。如果算上在堆栈中的元素，你会得到当前节点的级别。
lt;?php
function display_tree($root) {
// retrieve the left and right value of the $root node
$result = mysql_query(SELECT lft, rgt FROM tree .
WHERE title='.$root.';);
$row = mysql_fetch_array($result);
// start with an empty $right stack
$right = array();
// now, retrieve all descendants of the $root node
$result = mysql_query(SELECT title, lft, rgt FROM tree .
WHERE lft BETWEEN .$row[lft]. AND .
$row[rgt]. ORDER BY lft ASC;);
// display each row <b
剩余内容已隐藏，支付完成后下载完整资料</b
资料编号：[28689]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、开题报告、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
