文档章节

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

BearCatYN
 BearCatYN
发布于 2015/04/28 16:12
字数 548
阅读 794
收藏 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
朝阳
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
12/01
0
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

没有更多内容

加载失败,请刷新页面

加载更多

git常用命令

首先打开git bash方式可以直接鼠标右击 或者在开始菜单(windows系统,苹果暂时不要问我,等我有钱买苹果电脑告诉你们0.0) 打开界面如下 1.查看远程仓库地址 git remote -v 2.创建本地分支 ...

熊小熊会写代码哦
7分钟前
1
0
离屏Canvas — 使用Web Worker提高你的Canvas运行速度

现在因为有了离屏Canvas,你可以不用在你的主线程中绘制图像了! Canvas 是一个非常受欢迎的表现方式,同时也是WebGL的入口。它能绘制图形,图片,展示动画,甚至是处理视频内容。它经常被用...

嫣然丫丫丫
9分钟前
1
0
SpringBoot 整合 BeetlSQL

SpringBoot 整合 BeetlSQL 1. beetlsql介绍 BeetSql是一个全功能DAO工具, 同时具有Hibernate 优点 & Mybatis优点功能,适用于承认以SQL为中心,同时又需求工具能自动能生成大量常用的SQL的应...

Jeff_Regan
10分钟前
1
0
UNIGUI-DBGRID的统计行的使用

关键步骤: 1、设置DBGRID的summary.enabled:=true 2、打开DBGRID的columns字段,设置DBGRID对应的column的showsummary:=true; 3、写入uniDBGRID.onColumnSummary事件: procedure TframeCa......

dillonxiao
12分钟前
1
0
MySQL语法速查1:基础命令篇

[TOC] 1.1. 关于 SQL SQL 是 Structure Query Language(结构化查询语言)的缩写,是关系型数据库的基本语言,由 IBM 在 20 世纪 70 年代开发出来,作为 IBM 关系数据库原型 System R 的原型...

whoru
17分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部