二叉树在实际项目中的应用

3,265 阅读6分钟

二叉树模型在实际项目中的应用

【云计算尖子班】 技术分享

分享时间:2017.04.14

分享人:海诺

主题:《二叉树模型在实际项目中的应用》

[TOC]

首先向大家道歉,没有在云计算方面分享内容。我的内容是来源于最近几次的外包项目中,单产品金字塔体系的研究,希望能给大家一定的收获。

概述

金子塔是销售行业对二叉树的一个称呼,可能还有别的例如正三角,或者大三角小三角之说但总归离不开二叉树这个模型。

金字塔为什么是二叉树模型

  1. 首先金字塔的每一个节点需要一个上级,最顶级不需要

  2. 金字塔的每一个节点都可以且最多只能放置两个下级

  3. 整个金字塔内部节点,随着层数的增加呈现出以2的n次方方式的顺序

    第一层 $2^0$

    第二层 $2^1$
    ….
    第n层 $2^{n-1}$

    二叉树的缺点和优点

  4. 优点,可计算,每一个节点,每一个节点的数量都可以进行计算,而且可以很快的进行定位,即便是每一层不满员

  5. 缺点,缺点是每一节点下面有且最多只有2个下级节点。

    二叉树的计算模型

    A

二叉树算法模型

  1. 四角标号 每一个节点有一个定义 定义四个角
左上角表示层级 
右上角表示邀请人 
左下角表示左编号
右下角表示右编号

一般通用定义只定义两个就是左编码和右编码

  1. 层级规格 那一层那么他的层号为n-1

  2. 邀请人是根据实际情况来的,就是A邀请F那么F的右上角标记为A

  3. 左编码和右编码 除了第一层的左编码永远是1之外其他的左编码和右编码均会在节点增加时进行加法操作,每增加一个节点 节点后面的右编码和左编码都会进行更改做+2操作

二叉树算法模型示例图

完整的算法图形
A 2

二叉树的算法 节点左右编码算法

  1. 节点左上角的layer值算法就是$n-1$ 第一层就是$1-1 = 0$ 以此类推

  2. 左右下角的编码计算,当仅有一个节点A时,表示最顶级,左编码为1,右编码为2,增加一个人那么就会默认放在这个节点的左下节点,再增加一个为右下节点。先说增加左下节点的时候,新增加的左下节点为父级的左编码+1所以A的左下节点B的左编码为2,这时候B在最下方,B的右编码为左编码+1=3,A的右编码为B的右编码+1=4,当增加A的右下节点C时(这时候一定是存在左下节点的)那么C的左编码为左侧节点的右编码+1=4,C为最下方,C的右编码为自身左编码+1=5,A的右编码为C的右编码+1……以此类推,我们可以看到每增加一个节点A的右编码都会增加2,增加节点后左右编码值大于等于增加节点左编码值的所有值都+2;

  3. 层数计算 layer在实际当时是不可能通过1的方法得到的,因为新增的一个节点,电脑不会得到他是那一层。我们可以通过这样计算层,有两种方法:
    1. 计算他与最顶级之间的节点数 这个可以看西面的具体算法
    2. 读取他父节点的layer,然后+1
  4. 那么我们先看看如何计算总节点数,得到每个节点的信息
    假设我们把这个信息放入到数据库中,定义这样几个字段user,puser,layer,left,right 分别对应当前人,邀请人,层级,左编码,右编码。
    那么我们可以通过'select user from table where left >=1 and right <= 12[A对应的right值] 来得到所有节点,当然也可以通过select * from table得到所有节点,查询出数据后我们可以count()一下得到数组的长度,然后就得到所有节点和总节点数
    计算节点数,还有两种方法,
    1. 如果我们已经知道A的左右值为1和12,那么我们可以很轻松的使用12/2=6得到数据结果。
    2. 如果我们得到最下级节点信息,可以通过 $2^{layer+1}-1$ 来得到所有的节点数目
  5. 如何计算某条分支节点数,每个节点的信息
    仍然是遵循4的假设,按照图形示例中完整的二叉树算法图的信息来计算。我们如何获取到B 和F分支有几个节点以及节点信息呢?
    1. 引子:计算B下的节点数可以通过,【B的右编码】5-【B的左编码】2 然后减去【自身】1=1 来得到。示例中的图形是只有一个节点,但是节点多了呢依然如此,你可以自行计算下C下面的节点数。
    2. 有了上面的引子,我们来看如何获取节点信息。select * from table where left>=1 and left <=3 and right >=4 and right<=12 我们就可以轻松的查询出节点的信息,
    3. 当然我们也可以通过layer的减法来得到节点数例如 【F的layer】2-【A的layer】0 +1 =3,但是该方法无法得到节点信息。
  6. 如何计算A总共的邀请人数
    邀请人数我们一般会放在另一个表中单独处理,但是在当前的4的假设中,我们可以统计有效的邀请人数。 select * from table where puser='A' and left >1 and left <12; 只需要得到邀请人的信息即可。(这里有一个隐藏的原理,属于分销体系,你邀请的人只能在你的下方节点中)
    更简单的方法 select * from table where puser='A'
  7. 计算是否满员,有些销售体系在使用邀请制后,会制定特殊规则比如用户小金字塔必须三级。也就是说需要达到$2^0+2^1+2^2+2^3=2^{3+1}-1=15$ 人。这里怎么算呢可以通过layer来计算,以A为例子,select count(user) as num from table where layer between 0 and 3 and left >=1 and right <=12 即可得到。

总结

以上的内容是在实际开发中经常用到销售系统二叉树模型,感谢大家和我共同学习这个算法,限于个人水平和研究深度,如有不足和错误,恳请大家指正和批评。


海诺@云计算尖子班