我想递归地拆分一个列表，并最终将其存储在树状结构中。
我的目标是从头开始实现这一点，以便真正理解和学习，也就是说，我对任何提供该功能的模块都不感兴趣。
下面的代码并没有真正起作用，因为我正在努力处理一个需要调用两次的递归函数(对于拆分的两侧(。具体来说，我对代码有以下问题：
- min_size标准不成立
- 输出的形式应该是我可以跟踪孩子(左/右(和父母。如何以最佳方式实现此功能
有人能给我一些提示吗？如何改进我的代码，它可以正确地递归地分割列表。
任何建议都会有所帮助。谢谢
def _split(data):
'Dummy function to split data'
idx = np.random.randint(0,len(data),1)[0]
lhs, rhs = data[:idx], data[idx:]
return lhs, rhs
def tree(data, min_size=2):
out = []
if (len(data) <= min_size):
out.append(data)
return out
else:
lhs, rhs = _split(data)
out.append(tree(lhs, min_size))
out.append(tree(rhs, min_size))
return out
我把答案放在这里，而不是放在评论中，因为这将允许更丰富的格式，尽管我怀疑这是一个完整的答案。。。
1.尊重min_size
正如我在评论中所说，您必须确保不要拆分小于2*min_size的数组，因为那样您将无法将它们拆分为两个大于或等于min_size的数组。您还必须确保限制拆分索引，以免随机创建小于min_size的数组
def _split(data, min_size):
'Dummy function to split data'
# Create a random split index between `min_size` and `len(data)-min_size`
idx = np.random.randint(min_size,len(data)-min_size+1)
lhs, rhs = data[:idx], data[idx:]
return lhs, rhs
def tree(data, min_size=2):
out = []
if (len(data) < 2*min_size):
# out.append(data)
# You do not have to wrap the final layer in another array
return data
else:
lhs, rhs = _split(data,min_size)
out.append(tree(lhs, min_size))
out.append(tree(rhs, min_size))
return out
从1到12的阵列的输出为：
[[[1, 2], [3, 4]], [[[5, 6], [7, 8]], [[9, 10], [11, 12]]]]
我还用字典实现了一种替代方法，它可能更容易阅读。但它仍然不允许简单地遍历树。
def tree2(data, min_size=2):
if (len(data) < 2*min_size):
# out.append(data)
# You do not have to wrap the final layer in another array
return data
else:
lhs, rhs = _split(data,min_size)
return {
"left": tree2(lhs, min_size),
"right": tree2(rhs, min_size)
}
输出：
{'left': [1, 2], 'right': {'left': {'left': [3, 4], 'right': [5, 6]}, 'right': {'left': {'left': [7, 8], 'right': [9, 10]}, 'right': [11, 12]}}}
关于第二点，我不确定最好的方法，这取决于你期望从数据结构中进行什么样的确切操作。
一个想法是使用类。可能对您的问题进行了稍微过度的设计，但您可以通过使用Tree.parent、Tree.right、Tree.left:来完全遍历树
class Tree:
def __init__(self, data=None, level=0):
self.left = None
self.right = None
self.parent = None
self.data = data
self.level = level
def set_left_right(self, left, right):
self.left = left
self.right = right
def set_parent(self, parent):
self.parent = parent
def __str__(self):
if self.data == None:
data = "*{}*".format(self.level)
else:
data = self.data
if self.left != None and self.right != None:
return "[{}]<-({})->[{}]".format(self.left, data, self.right)
elif self.left != None:
return "[{}]<-({})".format(self.left, data)
elif self.right != None:
return "({})->[{}]".format(data, self.right)
else:
return "({})".format(data)
def tree3(data, min_size=2, level=0):
if (len(data) < 2*min_size):
return Tree(data, level=level)
else:
lhs, rhs = _split(data,min_size)
lhs = tree3(lhs, min_size,level+1)
rhs = tree3(rhs, min_size,level+1)
out = Tree(level=level)
lhs.set_parent(out)
rhs.set_parent(out)
out.set_left_right(lhs, rhs)
return out
print(tree3([1,2,3,4,5,6,7,8,9,10,11,12]))
输出：
[[[([1, 2])]<-(*2*)->[([3, 4, 5])]]<-(*1*)->[([6, 7])]]<-(*0*)->[[([8, 9, 10])]<-(*1*)->[([11, 12])]]