import copy
class Dept:
def __init__(self, id, name, parentid) -> None:
self.id = id
self.name = name
self.parentid = parentid
self.children = []
def __eq__(self, other):
# if(self.id == other.id and self.name == other.name and self.parentid == other.parentid
# and self.children == other.children):
if(self.__dict__ == other.__dict__):
return True
else:
return False
以上是一个组织的结构，现有一个list如下，里面存放的是这个组织的信息。求：将此list转换为树状结构
d1 = Dept('120', 'zhangsan', '12')
d2 = Dept('1200', 'lisi', '120')
d3 = Dept('1201', 'wangwu', '120')
d4 = Dept('12010', 'zhangsan', '1201')
l1 = [d4, d1, d3, d2 ]
以下是两个方法，均使用了递归函数。第一个方法是比较组织树dept和组织d1，如果dept是d1的子节点，则将dept加在d1下，并返回d1；如果d1是dept的子节点，则将d1加在dept下，返回dept；如果dept和d1关联不上，则返回dept。
第二个方法是dept是与list1里结构一样的组织对象，将list1中的组织对象组合到dept中成为一个树状组织。
第三，还新建了一个判断两个组织是否相等的方法，是重写了Dept的__eq__方法。
def traverse_dept(dept, d1):
tmp = copy.deepcopy(d1)
if(dept.id == d1.parentid):
dept.children.append(d1)
elif(d1.id == dept.parentid):
d1.children.append(dept)
else:
for dept_tmp in dept.children:
traverse_dept(dept_tmp, d1)
return d1 if(tmp != d1) else dept
def convert_list_to_tree(dept, list1):
if(len(list1)==0):
return dept
for i in list1:
tmp = copy.deepcopy(dept)
dept = traverse_dept(dept, i)
if(tmp != dept):
list1.remove(i)
dept = convert_list_to_tree(dept, list1)
return dept
# return dept
depts = convert_list_to_tree(l1[0], l1[1:])
for i in depts.children:
print(i.__dict__)
经过解决这个问题，对于递归函数有更多认识，现总结如下：
1、第一种常见的递归，就是函数处理一直是同一个对象，这种函数不需要有返回值，调用完函数之后，对象本身已经经过了处理。比如，下面，将一个list中的重复元素删除。
def del_repeat_element(list1):
for i in list1:
if(list1.count(i)):
list1.remove(i)
del_repeat_element(list1)
break
这种函数注意，可以在调用自身函数之后要加一个break语句，中断后面的遍历（有时候不写break语句，可能逻辑会出问题，因为一旦调用了自身，当前层函数的处理就完成了，如果不中断for循环，将会做多余的处理，结果就错了。在这个函数中加不加break语句结果相同，只是因此删除重复元素是一个幂等操作，即便多处理即便也不会出错）。
2、第二种是返回的结果是一个列表或者是一系列类似的值，比如求一个正整数的所有质因数。这种使用生成器比较方便，就是每产生一个数值就yield返回出去，剩下的继续往下执行。
def resolve_prime(pri_num):
for i in range(2,pri_num+1):
if(pri_num%i == 0):
yield i
pri_num = int(pri_num/i)
for j in resolve_prime(pri_num):
yield j
break
生成器类型的递归函数，再调用自己时，注意要用for来遍历（因为它本身是一个可迭代对象）。这种一旦调用了自己，当前层的循环就必须break掉。不然等所有的递归函数执行完之后，返回到最外层的函数时，还是会将未循环完的for继续执行下去。结果就是错的了。
3、第三种递归是如同开篇中的示例那样，入参为2个或者多个，返回的是其中的一个，这种参数为同一类型的对象，具有相同的结构。由于需要的结果不确定是处理之后的哪一个，因此需要有返回值
def traverse_dept(dept, d1):
tmp = copy.deepcopy(d1)
if(dept.id == d1.parentid):
dept.children.append(d1)
elif(d1.id == dept.parentid):
d1.children.append(dept)
else:
for dept_tmp in dept.children:
traverse_dept(dept_tmp, d1)
return d1 if(tmp != d1) else dept
dept组织树，d1是单个的组织，此函数是查找两者是否有上下级关系，如果有，则返回合并之后的组织，如果没有则返回dept。合并也有两种情况，dept合并到d1下，或者d1合并到dept下。在判断了dept和d1没有直接的关系之后，再查看d1与dept的子级有没有关系，在后面的循环调用中，d1就只可能是dept某一子级的的子级了，相当于d1只会合并到dept中，因此后面调用自己的过程中，返回的是只可能是dept，不可能是d1，就不需要接受函数的返回值了。最后返回最外层函数处理的结果就行了。
def convert_list_to_tree(dept, list1):
if(len(list1)==0):
return dept
for i in list1:
tmp = copy.deepcopy(dept)
dept = traverse_dept(dept, i)
if(tmp != dept):
list1.remove(i)
dept = convert_list_to_tree(dept, list1)
return dept
# return dept
上面这个函数是list1中的对象转换成一个树形结构，其中dept是list1中的一员。注意，此函数虽然返回的都是dept，但是dept经过函数traverse_dept(dept, i)处理之后，可能不是同一个对象了，因此不能在for循环之后返回dept，写在最外层，则最终返回的最外层的dept值，而递归里面处理之后的没有返回出来。所以，要将返回语句放在循环里面，递归之后，这样dept就会一层一层返回出来，最终返回的才是经过层层处理之后的dept。