【树型问题】从一次不太合理的需求中引发一个思考题

发表于 | 分类 | 阅读 次
字数: 2.5k | 时长 ≈ 12

项目需求

在一次项目中遇到的比较特殊的需求，具体信息描述如下：在部门管理中，如果某个管理员对父部门拥有权限，则对其部门及其以下任何部门都有权限；如果对某个部门对 所有子部门 拥有权限，则表示对其父部门拥有权限；还存在一种交叉管理现象即：管理员A管理部门D1和D2，管理员B管理部门D2和D3，他们可以共同管理部门D2，A可以取消B对部门D2对管理权限，同时也可以给B增加对D1的管理权限，反之亦然，A，B只能共同管理公共部门，不能管理自己没有权限的部门。

问题及解决方案

现有一组含父部门节点和子部门节点的集合（前端传参），根据已知的部门树形结构，要求消除含有父子关系节点（数据存储规则：如果有父级部门就存父级部门ID，否则就存子级部门ID），只保留最大权限的节点，例如：部门树形结构为[1, 1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2, 2.1, 2.2, 3, 4]，部门1.1表示是1的子部门，1.2.1表示1.2的子部门，依此类推。

用例枚举及其分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
部门树结构：[1, 1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2, 2.1, 2.2, 3, 4]
    egg1：(增加节点，减少子节点，用子节点替代父节点)
        管理者A权限：department_a=[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3]
        管理者B权限：department_b=[1.2.3, 2, 4]
        B操作步骤：给A增加权限[2,4]，并去掉[1.2.3]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2, 4]
        A的最后结果应为：[1.1, 1.2.1, 1.2.2, 2, 4]
    egg2：(增加子节点补全，用父节点替代子节点)
        管理者A权限：department_a=[1.1, 1.2, 1.2.1, 1.2.2, 2, 4]
        管理者B权限：department_b=[1.2.3, 2, 4]
        B操作步骤：给A去掉权限[2,4]，并增加 [1.2.3]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3]
        A的最后结果应为：[1]
    egg3：(减少子节点，增加子节点，用父节点替代子节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A去掉权限[2.2]，并增加 [1.2.3]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 1.2.3, 4]
        A的最后结果应为：[1, 2.1, 4]
    egg4：(减少父节点，增加子节点，用父节点替代子节点)（？）
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A去掉权限[2]，并增加 [1.2.3]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 4]
        A的最后结果应为：[1, 4]
    egg5：(减少子节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A去掉权限[2.2]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 4]
        A的最后结果应为：[1.1, 1.2.1, 1.2.2, 4]
    egg6：(减少父节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A减少权限[2]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 4]
        A的最后结果应为：[1.1, 1.2.1, 1.2.2, 4]
    egg7：(增加子节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A增加权限[2.2]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2.2, 4]
        A的最后结果应为：[1, 4]
    egg8：(增加父节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A增加权限[2]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 4]
        A的最后结果应为：[1, 2, 4]
    egg9：(增加子节点，（无父节点），用父节点替代子节点)
        管理者A权限：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 2.2, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A增加权限[2.1]
        传参数：update_departments=[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2.1, 2.2, 4]
        A的最后结果应为：[1, 2, 4]
    egg10：(删除子节点)
        管理者A权限：update_departments=[1, 1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2, 2.1, 2.2, 3, 4]
        管理者B权限：[1.2.3, 2, 2.1, 2.2, 4]
        B操作步骤：给A删除权限[1.2.3]
        传参数：update_departments=[0, 1, 1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 3, 4]
        A的最后结果应为：[1.1, 1.2.1, 1.2.2, 2, 3, 4]

完整的代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# coding:utf-8


def is_all_children(children, departments):
    """
    该节点是否含有全部子节点
    :param children:
    :param departments:
    :return:
    """

    res = []
    for n in departments:
        if n in children:
            res.append(n)

    if len(res) == 0:
        # 无子情况
        return -1

    return 0 if set(res) == set(children) else 1


def exists_parent(departments, p_c_dpts):
    """
    判断父子关系
    :param departments:
    :param p_c_dpts:
    :return:
    """

    for k, v in p_c_dpts.items():
        if k in departments and v in departments:
            return True

    return False


