文档章节

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

mac_zhao
 mac_zhao
发布于 2015/06/25 11:22
字数 645
阅读 340
收藏 5
点赞 0
评论 0
这个算法有如下几个数据结构:
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
粉丝 41
博文 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
如何用数据库保存多级结构的数据

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

xiao刀
2015/10/17
124
0
通过前序和中序遍历构造二叉树

原题   Given preorder and inorder traversal of a tree, construct the binary tree.   Note:   You may assume that duplicates do not exist in the tree. 题目大意   给定一个前......

一贱书生
2016/12/21
0
0
ZOJ Problem Set - 1944 Tree Recovery(二叉树三种遍历知二求三)

Tree Recovery Time Limit: 2 Seconds Memory Limit: 65536 KB Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary......

hushhw
2017/11/27
0
0
Leetcode——二叉树常考算法整理

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

qq_32690999
05/28
0
0
mysql左右值无限分类原理及实现

无限分类是我们开发中非常常见的应用,我们最常见最简单的方法就是在MySql里id ,name,f_id。优点是简单,结构简单。缺点是效率不高,因为每一次递归都要查询数据库,几百条数据库时就不是很快...

吴朝辉
2013/03/12
0
5
左右值无限分类实现算法

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

bengozhong
2016/09/09
5
0
【转】左右值无限分类实现算法

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

王二铁
2011/11/01
0
0
Leetcode144——Binary Tree Preorder Traversal

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree , return . ......

Quincuntial
2017/03/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java IO类库之ObjectInputStream和ObjectOutPutStream

一、ObjectOutputStream 1 - ObjectOuputStream介绍 ObjectOutputStream(对象字节输出流),用于将一个序列化对象写入到创建ObjectOutputStream时传入的底层字节输入流中,通过源码可知该类继...

老韭菜
12分钟前
0
0
17.TCP:传输控制协议

介绍 TCP和UDP使用同一网络层(IP),但TCP提供了面向连接、可靠的传输层服务 TCP传输给IP层的信息单位称为报文段或段 TCP通过如下方式保证可靠性: 应用数据被分割成TCP认为最合适发送的数据...

loda0128
21分钟前
0
0
重装Oracle时出现environment variable "PATH"错误的解决办法

在win7 64位下重新安装oracle 11g,一直报environment variable "PATH"的错误,按说明将path里多余的路径删除,但没办法解决。选择忽略错误继续安装,装一半会报CRC错误,还是安装失败。最好...

良言
27分钟前
0
0
TensorFlow 全连接的mnist

全连接的mnist import tensorflow as tf# 导入 MINST 数据集from tensorflow.examples.tutorials.mnist import input_datamnist = input_data.read_data_sets("MNIST_data/", one_ho......

阿豪boy
27分钟前
0
0
JAVA 三种WebService 规范

JAVA 中共有三种WebService 规范,分别是JAX-WS(JAX-RPC)、JAXM&SAAJ、JAX-RS。 1. Jaxws(掌握) JAX-WS 的全称为 Java API for XML-Based Webservices ,早期的基于SOAP 的JAVA 的Web 服务...

onedotdot
46分钟前
0
0
将博客搬至CSDN

将博客搬至CSDN

xpbob
47分钟前
1
0
Aidl进程间通信详细介绍

目录介绍 1.问题答疑 2.Aidl相关属性介绍 2.1 AIDL所支持的数据类型 2.2 服务端和客户端 2.3 AIDL的基本概念 3.实际开发中案例操作 3.1 aidl通信业务需求 3.2 操作步骤伪代码 3.3 服务端操作...

潇湘剑雨
今天
0
0
python爬虫日志(3)下载图片

import urlliburl='https://xxx.jpg'#图片地址res=urllib.request.urlopen(url)#此函数用于对url的访问data=res.read() #字节流with open(r'D:\1.jpg',"wb") as code: c...

茫羽行
今天
0
0
vue中$emit的用法

1、父组件可以使用 props 把数据传给子组件。 2、子组件可以使用 $emit 触发父组件的自定义事件。 vm.$emit( event, arg ) //触发当前实例上的事件 vm.$on( event, fn );//监听event事件后运...

JamesView
今天
0
0
bash审计系统搭建

step1:使用saltstack工具bash部署>>>>>> # salt -N clienta state.sls audit step2:安装elasticsearch>>>>>> 注意: 1.不能以root用户进行启动,需要创建用户,并对解压的elasticsearch目录赋......

硅谷课堂
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部