すべてのレベルのツリーを再帰的に解析する

Question

このツリー構造のすべてのレベルを再帰的に解析する最良の方法は何ですか？ 3つのレベルが最初ですが、残りのデータをどのように解析する必要がありますか？これは私が完了できなかったコーディリティテストからのものです。質問にはそれ以上のものがありましたが、これは私が立ち往生した場所です。一般的に

tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None))) 

def recurse(T): 
    calc = 0 
    def do_calc(T, calc): 
     if T ==(): 
      return calc 
     calc += 1 
     return do_calc(T[1:], calc) 
    return do_calc(T, calc) 

print recurse(tree) 

Answer 1

の木の奥行きをにしたいと思われます。ここでは、再帰を持つ典型的な解決策がある：

tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None))) 

def tree_depth(node): 

    if not isinstance(node, tuple): 
     return 1 
    else: 
     return max(tree_depth(subnode) for subnode in node) + 1 

print tree_depth(tree) 

出力はです。

組み込み関数maxとgenerator expressionがサンプルコードで使用されています。

Answer 2

再帰的binary treesでの作業あなただけがあれば、手元にノードを処理し、子どもたちに再帰する必要があります。 「トリック」とは、子どもたち、つまり下位枝を木自体として扱うことです。また、再帰を終了させるエッジ条件を特定する必要があります。

あなたの現在のコードは、最初のノード、あなたのツリーのルートを取るアキュムレータcalcをインクリメントし、再帰的タプルの残りのためdo_calcを呼び出します。これは子供たちに再帰することとは異なります。ルートノードは3タプルであるため、recurse(tree)はを返します。エッジ条件は、空のタプルとの比較です。

あなたがツリーのノードをカウントするようにしたいようだ：

def tree_count(tree): 
    # The edge condition: if a node is falsy (None, empty, what have you), 
    # then terminate the recursion 
    if not tree: 
     return 0 
    # Unpack the node, nicer to work with. 
    value, left, right = tree 
    # Count this node and recurse in to children. 
    return 1 + tree_count(left) + tree_count(right) 

あなたの最終的な目標は、ツリーの値を合計することであろう一方場合：

def tree_sum(tree): 
    # The edge condition 
    if not tree: 
     return 0    
    value, left, right = tree 
    # Sum this value and the values of children, if any 
    return value + tree_sum(left) + tree_sum(right) 

であなたの実際のツリーがk-ary treeであるか、1ノードあたりの子供の量が異なる単なるツリーです：

def tree_sum(tree): 
    if not tree: 
     return 0 
    # This still makes the assumption that the value is the 1st item of 
    # a node tuple 
    value, children = tree[0], tree[1:] 
    # In python3: 
    #value, *children = tree 
    return value + sum(tree_sum(child) for child in children) 

前述のように、コードは、ノードが、提供されたデータの例のように、値を含む第1要素を持つタプルであると仮定します。 実際のデータが表示されていない場合は、より良くするのはいくぶん不可能です。あなたのノードが実際に(left, value, right)タプルかそうである場合は、それに応じて変更してください。