最近做一个程序，用到树形结构，并且要存储到数据库中。于是研究了一下树形结构的左右值存储。

左右值虽然取父祖节点和子孙节点，查找节点路径非常方便，但要找某节点的父节点，子节点和兄弟节点就比较困难，所以还要需要一个层级维度方便确定父子和兄弟节点，也就是树形结构中所说的树的深度。

下面列举一些普通的左右值算法，网上有大量的资料，就不细说了。

以下资料来自网上，错误的地方我已纠正

一、计算某节点的子孙节点数。

子孙节点数量 = （节点右值-节点左值-1）/2

二、查找某节点的所有子孙节点。

select * from tree where L > 节点左值 and R < 节点右值 order by L asc;

三、查找某节点的所有父祖节点。

select * from tree where L < 节点左值 and R > 节点右值 order by L desc;

四、某节点所处层级。

select count(*) from tree where L <= 节点左值 and R >= 节点右值

五、增加节点。需要为要增加的节点腾出左右值的空间。然后将新节点插入数据库。在哪里增加？这就需要参照物，有下面四种情况。

1.在A节点下增加子节点B，B作为第一个子节点。

#更新受影响节点

update tree set L = L + 2 where L > A节点左值;

update tree set R = R + 2 where R > A节点左值;

#插入新增的节点

insert into tree (name, L, R) values('B', A节点左值+1, A节点左值+2);

2.在A节点下增加子节点B，B作为最后一个子节点。

#更新受影响节点

update tree set L = L + 2 where L >= A节点右值;

update tree set R = R + 2 where R >= A节点右值;

#插入新增的节点

insert into tree (name, L, R) values('B', A节点右值, A节点右值+1);

3.在A节点后面增加节点B, B作为A的兄弟节点。

#更新受影响节点

update tree set L = L + 2 where L > A节点右值;

update tree set R = R + 2 where R > A节点右值;

#插入新增的节点

insert into tree (name, L, R) values('B', A节点右值+1, A节点右值+2);

4.在A节点前面增加节点B,B作为A的兄弟节点。

#更新受影响节点

update tree set L = L + 2 where L >= A节点左值;

update tree set R = R + 2 where R >= A节点左值;

#插入新增的节点

insert into tree (name, L, R) values('B', A节点左值, A节点右值);

一个节点有左右值，两个数。所以上面的算法是添加1个节点要加2，依次类推2个节点是2*2=4，3个 3*2 =6。

六、删除A节点。先要计算出该节点及其所有子节点所占的左右值空间，作为常量，然后用这个常量更新其它节点的左右值。

常量 = A节点右值 – A节点左值 +1;

还有一个算法A所有子孙节点数量(含A节点) * 2

#删除A节点及其子孙节点

delete from tree where L >= A节点左值 and R <= A节点右值;

#更新受影响的节点 A节点后的所有节点均受影响

update tree set R = R – 常量 where R > A节点右值;

update tree set L= L - 常量 where L > A节点右值;

七、移动节点。 这部分是我利用多张下面的图形找出的规律，错误之处请高人指正。

重头戏来了，这个网上讲得大多含糊不清。移动节点简单点就是先删，后加。当然这个删不是真删，只是打个标记，表示删除。但这样有个弊端就是受影响的节点太多，数据量大时影响效率。经过几天的试验，找出了一个比较不错的移动节点的算法。

第一步，先确定移动的方向，是左移还是右移。左移，节点左右值会变小; 右移，节点的左右值会变大。

第二步，根据移动的方向和兄弟节点的排序，计算出节点移动后的左右值。

第三步，根据移动后的左右值，计算出受影响节点的左右值范围。

第四步，根据范围更新受影响节点的左右值，常量为A节点右值 – A节点左值 + 1;。

第五步，计算节点及期子孙节点的偏移量节点原左右值 - 移动后的左右值。

第六步，根据节点的偏移量更新其子孙节点的左右值。

