Pythonツリーソートされたリスト内の項目のグループのトラバースとソート

Question

私は非バイナリツリーを走査しています。ノードの高さと子の数を計算する機能があります。私は何をしたいの高さによって最初に私のノードの子を並べ替えることであり、それぞれの高さグループ内の私は、それが子供の数でソートされたい

例：

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

ので、私はツリーを走査する場合：私は F => A、C、G、H、B、D、Eは、行くが、私は必要がG => A、B、D、E、F、Cであり、このコードの

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) 

、h

任意のアイデアソートされたアイテムのグループを並べ替える方法IDEのpythonのリスト？

Answer 1

何をしたいの彼らの高さによって、ノードのリストをソートするには

、「マルチフィールドの並べ替え」と呼ばれ、その後、その数によってれる良いリファレンスです

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

これ単にリターン：子供の単純sort次の関数keyなどを与えますタプル（高さ、子供）。そしてsortはこのタプルを使って2つのノードを比較します。

コード：

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

：

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)と

これらの2つのタプルB = (x, y)を考えてみましょう

Answer 2

あなたが行っているツリートラバーサルのタイプは、プレオーダーと呼ばれます。完全な構造を知らなくてもコードを理解するのは難しいです。しかし、あなたは最初にルートノードから子を見ているように見えます。

私はあなたが最初の子ノードを開いて、その中を行き来したいと思うと思います。先行予約の場合、それは何かのようにすべきです。

node 
node.left 
node.right 

これは http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/