1

私はpythonが初めてで、ツリーの予約注文リストを再帰的に返す関数を作成しようとしています。予約注文リストを取得することはできますが、基本ケースとの再帰的な相互作用から、不要な空のリストが大量に発生します。

コードは次のとおりです。

def BinPreOrder(T):
    if Is_EmptyBinTree(T):
        return []
    else:
        return BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

すべてのノードの値だけのリストの出力を取得するにはどうすればよいですか (空のリストなどはありません)。

本当にありがとう、

4

3 に答える 3

1

演算子を使用して、次notの結果を逆にしますIs_EmptyBinTree(T)。

def BinPreOrder(T):
    if not Is_EmptyBinTree(T):
        return BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

None他の値が明示的に返されない場合、すべての関数は戻ります。

于 2015-10-04T18:06:56.917 に答える
1

答えとしてタプルのタプルではなく、フラットリストが必要だと思います。一番の問題は、

BinRoot(T), BinPreOrder(Left(T)), BinPreOrder(Right(T))

リストではなく、3 つの要素を持つタプルです。再帰呼び出しでもタプルが返されるため、タプルのタプルを終了します。

2 番目の問題は、結果に がすべて出現Noneすることです。何人かがすでに指摘しているように、Python 関数は常にデフォルトで None を返すため、明示的にNone's を避ける必要があります。

次のようなことを試してください：

def BinPreOrder(T):
    if not Is_EmptyBinTree(T):
        answer = [BinRoot(T)] 
        left = BinPreOrder(Left(T))
        if left is not None:
           answer.extend(left) 
        right = BinPreOrder(Right(T))
        if right is not None:
           answer.extend(right)
        return answer

編集:これを行うには、より短く、より明確な方法があります。空のサブツリーに対して None を返す代わりに、空のリストを返すようにします。次に、3 つのリストを連結するだけです。問題自体について考えるのではなく、コードの問題に対処することに集中していました。ごめん

def BinPreOrder(T):
    if Is_EmptyBinTree(T): return []
    return [BinRoot(T)] + BinPreOrder(Left(T)) + BinPreOrder(Right(T))
于 2015-10-04T20:25:58.683 に答える
0

リストを作成し、再帰的に返します。 

def BinPreOrder(T):
    ans=[]
    if T is not None:
        ans.append(T.val)
        ans.extend(BinPreOrder(T.lelt))
        ans.extend(BinPreOrder(T.right))
    return ans
于 2019-04-08T06:47:14.100 に答える