文档章节

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

酒逍遥
 酒逍遥
发布于 2013/07/26 14:20
字数 1235
阅读 1391
收藏 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('数码产品');
完成之后表结构如下:


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


© 著作权归作者所有

酒逍遥

酒逍遥

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

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

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

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

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

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

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

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

超人汪小建
2018/08/09
0
0
红黑树,超强动静图详解,简单易懂

写在前面 红黑树,对很多童鞋来说,是既熟悉又陌生。学校中学过,只了解大概;工作中不怎么使用,但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。没错,本...

tan日拱一兵
07/24
38
0

没有更多内容

加载失败,请刷新页面

加载更多

zk中快速选举FastLeaderElection实现

选举涉及概念 服务器状态 投票 如何选择投票? 协议 选举 如何进行选举? epoch 发送者 接收者 发送队列 接收队列 服务器状态 public enum ServerState { LOOKING,寻找Leader状态,当服务处于...

writeademo
刚刚
0
0
Knowage 6.2安装部署

注意:需要正确配置JAVA_HOME和JRE_HOME还有catalina_home,否则启动的时候tomcat一闪而过,想要获得报错信息,可以打开cmd,在dos命令行运行开始命令 官网:https://www.knowage-suite.com/s...

阿伦哥-
2分钟前
0
0
c++11 左值引用和右值引用

#include <iostream>using namespace std;void Print(string& s){ cout << s;}int main(){ string s="abc"; Print(s); // OK Print("abc"); // parse error......

SibylY
4分钟前
0
0
浅谈Facade外观模式

一、前言 外观模式是一种非常简单的模式,简单到我们经常都会使用,比如对于类A和B,如果两者需要交互,经过一定的处理过程才能实现某一个具体的功能,那么我们可以将这个处理的过程定义为一...

青衣霓裳
4分钟前
0
0
AnalyticDB for PostgreSQL 6.0 新特性介绍

阿里云 AnalyticDB for PostgreSQL 为采用MPP架构的分布式集群数据库,完备支持SQL 2003,部分兼容Oracle语法,支持PL/SQL存储过程,触发器,支持标准数据库事务ACID。ADB PG通过行存储、列存...

Mr_zebra
6分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部