无限级分类[预排序遍历树算法]
预排序遍历树算法
现在让我们看一看另外一种不使用递归计算,更加快速的方法,这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的手指)。
这些数字标明了各个节点之间的关系,"Red"的号是3和6,它是 "Food" 1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点
以下是代码: 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
复制代码这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。
以下是代码: +----------+------------+-----+-----+
| 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"字段来表示树状结构。也就是 说下面这样的表结构就足够了。
以下是代码: +------------+-----+-----+
| 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;
复制代码这个查询得到了以下的结果。
以下是代码: +------------+-----+-----+
| 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;
复制代码剩下的问题如何显示层级的缩进了。
以下是代码:
<?php
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;
复制代码这样就会得到以下的结果:
以下是代码: +------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
复制代码那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2 descendants = (right – left - 1) / 2
复制代码不相信?自己算一算啦。
用这个简单的公式,我们可以很快的算出"Fruit 2-11"节点有4个子孙节点,而"Banana 8-9"节点没有子孙节点,也就是说它不是一个父节点了。
很神奇吧?虽然我已经多次用过这个方法,但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法,但是有什么办法能够帮我们建立这样有左右值的数据表呢?这里再介绍一个函数给大家,这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码:
<?php
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语句会变得更加简单。
<?php
@session_start();
require_once("../Inc/Conn.php");
require_once("../Inc/function.php");
$filepath = '../userhead/';
$filename = time().mt_rand(10,100);
//$uid = get_id($_SESSION['uname']);
$uid = 14;
if (isset($GLOBALS["HTTP_RAW_POST_DATA"]))
{
$im = $GLOBALS["HTTP_RAW_POST_DATA"];
if( !is_dir( $filepath ) )
{
mkdir($filepath,0777);
}
if(file_put_contents($filepath.$filename.'.jpg',$im))
{
$path = 'http://'.$_SERVER['HTTP_HOST'].'/userhead/'.$filename.'.jpg';
savaPath($path);
}
else
{
ShowMsg('result:false');
}
}
function savaPath($path)
{
global $uid;
$sql = "Insert into dd(oy_uid,oy_dsp,oy_path) value('$uid','','$path')";
if( mysql_query( $sql ) )
{
ShowMsg('result:true');
}
else
{
ShowMsg('result:false'.mysql_error());
}
}
?>
本站原创转载注明:www.111cn.net/phper/php.html
无限级分类一般是对于商品或站品分类来做的下面我们就来看一下关于使用递归法的算法与代码吧。<?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
下面的一段代码是一段简单的php+json用户注册返回json数据哦,因为在做flash互动时经常会用到flash与json数据交换哦,我们所用php实时返回并且输出json<?php
require_once("../Inc/Conn.php");
require_once("../Inc/function.php");
/*
接收flash post 数据
Date"2009.04.24
*/
$User_Name = Get_value('User_name',1);
$User_Pass = Get_value('User_Pass',1);
$Puser_Pass = Get_value('Puser_Pass',1);
$User_Mail = Get_value('User_Mail',1);
$User_Baby_Sex = Get_value('User_Baby_Sex',1);
$year = Get_value('year',1);
$month = Get_value('month',1);
$day = Get_value('day',1);
$User_Prov = Get_value('User_Prov',1);
$User_City = Get_value('User_City',1);
$User_rname = Get_value('User_rname',1);
$User_Zip = Get_value('User_Zip',1);
$User_Hand = Get_value('User_Hand',1);
$User_YesNo = Get_value('User_YesNo',1);
$User_Address = Get_value('User_Address',1);
if( empty( $User_Name ) || strlen( $User_name ) >8 ){
ShowMsg("{"result":"false"}");
}elseif( empty( $User_Pass ) || ( $User_Pass != $Puser_Pass ) ) {
ShowMsg("{"result":"false"}");
}elseif( !@preg_match("/w+([-+.]w+)*@w+([-.]w+)*.w+([-.]w+)*/",$User_Mail) || strlen($User_Mail)<6 ){
ShowMsg("{"result":"false"}");
}elseif( empty( $User_Prov ) || empty( $User_City ) ){
ShowMsg("{"result":"false"}");
}elseif( !empty( $User_rname ) ){
if( strlen( $User_rname )> 6){
ShowMsg("{"result":"false"}");
}
}
if( !empty( $User_Address )){
if( strlen( $User_Address )>100 ){
ShowMsg("{"result":"false"}");
}
}
if( !empty( $User_Zip ) ){
if( !strlen( $User_Zip )== 6 || !is_numeric( $User_Zip )){
ShowMsg("{"result":"false"}");
}
}
if( is_numeric( $User_Hand ) ){
if( !@preg_match("/d{11}/",$User_Hand) ){
ShowMsg("{"result":"false"}");
}
}
$User_Baby_Birth =@iconv('utf-8','gb2312',"$year 年 $month 月 $day 日");
$sheng = @iconv('utf-8','gb2312',$User_Prov.$User_City);
$sql ="Insert into tablename(User_Name,User_Pass,User_Mail,User_Baby_Sex,User_Baby_Birth,sheng,User_Zip,User_Address,";
$sql.="User_Hand,User_YesNo,User_rname) values('$User_Name','$User_Pass','$User_Mail','$User_Baby_Sex','$User_Baby_Birth',";
$sql.="'$sheng','$User_Zip','$User_Address','$User_Hand','$User_YesNo','$User_rname')";
$sqlUser ="select User_Name from tablename where User_Name='$User_Name'";
$result = mysql_query( $sqlUser ) or die(mysql_error().$sqlUser);
if( mysql_num_rows( $result ) ){
ShowMsg("{"result":"false"}");
}else{
if( mysql_query( $sql ) ){
$outPut ="{
"Id":".mysql_insert_id().",n
"User_Name":"$User_Name",n
"User_Mail":"$User_Mail",n
"User_Baby_Sex":"$User_Baby_Sex",n
"User_Baby_Birth":"$User_Baby_Birth",n
"sheng":"$sheng",n
"User_Zip":"$User_Zip",n
"User_Address":"$User_Address",n
"User_Hand":"$User_Hand",n
"User_YesNo":"$User_YesNo",n
"User_rname":"$User_rname",n
"result":"true"
}";
ShowMsg($outPut);
}else{
ShowMsg("{"result":"false"}");
}
}
?>
本站原创转载注明: http://www.111cn.net/phper/php.html
关于这两个函数他们有一个区别就是mt_rand效率要高到rand哦。mt_rand与rand函数区别与实例
下面我们来看看mt_rand函数的实例吧。
function roll () {
return mt_rand(1,6);
}
echo roll();
function roll ($sides) {
return mt_rand(1,$sides);
}
echo roll(6); // roll a six-sided die
echo roll(10); // roll a ten-sided die
echo roll(20); // roll a twenty-sided die
再看一个rand函数的实例吧。
function cn111 () {
return rand(1,6);
}
echo cn111();
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
- 无限级分类在开发中经常使用,例如:部门结构、文章分类。无限级分类的难点在于“输出”和“查询”,例如 将文章分类输出为<ul>列表形式; 查找分类A下面所有分类包含的文章。1.实现原理 几种常见的实现方法,各有利弊。其中...2015-10-23
- 在一些复杂的系统中,要求对信息栏目进行无限级的分类,以增强系统的灵活性。那么PHP是如何实现无限级分类的呢?我们在本文中使用递归算法并结合mysql数据表实现无限级分类。 递归,简单的说就是一段程序代码的重复调用,当把...2015-10-23
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-05-20- ecshop商品无限级分类代码 function cat_options($spec_cat_id, $arr) { static $cat_options = array(); if (isset($cat_options[$spec_cat_id]))...2016-11-25
- 这篇文章主要介绍了c# 遍历 Dictionary的四种方式,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2020-12-08
jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结
借助jQuery我们可以轻松地堆DOM元素进行向上、向下遍历以及同级的遍历,本文我们即来整理jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结:...2016-07-25- 下面就为大家带来一篇jquery对Json的各种遍历方法总结(必看篇)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-10-02
- 这篇文章主要介绍了C# 遍历datatable字段名和value的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-19
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要为大家详细介绍了JS中的二叉树遍历,何为二叉树,什么是二叉树的遍历,感兴趣的小伙伴们可以参考一下...2016-03-22
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了Xml中使用foreach遍历对象实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-12-04
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要给大家介绍了关于JavaScript循环遍历的24个方法,文中对每种方法都给出了详细的实例代码,方便大家理解学习,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2021-09-15
- Go 语言提供的基础容器,免不了要查询容器中的数据,那么是如何实现遍历的呢?本文将会介绍几种常用容易的遍历及其使用。感兴趣的可以了解一下...2021-06-13