具体看代码，代码有详细的注释，此代码经过初步测试未发现有问题

         /// <summary>

        /// 移动节点  有子孙节点的，会连子孙节点一起移动

        /// </summary>

        /// <param name="srcid">要移动的节点ID</param>

        /// <param name="targetid">移动后新的父节点</param>

        /// <param name="pos">兄弟节点位置 -1 最后 0 1最前 具体数字为顺序号</param>

        public static void move(int moveid,int targetpid, int FamilyID,int pos=-1)

        {

            Point srcp = getLRval(moveid, FamilyID);           //取移动节点的原左右值

            Point targetp = getLRval(targetpid, FamilyID);     //取目标节点的左右值   移动节点新的父节点  

 

            if (targetp.X >= srcp.X && targetp.Y <= srcp.Y)

                throw (new Exception("不能移动到其本身节点或其子节点！"));

 

            int otheroffse = srcp.Y - srcp.X + 1;//其他受到影响节点要加或减的值 偏移值 要移动的节点数目 *2  右移减掉 左移加上

 

            bool IsLeft = (srcp.X - getLocation(FamilyID, targetpid, pos))>0;//判断是左移还是右移 右移为负，左移为正 （移动前-移动后）不会出现等于0的情况

           

            int srcLevel = (int)dbop.GetSingle($"select nLevel from Relation where MID = {moveid} and HID = {FamilyID}"); //移动节点原层级

            int targetLevel = (int)dbop.GetSingle($"select nLevel from Relation where MID = {targetpid} and HID = {FamilyID}") + 1; //移动后层级

            int loffse = srcLevel - targetLevel;//层级差 偏移量

 

            int moffse = 0; //移动节点偏移量。右移为负，左移为正 （移动前-移动后）

 

            //获取移动节点所有子孙节点的id，方便后面更新（不包含自身）

            int[] srcchildren =  getchildrenIDs(moveid,FamilyID);

            //获取其他受影响节点 左移 原父左值变 新父右值变， 右移 原父右值变，新父左值变  

           

            List<string> sqlList = new List<string>();

            if (IsLeft)//左移 受影响的数据值范围为 大于等于移动节点的新左值 ，小于原左值

            {

                Point newPoint = getNewPoint(targetpid, pos, otheroffse, FamilyID); //计算移动节点新位置的左右值

                moffse = srcp.X - newPoint.X; //计算移动节点及其子节点的偏移量

                //更新受影响的节点 右移减 左移加

                sqlList.Add($"update Relation set Nleft = Nleft + {otheroffse} where Nleft >= {newPoint.X} and Nleft < {srcp.X} and HID = {FamilyID} ");

                sqlList.Add($"update Relation set Nright = Nright + {otheroffse} where Nright >= {newPoint.X} and Nright < {srcp.X} and HID = {FamilyID}");

            }

            else //右移 受影响的数据值范围为 大于移动节点的原右值 ，小于等于新右值

            {

                Point newPoint = getNewPoint(targetpid, pos, otheroffse, FamilyID,false); //计算移动节点新位置的左右值

                moffse = srcp.X - newPoint.X; //计算移动节点及其子节点的偏移量

                //更新受影响的节点 右移减 左移加

                sqlList.Add($"update Relation set Nleft = Nleft - {otheroffse} where Nleft > {srcp.Y} and Nleft <= {newPoint.Y} and HID = {FamilyID}");

                sqlList.Add($"update Relation set Nright = Nright - {otheroffse} where Nright > {srcp.Y} and Nright <= {newPoint.Y} and HID = {FamilyID}");

            }

            //更新移动节点及其子孙节点

            //左右值 层级

            string ids = String.Join(",", srcchildren) + "," + moveid;

            ids = ids.Trim(',');

            sqlList.Add($"update Relation set Nleft = Nleft - {moffse}, Nright = Nright - {moffse},nLevel = nLevel - {loffse} where MID IN ({ids}) and HID = {FamilyID}");

            //父ID

            sqlList.Add($"update Relation set PID = {targetpid} where MID = {moveid} and HID = {FamilyID}");

            dbop.ExecuteSqlTran(sqlList); //事务更新

 

        }