python 实现多叉树重复值合并

原始应用场景：

1. 扫描系统中的image，在release的前夕确保系统的image tag是可release的版本。
2. 追溯上游image（base），保证上游base image版本同样达到release要求，且可控。

那么如何做到溯源，要求docker file中From 或者Label字段上记录该image的上游。如果能保证按照这条规则执行，那么我们会得到类似于这样的信息：

    centos-base:1.0.0-->openjdk:1.8.0-->product:2.0.0
    ubuntu-base:1.0.1-->tomcat:1.3.0-->product1:2.0.1
    centos-base:1.0.0-->openjdk:1.8.1-->product:2.0.1
    ...

继续思考：观察数据会发现好多image会有同样的base image，那么针对这些image，我们需要将他们归并到一条分支上。或者说要找出他们的祖先，将他们归并道对应的祖先分支上。那么思想和树很像了，决定用树形结构来处理。

简化抽象需求，画出简图如下：

jaymz
├── abc
│   ├── abcd
│   └── shg
│       └── du
├── ef
│   ├── abcd
│   │   ├── mn
│   │   │   └── df
│   │   ├── xyz
│   │   └── xyz(重复节点)
│   └── gh
├── abc(重复节点)
│   └── abcd（重复节点）
│       └── sh
└── abc(重复节点)

设计：

使用python treelib模块构造多叉树：

tree = Tree()
tree.create_node('root','root',data = NodeX('jaymz'))
tree.create_node("child1","child1",parent="root",data=NodeX("abc"))
tree.create_node("child11","child11",parent="root",data=NodeX("ef"))
tree.create_node("child111","child111",parent="root",data=NodeX("abc"))
tree.create_node("child1111","child1111",parent="root",data=NodeX("abc"))
tree.create_node("child2","child2",parent="child1",data=NodeX("abcd"))
tree.create_node("child22","child22",parent="child1",data=NodeX("shg"))
tree.create_node("child222","child222",parent="child11",data=NodeX("abcd"))
tree.create_node("child2222","child2222",parent="child11",data=NodeX("gh"))
tree.create_node("child22222","child22222",parent="child111",data=NodeX("abcd"))
tree.create_node("child3","child3",parent="child22",data=NodeX("du"))
tree.create_node("child33","child33",parent="child222",data=NodeX("mn"))
tree.create_node("child333","child333",parent="child222",data=NodeX("xyz"))
tree.create_node("child3333","child3333",parent="child222",data=NodeX("xyz"))
tree.create_node("child33333","child33333",parent="child22222",data=NodeX("sh"))
tree.create_node("child4","child4",parent="child33",data=NodeX("df"))

将每一层的树节点的id，编为child1，child11...child2，child22...同一层后缀数字一样，个数不一样，不同层数字不一样，以此类推。这样的好处就是我能根据节点ID，就知道它属于第几层。

合并思路：

同层节点比较，将第一个节点的数值作为base value，通过tree.children(parentNodeTag)，获取同层的子节点，如果发现有相同的数值，将其ID记录到变量中，等处理完后统一从tree中remove。当然在remove之前需要将其子树移动到相同值的节点上。

流程图如下：

WeChat Screenshot_20190513175033.png

代码部分：

#!/usr/bin/env python
import treelib
from treelib import Tree, Node

class NodeX(object):
    def __init__(self,num):
        self.num = num

def moveNode(tree,source,dentinate):
    if len(source)==1:
        tree.move_node(''.join(source),dentinate)
    else:
        for var in source:
            tree.move_node(var,dentinate)

def getChildrenNodeTag(tree,nodeTag):
    childrenNodeTag = tree.children(nodeTag)
    tags = []
    for i in childrenNodeTag:
        tags.append(i.tag)
    return tags

def compareSameFloorAndRemoveDupliNode(tree,nodeTag):
    dupltiNodeTag = []
    firstNodeTag = ""
    if tree.children(nodeTag):
        nodeCount = len(tree.children(nodeTag))
        tempValue = []
        for m in range(nodeCount):
            # print("tempValue",tempValue)
            nodeValue = tree.children(nodeTag)[m]
            if len(tempValue)==0:
                tempValue.append(nodeValue.data.num)
                firstNodeTag = nodeValue.tag
            else:
                if nodeValue.data.num in tempValue:
                    dupltiNodeTag.append(nodeValue.tag)
                    # print("dupltiNodeTag",dupltiNodeTag)
                    if hasMultiLeafs(tree,nodeValue.tag):
                        adjustNode = getChildrenNodeTag(tree,nodeValue.tag)
                        moveNode(tree,adjustNode,firstNodeTag)
                else:
                    tempValue.append(nodeValue.data.num)
    # print(dupltiNodeTag)
    return dupltiNodeTag

def hasMultiLeafs(tree,nodeTag):
    count = len(tree.children(nodeTag))
    if count>=1:
        return True
    else:
        return False

def main():
    createTree()
    # tree.show()
    print("---------------refactor below-------------------")

    removeNode = []
    treeStruct =tree.to_json()
    for floor in range(tree.depth()):
        if floor == 0:
            nodeTag = "root"
        else:
            nodeTag = "child"+str(floor)
            levelCount = treeStruct.count(nodeTag)
            horizontalTempNodeTag = "child"
            for horizontal in range(levelCount):
                horizontalTempNodeTag = horizontalTempNodeTag+str(floor)
                if tree.contains(horizontalTempNodeTag) and hasMultiLeafs(tree,horizontalTempNodeTag):
                    removeNode.extend(compareSameFloorAndRemoveDupliNode(tree,horizontalTempNodeTag))
                else:
                    continue

        removeNode.extend(compareSameFloorAndRemoveDupliNode(tree,nodeTag))

    for i in set(removeNode):
        # print(set(removeNode))
        tree.remove_node(i)
    return tree.show(data_property="num")


if __name__=="__main__":
    main()

效果如下：

WeChat Screenshot_20190513175613.png

PS:代码还有优化空间，嵌套比较多，性能方面考虑不是很多。