文档章节

预排序遍历树算法(modified preorder tree traversal algorith

mac_zhao
 mac_zhao
发布于 2015/06/25 11:22
字数 645
阅读 425
收藏 5
这个算法有如下几个数据结构:
1、lft 代表左 left
2、rgt 代表右 right
3、lvl 代表所在的层次 level
下面这个图是一个典型的结构:

 

 我们先看一些使用方法

1、查看整个树(A)有多少节点(包含自己),直接看根节点就行了 (right-left+1)/2 = (20-1+1)/2 = 10

   这个数有10个节点

2、查看从节点A到E的路径

   1 select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft

 

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

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

  反向也是一样的,可以拿到底部一个节点,到上级节点的路径

  1 select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft desc

 

  唯一的区别就是排序是反向的就行了。

3、得到某个节点下面的所有节点,且按照树状结构返回我们用B做例子

  1 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的。

  1 select * from tree where lft>2 and right<11 and lvl<=3 order by lft

 

  下面看我们新增加一个节点的方法。我们在根节点的下面,G节点的右侧增加一个X节点

 

我们要做的工作就是

1、G节点的右参数为13

2、变更所有的受影响的节点,给新节点腾出空位子,所有左节点比G节点大的,都增加2

   1 update tree set lft=lft+2 where lft>12

 

   所有右节点比G节点大的,都增加2

  1 update tree set rgt=rgt+2 where rgt>13

 

3、新节点放在空位子上,lft=14,rgt=15,这样就完成了一个新节点的增加操作。

算法说明:

1.所有分类 左边和右边的值 > 插入节点的左边节点记录的右值 的全部 + 2

2.插入节点 左值 = 插入位置左边节点记录的右值 + 1, 右值 = 插入位置左边节点记录的右值 + 2

  

 其它相关说明请参考:

 http://be-evil.org/tb.php?sc=67fcc&id=168

  http://blog.csdn.net/wisewillpower/archive/2008/04/19/2306461.aspx

© 著作权归作者所有

共有 人打赏支持
mac_zhao
粉丝 42
博文 249
码字总数 304671
作品 0
普陀
程序员
私信 提问
树状分类结构,数据库构建(预排序历遍算法)

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

liangyx
2013/01/02
0
6
PHP+Mysql树型结构(无限分类)数据库设计的2种方式实例

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

我心中有猛狗
2016/10/29
43
0
HDU 1710 Binary Tree Traversals

Binary Tree Traversals   A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtre......

suvvm
2018/11/04
0
0
Leetcode 二叉树解题报告

1. Binary Tree Preorder Traversal Description Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Analy......

BookThief
2018/07/29
0
0
如何用数据库保存多级结构的数据

产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供...

xiao刀
2015/10/17
124
0

没有更多内容

加载失败,请刷新页面

加载更多

2亿用户背后的Flutter应用框架Fish Redux

背景 在闲鱼深度使用 Flutter 开发过程中,我们遇到了业务代码耦合严重,代码可维护性糟糕,如入泥泞。对于闲鱼这样的负责业务场景,我们需要一个统一的应用框架来摆脱当下的开发困境,而这也...

阿里云官方博客
22分钟前
2
0
C++生成随机数:高斯/正态分布(gaussian/normal distribution)

高斯分布也称为正态分布(normal distribution)。 常用的成熟的生成高斯分布随机数序列的方法由Marsaglia和Bray在1964年提出,C++版本如下: #include <stdlib.h>#include <math.h> d...

天蚕宝衣
25分钟前
1
0
从 Jenkins 迁移到 Jenkins X:一场持续交付之旅

背景 在 dailymotion,我们信奉 DevOps 最佳实践,并且重度使用了 Kubernetes。我们的部分产品(并非全部)已经部署在 Kubernetes 上。在迁移我们的广告技术平台时,为了赶时髦(作者你这么直...

微笑向暖wx
29分钟前
2
0
Kafka Producer Consumer

Producer API org.apache.kafka.clients.producer.KafkaProducer 如果想学习Java工程化、高性能及分布式、深入浅出。微服务、Spring,MyBatis,Netty源码分析的朋友可以加我的Java高级交流:...

编程SHA
37分钟前
1
0
在centos上搭建git服务器并自动同步代码

在centos上搭建git服务器并自动同步代码 tortoisegit git centos linux 5k 次阅读 · 读完需要 15 分钟 0 参考文章 CentOS安装Git实现多人同步开发 centos中GIT服务器搭建及使用密钥连接 简述...

linjin200
38分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部