预排序遍历树算法

如题所示，这是一种为查询而生的遍历树算法，如果业务需求要求查询的场景高于、多于增删改，可以考虑此算法，该算法会牺牲掉一些插入、删除的性能。

算法简单概括：类二叉树先序遍历，将树上的每个节点标示left、right、level、parent属性（parent可以更方便画出树结构），查询通过left和right取值，一般情况可以通过一条sql查询和排序出整个需要的树节点。

该算法在网络上有很多资源。

查询某段树的节点数

查询整树

新增、删除节点

比较常用的树结构——邻接表

通过先序遍历算法，预置每个节点left、right后的树如下图所示：图片转自网络

1.查询某段树的节点数

(顶点right-顶点left+1)/2

例如图中B、C、D、E、F段树的节点数：(11-2+1)/2=5

2.查询整树

顶点left <= left && 顶点right >= right

例如图中B、C、D、E、F树:
select * from tree where left>=2 and right<=11 order by left
然后根据level可以和父子关系可以很清晰的画出整个树。

3.新增、删除节点
如下图新增X节点：图片转自网络

通过图可以看到，新增点位X左边的left和right都不变，右边所有节点都需要update。
更新公式：
X右边所有节点的left＋2、right＋2，
X节点由于没有子节点，所有left＝左边临界点right＋1、right＝自己的left＋1

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

4.比较常用的树结构——邻接表
这种结构是现实中最常用而且最容易理解的，简单来讲就是每个节点标示一下自己的parent ，根据parent递归画出树结构，需要多次遍历。但是更新会更加方便。

Renfei's blog