文档章节

php利用多叉树(平衡树)的方式构建无限分类

酒逍遥
 酒逍遥
发布于 2013/07/26 14:20
字数 1235
阅读 1195
收藏 25

说起无限分类..大多数的结构都是  id   name   parent_id  这种模式.整个结构比较简单清晰.要构建和更新整个分类也比较容易.但是查询起来就会非常的麻烦.经常会用到递归的算法.例如 获取某个节点的所有父节点之类.

今天说一说通过多叉树的方式构建无限分类,结构上可能会复杂一点,构建和更新也比较麻烦.但是查询非常方便.两种方法的优劣就不评论了.

先看一张图

这是我们要构建的无限分类的模型. 电子产品是最大的分类.家用电器 ,数码产品是其子分类.可以看到子分类是被父分类包含起来的.每个分类都有左右 两个节点编号分别是1、2、3.....

根据上面的图mysql中建立表和插入数据

CREATE TABLE  `product_categories` (

`id` MEDIUMINT( 8 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,

`name` VARCHAR( 20 ) NOT NULL ,

`left_node` MEDIUMINT( 8 ) NOT NULL ,

`right_node` MEDIUMINT( 8 ) NOT NULL

) ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_general_ci;


INSERT INTO `product_categories` (`id`, `name`, `left_node`, `right_node`) VALUES

(1, '电子产品', 1, 20),

(2, '家用电器', 2, 9),

(3, '电视机', 3, 4),

(4, '电冰箱', 5, 6),

(5, '空调', 7, 8),

(6, '数码产品', 10, 19),

(7, '电脑', 11, 18),

(8, '台式电脑', 12, 13),

(9, '笔记本电脑', 14, 15),

(10, '平板电脑', 16, 17);

表结构如下:

下面是PHP的实例代码:

1、获取所有节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT c.name FROM product_categories as c, product_categories as p
WHERE c.left_node BETWEEN p.left_node AND p.right_node
AND p.name='电子产品' ORDER BY c.left_node");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);

foreach($rs as $v){
	echo $v['name'].'<br />';
}
输出:

电子产品

家用电器

电视机

电冰箱

空调

数码产品

电脑

台式电脑

笔记本电脑

平板电脑

2、 获取某个父节点以及其所有子节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT c.name FROM product_categories as c, product_categories as p
WHERE c.left_node BETWEEN p.left_node AND p.right_node
AND p.name='数码产品' ORDER BY c.left_node");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);

foreach($rs as $v){
	echo $v['name'].'<br />';
}

输出:

数码产品

电脑

台式电脑

笔记本电脑

平板电脑

3、获取所有的叶子节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT name FROM product_categories where right_node-left_node=1");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);

foreach($rs as $v){
	echo $v['name'].'<br />';
}

输出:

电视机

电冰箱

空调

台式电脑

笔记本电脑

平板电脑

4、获取某个子节点及其所有父节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT p.name FROM product_categories AS c, product_categories AS p WHERE c.left_node BETWEEN p.left_node AND p.right_node AND c.name = '平板电脑' ORDER BY p.left_node");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);

foreach($rs as $v){
	echo $v['name'].'<br />';
}
输出:

电子产品

数码产品

电脑

平板电脑

5、获取所有节点极其所处的层级

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT c.name, (COUNT(p.name) - 1) AS level FROM product_categories AS c, product_categories AS p WHERE c.left_node BETWEEN p.left_node AND p.right_node GROUP BY c.name ORDER BY c.left_node");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
var_dump($rs);
echo '<br />';
foreach($rs as $v){
	echo $v['name'].' level:'.$v['level'].'<br />';
}
输出:

电子产品 level:0
家用电器 level:1
电视机 level:2
电冰箱 level:2
空调 level:2
数码产品 level:2
电脑 level:2
台式电脑 level:3
笔记本电脑 level:3
平板电脑 level:3


6、获取某个节点的层级

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

$stmt = $pdo->prepare("SELECT c.name, (COUNT(p.name) - 1) AS level FROM product_categories AS c, product_categories AS p WHERE c.left_node BETWEEN p.left_node AND p.right_node and c.name='平板电脑' GROUP BY c.name ORDER BY c.left_node");

$stmt->execute();

$rs=$stmt->fetchAll(PDO::FETCH_ASSOC);
var_dump($rs);
echo '<br />';
foreach($rs as $v){
	echo $v['name'].' level:'.$v['level'].'<br />';
}
输出:

平板电脑 level:3

7、在某个节点后平行的插入一个节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

function addNode($left_node,$new_node){
    global $pdo;
    $stmt = $pdo->prepare("SELECT right_node FROM product_categories WHERE name = '$left_node'");
    $stmt->execute();
    $rs=$stmt->fetch(PDO::FETCH_ASSOC);
    $right_node=$rs['right_node'];
    $pdo->exec("UPDATE product_categories SET right_node = right_node + 2 WHERE right_node > $right_node");
    $pdo->exec("UPDATE product_categories SET left_node = left_node + 2 WHERE left_node > $right_node");
    $pdo->exec("INSERT INTO product_categories(name, left_node, right_node) VALUES('$new_node', $right_node + 1, $right_node + 2)");
}

addNode('家用电器','办公用品');
完成之后表结构如下:


8、删除某个节点及其所有子节点

<?php
$pdo = new PDO(
    'mysql:host=localhost;dbname=test',
    'root',
    ''
);

$pdo->exec("SET NAMES UTF8");

function deleteNode($node_name){
	global $pdo;
    $stmt = $pdo->prepare("SELECT left_node,right_node, right_node - left_node + 1 as width FROM product_categories WHERE name ='$node_name'");
    $stmt->execute();
	$rs=$stmt->fetch(PDO::FETCH_ASSOC);
	$left_node=$rs['left_node'];
	$right_node=$rs['right_node'];
	$width=$rs['width'];
    $pdo->exec("DELETE FROM product_categories WHERE left_node BETWEEN $left_node AND $right_node");
    $pdo->exec("UPDATE product_categories SET right_node = right_node - $width WHERE right_node > $right_node");
    $pdo->exec("UPDATE product_categories SET left_node = left_node - $width WHERE left_node > $right_node");
}
deleteNode('数码产品');
完成之后表结构如下:


可以看到用多叉树的方式构建无限分类,查询的时候是非常简便的.但是在插入新的节点和删除节点时就比较麻烦了.


© 著作权归作者所有

共有 人打赏支持
酒逍遥

酒逍遥

粉丝 48
博文 40
码字总数 35454
作品 0
武汉
高级程序员
私信 提问
利用内存多叉树实现Ext JS中的无限级树形菜单(一种构建多级有序树形结构JSON的方法)

利用内存多叉树实现Ext JS中的无限级树形菜单(一种构建多级有序树形结构JSON的方法) 一、问题研究的背景和意义 目前在Web应用程序开发领域,Ext JS框架已经逐渐被广泛使用,它是富客户端开...

星星知我心
2012/01/30
3.1K
4
Leetcode——二叉树常考算法整理

二叉树常考算法整理 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法项目点star呀~~ 前言 二叉树即...

qq_32690999
05/28
0
0
小蚂蚁学习数据结构(34)——平衡二叉树的概念

平衡二叉树的作用 由于二叉排序树的结构可能不平衡,导致对树的运算的时间复杂度增加。 调整二叉排序树的结构,使其始终成为平衡的状态——平衡二叉树。 平衡二叉树的定义 若一个二叉树中每个...

嗜学如命的小蚂蚁
2016/02/09
198
0
看图轻松理解数据结构与算法系列(AVL树)

前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等...

超人汪小建
08/09
0
0
平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134
2017/06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

正则表达式匹配不包含

^((?!xxx).)*$

安小乐
6分钟前
1
0
python Windows tkinter应用开发3 列出目录的所有文件

在本章中,我们将编写程序来执行此操作。 1)选择文件夹。 2)在UI的标签部分打印该文件夹中的所有文件名(带文件扩展名)。 首先,修改selectFile函数以打开文件夹。主文件如下: from tki...

python测试开发人工智能安全
8分钟前
1
0
使用Laya引擎开发微信小游戏(上)

  使用一个简单的游戏开发示例,由浅入深,介绍了如何用Laya引擎开发微信小游戏。      img      作者:马晓东,腾讯前端高级工程师。      微信小游戏的推出也快一年时间了,...

SEOwhywhy
13分钟前
1
0
react程序开发问题记录

1、webpack.config.dev.js文件的publicpath配置

teamlog
25分钟前
2
0
javascript 值转换为布尔值

任意javascript 的值都可以转换为布尔值。 特别是在 if() 等判断中使用的时候: 下面这些值会被转换为 false undefined , null , 0 , -0 , NaN , "" 空字符串 来自 JavaScript 权威指南 书籍...

之渊
28分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部