def get_merge_departments(departments):
    """
    将更新前后部门数据合并，组成新的部门集合
        特别注意：
        错误做法：1）包括全部子节点即删除子节点，这是错误的，必须从叶子节点开始检查。
         1
         1.1
          1.1.1
            1.1.1.1
            1.1.1.2
            1.1.1.3 (x)
          1.1.2
          1.1.3
         1.2
        说明：如果发现1.1的子节点都在，删除了即保留1.1，这是明显错误的，他只有（1.1.1.1, 1.1.1.2, 1.1.2, 1.1.3）
        2）不包括全部子节点即删除父节点，这是正确的。
        正确解法：先找到可删除的父节点进行删除，然后对包括全部子节点进行如下处理：（1）删除子节点，保留或增加父节点；
        （2）循环遍历，因为新增的父节点可能构成全部子节点中的一个节点，直到不同时存在父子关系的节点为止。

        是否存在父子关系？
            存在：1）处理不包括全部子节点的父节点立即删除（循环处理完）
                 2）包括全部子节点进行处理：删除子节点，保留或增加父节点（循环处理完）
            不存在：看兄弟节点能否组成一个某个父节点的全部子节点，回2）返回结果
    """

    # 保存父子关系，判断是否包含全部子节点
    p_dpts = {
             '1': ['1.1', '1.2'],
             '1.2': ['1.2.1', '1.2.2', '1.2.3'],
             '2': ['2.1', '2.2']
    }
    p_c_dpts = {
        '1.1': '1',
        '1.2': '1',
        '1.2.1': '1.2',
        '1.2.2': '1.2',
        '1.2.3': '1.2',
        '2.1': '2',
        '2.2': '2'
    }

    while True:
        if not exists_parent(departments, p_c_dpts):
            return departments

        # 处理不包括全部子节点的父节点立即删除（父子同时存在）
        flag = list()
        for index, up in enumerate(departments):
            if p_dpts.get(up) and is_all_children(p_dpts[up], departments) == 1:
                flag.append(up)

        # 进行删除
        for item in flag:
            departments.remove(item)

        flag = list()
        for index, up in enumerate(departments):
            if p_dpts.get(up) and is_all_children(p_dpts[up], departments) == 0:
                flag += p_dpts[up]

        # 进行删除
        for item in flag:
            departments.remove(item)

        # 兄弟节点能否合并
        flag = dict()
        for k, v in p_dpts.items():
            if not set(v).difference(set(departments)):
                flag[k] = v

        # 删除子节点，增加父节点
        for k, v in flag.items():
            departments.append(k)
            for i in v:
                departments.remove(i)


if __name__ == '__main__':

    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 2, 4]
    # A的最后结果应为：[1.1, 1.2.1, 1.2.2, 2, 4]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '2', '4']
    print("[1.1, 1.2.1, 1.2.2, 2, 4] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 1.2.3]
    # A的最后结果应为：[1]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '1.2.3']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 1.2.3]
    # A的最后结果应为：[1, 2.1]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '1.2.3', '2', '2.1']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 1.2.3] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 4]
    # A的最后结果应为：[1, 4]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '1.2.3', '4']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 4] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 4]
    # A的最后结果应为：[1.1, 1.2.1, 1.2.2, 4]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '4']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 4] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 4]
    # A的最后结果应为：[1, 2, 4]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '2', '2.1', '2.2', '4']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 4] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2.1, 2.2, 4]
    # A的最后结果应为：[1, 2, 4]
    update_departments = ['1.1', '1.2', '1.2.1', '1.2.2', '1.2.3', '2.1', '2.2', '4']
    print("[1.1, 1.2, 1.2.1, 1.2.2, 1.2.3, 2.1, 2.2, 4] = ", get_merge_departments(update_departments))
    # 传参数：update_departments = [1, 1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 4]
    # A的最后结果应为：[1.1, 1.2.1, 1.2.2, 2, 4]
    update_departments = ['1', '1.1', '1.2', '1.2.1', '1.2.2', '2', '2.1', '2.2', '4']
    print("[1, 1.1, 1.2, 1.2.1, 1.2.2, 2, 2.1, 2.2, 3, 4] = ", get_merge_departments(update_departments))
坚持原创技术分享，您的支持将鼓励我继续创作！