3

私はツリーを持っていますが、それは二分木ではないので、すべてのノードを比較し、再帰を使用して最大のノードを返したいと思います。グローバル変数を配置できないため、ローカル変数である必要があるため、追跡方法に問題があります...推測します...しかし、再帰が発生すると、ローカル変数がリセットされます。

def tree_max(node):
    max=1                                                                                     
    if node.left == None and node.right == None:
       if node.value>max:
          max=node.value
          return max
    elif node.left == None and node.right != None:
        return tree_max(node)
    elif node.left != None and node.right == None:
        return tree_max(node.left)
    else:
        return tree_max(node.left)

助言がありますか？

4

3 に答える 3

4

すべての再帰呼び出しで変数の最大値を保持する必要はありません。グローバル呼び出しではありません。適切に構造化された再帰では、結果は各再帰呼び出しの戻り値で渡されます。このような：

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

上記は、がそうでnodeはないことを前提としています。nullになる可能性があるNone場合は、を呼び出す前nodeにこの条件を確認してください。tree_max()

于 2013-02-04T23:26:50.513 に答える
3

木を横切るジェネレーターがあります。これは、トラバーサルロジックを複製せずmin()になどを記述できることを意味しますsum()

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        for v in tree_traverse(node.left):
            yield v
    if node.right:
        for v in tree_traverse(node.right):
            yield v

今、あなたはただ使うことができますmax(tree_traverse(node))

すべてのノードに値がある場合は、最初のノードをスキップしてif、yield

@abarnertが言うように、Python3.3には再帰ジェネレーターを単純化するための優れた方法があります

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        yield from tree_traverse(node.left)
    if node.right:
        yield from tree_traverse(node.right)
于 2013-02-04T23:41:15.897 に答える
1

これは通常、キーワード引数を使用して行われます。

def tree_max(node, max=None):
于 2013-02-04T23:24:53.797 に答える