0

リスト内のツリー内のすべての要素を返す関数を書きたいと思います。ただし、グローバル変数の使用は許可されていません。これが私が試したことです：

def traverse(current node):    
    if no left child and no right child:
        return current nodes data
    else:
        if both left child and right child exist:
            return [current nodes data,left_child.traverse(),right_child._traverse()]
        elif no left child:   return [current node's data,right_child.traverse()]
        elif no right child:  return [current node's data,left_child.traverse()]

この例を使用しました: (ルートは 2、左の子は 1、右の子は 3、右の子の右の子は 4)

    2
1      3
          4

このツリーで traverse を呼び出すと、次のように返されました。

[2, 1, [3, 4]]

したがって、唯一の問題は、すべてを 1 つのリストに収めることができないことです。

編集: 呼び出すことができるノード関数の一部を以下に示します: node.data, node.left,node.right

4

2 に答える 2

2

値のリストを返す代わりに、配列を渡し、値を再帰的に配列に追加します。

def traverse(node, arr):
    if node.left:
        traverse(node.left, arr)
    arr.append(node.data)
    if node.right:
        traverse(node.right, arr)
    return arr # this is for convenience so we don't have to store arr

次のように呼び出してリストを取得します。

traverse(node, [])
于 2013-04-05T03:21:23.473 に答える
0

問題は、各関数呼び出しが新しいリストを作成し、それを既存のリストに追加することです。代わりに、子ノードを既存のリストに追加します。

呼び出し間でリストを明示的に渡すことに依存しない再帰的なソリューションを次に示します。

def traverse(node):
    if node.left and node.right:
        return [node.data] + traverse(node.left) + traverse(node.right)
    elif node.left:
        return [node.data] + traverse(node.left)
    elif node.right:
        return [node.data] + traverse(node.right)
    else:
        return [node.data]
于 2013-04-05T03:22:36.960 に答える