前几天在项目开发中遇到了前辈们所设计的结构(用来实现商品分类)，所设计的结构便是利用了预排序遍历树算法。故特此去查询资料以便掌握该知识点!下面是我这些天的心得体会。
一，商品分类表--建表语句和数据库结构
CREATE TABLE IF NOT EXISTS `test`.`product_type` (
`pt_id` INT(11) unsigned NOT NULL AUTO_INCREMENT ,
`pt_name` varchar(50) NOT NULL COMMENT '分类名称' ,
`pt_fid` INT(11) unsigned NOT NULL DEFAULT 0 COMMENT '父分类id' ,
`pt_depth` tinyint(5) NOT NULL DEFAULT 0 COMMENT '分类深度' ,
`pt_left` INT(11) unsigned NOT NULL DEFAULT 0 COMMENT '节点左侧编号' ,
`pt_right` INT(11) unsigned NOT NULL DEFAULT 0 COMMENT '节点右侧编号' ,
PRIMARY KEY (`pt_id`) )
ENGINE = InnoDB
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_general_ci
COMMENT = '商品分类表';
商品分类表数据结构 .jpg
建表成功后的数据结构
二，预排序遍历树的结构
1.jpg
当我第一眼看到这个图的时候，我的最大的疑问就是图1.jpg上的那些节点的左右数字编号是如何确定的？为什么B节点的左右编号是2和11？E，F这些节点的左右编号相差1？
首先我们用手指按照图中红线箭头所示的方向自行描一遍，分别从1赋值到20，明白了没有？（还不明白，那就再描一遍）。从根节点的左侧向下（平行结构时从左到右）数字加1，如：B C D 节点所组成的树。到此，我们可以看出来每个终端节点的左右编号相差为1；一个节点的左编号必定是以该节点为根节点所组成树的编号里面的最小值，而它的右编号必定是最大值，这样才能涵盖它子孙节点的编号变化。
三，所对应的相关算法
插入数据，将图1.jpg所显示的结构存入数据库中（我们一条条的添加），这样有助于我们更加清晰直观的了解整个树结构的变化。在见到整个结构之前你是不知道1.jpg所示结构的,那么我们按照业务逻辑来的话,商品分类逐级建立,则sql语句应如下：
//添加一级分类 A
insert into product_type(pt_name,pt_fid,pt_depth,pt_left,pt_right) values('A',0,1,1,2);
//A下添加二级分类B (A的主键已知)
select * from product_type where pt_id=1; //得到A的左右编号 1 2
select max(pt_right) from product_type where pt_fid = 1; //得 null ,故A没有子节点
update product_type set pt_right = pt_right+2 where pt_right>=2; //A右编号+2 为B腾出空间
insert into product_type(pt_name,pt_fid,pt_depth,pt_left,pt_right) values('B',1,2,2,3);
//B下添加三级分类C (B的主键已知)
select * from product_type where pt_id=2; //得到B的左右编号 2 3
select max(pt_right) from product_type where pt_fid = 2; //得 null ,故B没有子节点
update product_type set pt_right = pt_right+2 where pt_right>=3; //A,B右编号+2 为C腾出空间
insert into product_type(pt_name,pt_fid,pt_depth,pt_left,pt_right) values('C',2,3,3,4);
//B下添加三级分类D(B的主键已知)
select * from product_type where pt_id=2; //得到B的左右编号 2 3
select max(pt_right) from product_type where pt_fid = 2; //得 4 ,故D左右为 5 6
update product_type set pt_right = pt_right+2 where pt_right > 4; //A,B右编号+2 为D腾出空间
insert into product_type(pt_name,pt_fid,pt_depth,pt_left,pt_right) values('D',2,3,5,6);
......(好烦,为了页面好看在此省略下面的代码)
建立好结构后,我们可以很清楚的发现一些规律:
1. 那我们在查询数据库时where条件为 pt_right - pt_left = 1 的所查询出来的结构必定为终端节点。sql语句如下 :
select * from product_type where pt_right - pt_left = 1;
2. 得到某个节点下面的所有子孙节点，只需要where条件 pt_left 大于该节点的左值 and pt_right小于该节点的右值,以b节点举例,则sql语句如下:
select * from product_type where pt_left>2 and pt_right<11 order by pt_left asc;
得到的结果是 C,D,E,F四个节点的数据。
3. 查找两个节点之间的路径,以A到E为例,sql语句如下:
select * from product_type where pt_left between 1 and 6 and pt_right between 7 and 20 order by pt_left ;
得到的结果是A,B,D,E 这4个节点的数据。
4.通过我们刚才新增数据得到这个结构的操作，我们发现新增分两种情况。第一种如下图所示：
新增节点X
变更所有的受影响的节点,给新节点腾出空位子，所有左节点比G节点大的，都增加2，所有右节点比G节点大的，也都增加2，则sql语句如下：
update product_type set pt_right=pt_right+2 where pt_right>=7;
update product_type set pt_left=pt_left+2 where pt_left>12;
update product_type set pt_right=pt_right+2 where pt_right>13;
另一种为新增子节点，但该新增的节点左侧并有节点。举例：在E下新增Y节点，Y节点左右值为7,8，这时我们在修改后续节点时也应该考虑到E节点的存在。所以sql语句如下：
update product_type set pt_left=pt_left+2 where pt_left>6;
算法说明：
1.所有分类 左边和右边的值 > 插入节点的左边节点记录的右值 的全部 + 2
2.插入节点 左值 = 插入位置左边节点记录的右值 + 1， 右值 = 插入位置左边节点记录的右值 + 2
总结：
经过这几天的相关操作和查询资料，整理后我写出了这些东西，但我的收获远不止这些，奈何语言水平有限就讲这么多吧！
网友评论