文档章节

预排序遍历树算法的图文解释

BearCatYN
 BearCatYN
发布于 2015/04/28 16:12
字数 548
阅读 780
收藏 2

这个算法有如下几个数据结构 
1 lft 代表左 left 
2 rgt 代表右 right 
3 lvl 代表所在的层次 level 

下面这个图是一个典型的结构 
 

我们先看一些使用方法 
1 查看整个树(A)有多少节点(包含自己) 
直接看根节点就行了 (right-left+1)/2 = (20-1+1)/2 = 10 
这个数有10个节点 

2 查看从节点A到E的路径 
select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft 

得到的结果是A,B,D,E 这4个节点的数据,且按照访问路径的顺序 

如果2个节点之间不是上下级的关系,则查询没有结果 

反向也是一样的,可以拿到底部一个节点,到上级节点的路径 
select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft desc 
唯一的区别就是排序是反向的就行了。 

3 得到某个节点下面的所有节点,且按照树状结构返回 
我们用B做例子 
select * from tree where lft>2 and right<11 order by lft 
拿到的结果是 C,D,E,F,而且顺序也是正确的。 

4 拿到所有下2级的子节点 
我们A做例子,这次加上了lvl的参数,因为A的level是1,所以我们查询level不大于3的。 
select * from tree where lft>2 and right<11 and lvl<=3 order by lft 



下面看我们新增加一个节点的方法。 
我们在根节点的下面,G节点的右侧增加一个X节点 
 
我们要做的工作就是 
1 G节点的右参数为13 
2 变更所有的受影响的节点,给新节点腾出空位子 
所有左节点比G节点大的,都增加2 
update tree set lft=lft+2 where lft>12 
所有右节点比G节点大的,都增加2 
update tree set rgt=rgt+2 where rgt>13 
3 新节点放在空位子上,lft=14,rgt=15 
这样就完成了一个新节点的增加操作。

本文转载自:http://blog.chinaunix.net/uid-21586638-id-3875107.html

共有 人打赏支持
BearCatYN
粉丝 26
博文 158
码字总数 11947
作品 0
朝阳
程序员
PHP+Mysql树型结构(无限分类)数据库设计的2种方式实例

我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种: 1. 领接表的方式; 2. 预排序遍历树方式; 假设树状结构如下图: 领接表方式 ...

我心中有猛狗
2016/10/29
43
0
树状分类结构,数据库构建(预排序历遍算法)

树状结构的数据保存在数据库中的常用方法有一下两种: 1、邻接表(adjacency list model) 2、预排序遍历树算法(modified preorder tree traversal algorithm) 用一下的例子讨论这两种方法的差...

liangyx
2013/01/02
0
6
算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充

接着来搞树! 支持云栖社区,也希望大家能支持下我的独立博客——白水东城 文章地址: 算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充 一、B+树 B+树的特征 有k个子树的中...

kissjz
08/16
0
0
python机器学习案例系列教程——LightGBM算法

全栈工程师开发手册 (作者:栾鹏) python教程全解 安装 gitup网址:https://github.com/Microsoft/LightGBM 中文教程 http://lightgbm.apachecn.org/cn/latest/index.html lightGBM简介 xg...

luanpeng825485697
05/08
0
0
机器学习基础之 三大神器GBDT、XGBoost、LightGBM

本文主要简要的比较了常用的boosting算法的一些区别,从AdaBoost到LightGBM,包括AdaBoost,GBDT,XGBoost,LightGBM四个模型的简单介绍,一步一步从原理到优化对比。 AdaBoost原理 原始的AdaBo...

secondlieutenant
04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Docker学习笔记

Docker Resources All In One Docker 学习资源整理

OSC_fly
11分钟前
3
0
Android 安全逆向:篡改你的位置信息

篡改你的位置信息

蔡小鹏
11分钟前
1
0
SpringMVC 全局异常处理,返回json

1.在spring-mvc.xml中增加配置: 比如我的freemarker视图定义的是:/WEB-INF/template 我的页面则放在template下的common目录下,所以下方定义的是common/500,文件扩展名根据视图定义可以忽...

Gmupload
12分钟前
2
0
一篇文章搞定前端面试

本文旨在用最通俗的语言讲述最枯燥的基本知识 面试过前端的老铁都知道,对于前端,面试官喜欢一开始先问些HTML5新增元素啊特性啊,或者是js闭包啊原型啊,或者是css垂直水平居中怎么实现啊之...

Jack088
19分钟前
3
0
ajax 轮询请求后台服务器

<script type="text/javascript"> // var i=0; //声明轮询次数变量 $(document).ready(function(){ c = window.setInterval("getResult()",10000); //间隔多少秒去触发ajax }); function get......

15834278076
22分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部