Python树遍历和排序列表中的项目组排序

Question

我正在遍历非二叉树，我有一个函数来计算节点的高度和 child 的数量。我想要做的是首先按高度对我的节点的 child 进行排序，然后在每个高度组内我希望它按 child 的数量排序

例如:

      a
   /     \
  b       c
 /|\     /
d e f   g
       /
      h

所以当我遍历树时:

def orderTree(node):        
   if "children" in node:
        if node['children']:
            node['children'].sort(key=findHeight)
            node['children'].sort(key=countChildren)

            for child in node['children']:
                print(child['name'])
                orderTree(child)

我用这段代码 => a,c,g,h,b,d,e,f但我需要的是=> a,b,d,e,f,c,g,h

知道如何对 python 列表中已排序的项目组进行排序吗？

Answer 1

你要做的叫“多字段排序”，

要按高度对节点列表进行排序，然后按子节点的数量对节点列表进行排序，只需将以下函数作为 key 赋予 sort:

lambda x : (findHeight(x), children(x))

这只是返回一个元组 (height, children)。然后 sort 使用这个元组来比较两个节点。

代码:

def orderTree(node):
   # I combined the two ifs
   if "children" in node and node['children']:
        node['children'].sort(key= lambda x : (findHeight(x), children(x) ) )

        for child in node['children']:
            print(child['name'])
            orderTree(child)

假设我有 A = (a,b) 和 B = (x, y)

这两个元组将像这样进行比较:

def compare_tuple(A, B):
    if A[0] != B[0]: return A[0] < B[0]
    else: return A[1] < B[1]