NO.001算法应用—组织结构问题----By.实施组

案例背景

某集团公司下设有多级多个子公司，集团每月进行财务核算，需要把报表逐级合并至集团公司，采用NC系统的合并报表功能。是典型的重复、有规律操作。该集团还有个特点，上下公司在组织结构上会不定期调整。

流程设计

流程分析

整体流程除了登录、组织结构维护都是重复执行的部分，循环项就是公司，是含有下级的公司，同时循环顺序根据业务要求，从低级往高级。按照一般的思路，我们会让用户提供表格，在表格中按顺序填写公司，流程根据这列顺序进行循环。

我们在A列按序写上带有下级的公司，在B-D列写上与A列对应的下级公司，根据这样的表格去做组织结构维护和合并报表操作。这个思路对开发的同学来说很方便，读取输入操作就行。但对用户就不友好，TA每次要手动去调整这里的顺序，至少需要：插入行、复制、粘贴、删除行4步动作。核对麻烦，顺序不能错，后面的子公司也不能错。

A	B	C	D
A集团公司	B1区域公司	B2区域公司
B1区域公司	C1技术公司
C1技术公司	D1技术公司	D2技术公司	D3技术公司
D1技术公司	E1技术公司
E1技术公司	E2技术公司	E3技术公司
E2技术公司	F1技术公司	F2技术公司
F1技术公司	G1技术公司

改进

现在我们需要让这个表格看起来更简单点，比如不去人为的注明顺序，只是简洁的反映上下关系。
只放两列数据，A列是所有公司，B列是A列对应的上级。像下面这表格

A	B
A集团公司
B2区域公司	A集团公司
F2技术公司	E2技术公司
F1技术公司	E2技术公司
G1技术公司	F1技术公司
E2技术公司	E1技术公司
E3技术公司	E1技术公司
E1技术公司	D1技术公司
D3技术公司	C1技术公司
D2技术公司	C1技术公司
D1技术公司	C1技术公司
C1技术公司	B1区域公司
B1区域公司	A集团公司

很明显写在B列的就是带有下级的公司。
去重后就是：A集团公司、E2技术公司、F1技术公司、E1技术公司、D1技术公司、C1技术公司、B1区域公司
那这些”公司“的顺序又该如何确定🤔，计算机又不能像人一样看出来。
如果我们把最上面的一层A集团公司的深度表示为1，依次往下标出深度。同一层的公司深度一致。那么深度的大小就是顺序的先后。求”公司“顺序，现在就是求他们的深度。

解决方法

怎么求，用数据结构”树“
它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
当然这里不用手写树结构，而是学会用treelib 模块去搭建这颗树，和使用相关方法。
用”Tree“对象的方法生成节点，配合递归思路去补充”Tree“的节点。
构造完整的”Tree“对象后，对B列节点求深度、排序。

模块中的相关方法：
create_node( tag=None, identifier=None, parent=None, data=None ) 
创建一个节点并直接添加到树中。tag表示节点的标签，在控制台打印树的结构时显示的就是节点的标签，可以指定值，如果不指定值则默认等于id。identifier表示节点的id，默认会分配一个唯一的id，也可以指定一个唯一id。这里要注意，id是唯一的，不能重复，标签是可以重复的但最好别重复。parent表示节点的父节点，根节点可以不指定，不过，一棵树只能有一个根节点，如果树中已经有根节点了，parent还为空会报错。data表示节点中保存的数据，可以是各种数据类型。
总结下来就是，identifier必传，parent非根节点时必传

contains(self, nid)
检查树中是否包含以nid为标识的节点

depth(node=None):
返回节点的高度，根节点高度为0，依次递增。如果不指定节点则返回树的高度。
node 可以是 id或者 标签

is_branch(self, nid)
返回以nid为节点的子节点标识(identifier)的list列表，nid不存在则返回list为空

递归思路：
创建节点前需要判断，它的父节点是否存在，不可以直接创建。
如果父级节点不存在，那么改为创建父级节点，同理继续判断父节点的父节点是否存在；如果存在则创建当前节点。
但是有一种情况不用判断父节点，就是最上面的根节点，表格里的B列值为空时，那A列就是根节点了，直接创建节点就行。

from treelib import Tree

# 读取A列 A_col
# 读取B列 B_col

A_col = ["A集团公司","B2区域公司","F2技术公司","F1技术公司","G1技术公司","E2技术公司","E3技术公司","E1技术公司","D3技术公司","D2技术公司","D1技术公司","C1技术公司","B1区域公司"]
B_col = ["","A集团公司","E2技术公司","E2技术公司","F1技术公司","E1技术公司","E1技术公司","D1技术公司","C1技术公司","C1技术公司","C1技术公司","B1区域公司","A集团公司"]

# 转字典
dict_关系 =dict(zip(A_col,B_col))

tree = Tree()

# 添加当前节点
def addNode(节点,父级):

    if 父级 =='' and tree.contains(节点)==False:
        tree.create_node(identifier=节点)
        return

    if tree.contains(父级)==False:
        addNode(父级, dict_关系[父级])
        tree.create_node(identifier=节点,parent = 父级)
        return

    elif tree.contains(节点)==False:
        tree.create_node(identifier=节点,parent = 父级)
        return

for key, value in dict_关系.items():
    addNode(key,value)

tree.show()

# A集团公司
# ├── B1区域公司
# │   └── C1技术公司
# │       ├── D1技术公司
# │       │   └── E1技术公司
# │       │       ├── E2技术公司
# │       │       │   ├── F1技术公司
# │       │       │   │   └── G1技术公司
# │       │       │   └── F2技术公司
# │       │       └── E3技术公司
# │       ├── D2技术公司
# │       └── D3技术公司
# └── B2区域公司

# B列节点求深度、排序
dict_深度={}
for i in B_col:
    if i !='' and i not in dict_深度:
        深度 = tree.depth(i)
        child_node = tree.is_branch(i)
        dict_深度[i]= [深度, child_node]

result = sorted(dict_深度.items(), key = lambda kv:(kv[1][0], kv[0]) ,reverse=True)
print(result)

# [
#     ('F1技术公司', [6, ['G1技术公司']]), 
#     ('E2技术公司', [5, ['F2技术公司', 'F1技术公司']]), 
#     ('E1技术公司', [4, ['E2技术公司', 'E3技术公司']]), 
#     ('D1技术公司', [3, ['E1技术公司']]), 
#     ('C1技术公司', [2, ['D1技术公司', 'D3技术公司', 'D2技术公司']]), 
#     ('B1区域公司', [1, ['C1技术公司']]), 
#     ('A集团公司', [0, ['B2区域公司', 'B1区域公司']])
# ]

自此用户只需要写两列数据，我们就能整理出这些数据的层级关系。