Question

python里如何用递归法列出一个tree里所有的枝干？

如图这样的tree 如果我想让他return出一个这样的list:[‘6-5-4-3’, ‘6-5-4-0’, '6-5-1', '6-2-1']应该怎么用写代码？谢谢啦！！有分送！！

Answer 1

您好：perm函数输出的是参数list从参数k位置开始，到参数m位置结束的全排列
def perm(list,k,m):
if k==m:
for i in range(m+1): # 递归的结束条件是k==m，在整个递归过程中参数m（即结束位置没有改变），而参数k则每次递归+1
print list[i], # 输出递归结束时的list状态
print
else:
for i in range(k,m+1): # 该循环用来负责生成递归的下一个状态
list[k],list[i]=list[i],list[k] # 将list的k位置与每一个位置i分别交换
perm(list,k+1,m) # 由于k位置与每一个位置i交换，也即k位置所有可能选值都已被穷举，此时只需要继续计算k+1之后的职位即可，因此以k+1为开始位置，结束位置m不变进入下一层递归
list[k],list[i]=list[i],list[k] # 由于list是引用传递，因此需要在位置交换之后重新交换，以保证list不变。