18
2013-01

预排序遍历树算法

  预排序遍历树算法

  这个算法有如下几个数据结构

  lft代表左 left

  rgt 代表右 right

  lvl 代表所在的层次 level

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

image


  我们先看一些使用方法

  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节点。

image


  我们要做的工作就是

  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://www.shiyayong.cn/post/106.html

评论列表:

8  匪里匪气  2013-1-20 15:54:16 回复该留言  IP:112.244.233.141
呵呵 这种文章 土匪只能围观了···
  茶馆老板  2013-1-20 21:34:55 回复该留言  IP:118.186.58.177
那你是学什么专业的啊?嘿嘿
茶馆老板
匪里匪气
7  IFan  2013-1-20 14:12:48 回复该留言  IP:60.221.240.102
说实话。这个俺站看不懂! 俺是打酱油的!
  茶馆老板  2013-1-20 21:34:40 回复该留言  IP:118.186.58.177
程序你自己都弄出名堂来了哦
  IFan  2013-1-21 10:52:21 回复该留言  IP:123.183.223.25
哈哈!
IFan
茶馆老板
IFan
6  旅途者  2013-1-20 14:04:39 回复该留言  IP:114.246.106.13
这些基础数据结构里应该都有了。
  茶馆老板  2013-1-20 21:34:24 回复该留言  IP:118.186.58.177
基础的吧,有介绍的
茶馆老板
旅途者
5  肥牛陈  2013-1-19 15:12:25 回复该留言  IP:180.158.233.159
我用的西数的香港主机,慢的要死。
  茶馆老板  2013-1-20 21:33:18 回复该留言  IP:118.186.58.177
我用的不是西部数码的,是一个不出名的吧
茶馆老板
肥牛陈
4  肥牛陈  2013-1-19 12:20:47 回复该留言  IP:180.158.233.159
你的那个时间挺有意思的!我看了好几分钟!最奇妙的是整点的时候,全部数字都在扭动!我难道很无聊??
  茶馆老板  2013-1-19 12:35:34 回复该留言  IP:220.181.73.127
没有啊,你可以拿到自己的网站上用哦
  肥牛陈  2013-1-19 12:38:34 回复该留言  IP:180.158.233.159
呵呵,不用了,用的服务器不好,打开速度太慢了。博客又不好备案,不然就转国内服务器了
  茶馆老板  2013-1-19 15:10:45 回复该留言  IP:118.186.140.17
我用的就是国内的服务器,凑合吧,一般般速度
茶馆老板
肥牛陈
茶馆老板
肥牛陈
3  sifu  2013-1-18 22:33:14 回复该留言  IP:125.34.1.66
不是平衡二叉树啊
  茶馆老板  2013-1-27 15:00:01 回复该留言  IP:114.112.46.60
不是的,这个是数据结构中的遍历树
茶馆老板
sifu
2  多语言网站制作  2013-1-18 16:15:42 回复该留言  IP:120.32.221.62
没明白它的作用!看来没有多学习下,就是什么都不懂!
  茶馆老板  2013-1-18 17:31:12 回复该留言  IP:124.205.133.34
这个是数据结构中常见的排序问题了
  多语言网站制作  2013-1-19 18:06:07 回复该留言  IP:120.32.217.142
嗯,理解了
  茶馆老板  2013-1-19 21:17:14 回复该留言  IP:220.181.73.127
数据结构中的好多都是基于C语言的
茶馆老板
多语言网站制作
茶馆老板
多语言网站制作
1  ggr  2013-1-18 15:53:09 回复该留言  IP:14.122.106.10
别就是排序是反向的就行了 http://www.10086zg.com/caogen/?13970
ggr

发表评论:

(设置个性头像)

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

无觅相关文章插件,快速提升流量