-1

preorder(t):、postorder(t):、 の3 つの関数を定義する必要がありinorder(t):ます。

各関数は二分木を入力として取り、リストを返します。次に、リストは、ツリー要素がそれぞれのトラバーサルでアクセスされるのと同じ方法で並べられる必要があります (ポストオーダー、プリオーダー、またはインオーダー)。

それぞれのコードを書きましたが、別の関数 ( flat_list()) を呼び出すとエラーが発生し続け、インデックス エラーがスローされます。

if not x or len(x) < 1 or  n > len(x) or x[n] == None:
    IndexError: list index out of range

私のトラバーサル メソッドのコードは次のとおりです。

def postorder(t):
    pass
    if t != None:
        postorder(t.get_left())
        postorder(t.get_right())
    print(t.get_data())

def pre_order(t):
    if t != None:
        print(t.get_data())
        pre_order(t.get_left())
        pre_order(t.get_right())

def in_order(t):
    pass
    if t != None:
        in_order(t.get_left())
        print(t.get_data())
        in_order(t.get_right())

def flat_list2(x,n):
  if not x or len(x) < 1 or  n > len(x) or x[n] == None:
    return None

   bt = BinaryTree( x[n] )
   bt.set_left( flat_list2(x, 2*n))
   bt.set_right(flat_list2(x, 2*n + 1))
 return bt

これは私が flat_list2 を呼び出す方法です

flat_node_list = [None, 55, 24, 72, 8, 51, None, 78, None, None, 25]
bst = create_tree_from_flat_list2(flat_node_list,1)

    pre_order_nodes = pre_order(bst)

    in_order_nodes = in_order(bst)

    post_order_nodes = post_order(bst)

    print( pre_order_nodes)

    print( in_order_nodes)

    print( post_order_nodes)
4

2 に答える 2

0

まず最初に、提供されたコード ブロックでインデントが一貫していないことに気付きました (リビジョンで修正されました)。インデントが一貫していることを確認することが重要Pythonです。そうしないと、物事がすぐに南下します。また、以下のコードでは、あなたt.get_data()がまだif t != Noneあなたpostorder(t)の . 最後に、あなたのメソッド名が質問に記載されている仕様と一致していないことに気付きました。そのため、仕様に準拠するように以下のメソッド名を更新しました (_命名にはありません)。

リストを取得するために必要なことは、トラバーサル メソッドがリストを返してextendから、トラバーサルの各レベルで他のトラバースされた値を含むリストを返すことだけです。これは、データを印刷する代わりに行われます。

def postorder(t):
    lst = []
    if t != None:
        lst.extend(postorder(t.get_left()))
        lst.extend(postorder(t.get_right()))
        lst.append(t.get_data())
    return lst

def preorder(t):
    lst = []
    if t != None:
        lst.append(t.get_data())
        lst.extend(preorder(t.get_left()))
        lst.extend(preorder(t.get_right()))
    return lst

def inorder(t):
    lst = []
    if t != None:
        lst.extend(inorder(t.get_left()))
        lst.append(t.get_data())
        lst.extend(inorder(t.get_right()))
    return lst

これは、各ノードの左右両方の完全な深さまでトラバースし、preorder、postorder、またはのいずれであるかに応じてinorder、トラバースされたすべての要素をトラバースされた順序で追加します。これが発生すると、適切に順序付けられたリストを次のレベルに戻し、そのリストに追加されます。これは、ルート レベルに戻るまで繰り返されます。

現在、IndexErrorからのは、が に等しい可能性があるときflat_listにアクセスしようとしたことが原因である可能性があります。のリスト/配列は からインデックス付けされることに注意してください。つまり、リストの最後の要素はではなくになります。x[n]nlen(x)Python0x[n-1]x[n]

したがって、それを修正するには、に置き換えx[n]ますx[n-1]。そのようです：

def flat_list2(x,n):
    if not x or len(x) < 1 or n < 1 or n > len(x) or x[n-1] == None:
        return None

    bt = BinaryTree( x[n-1] )
    bt.set_left( flat_list2(x, 2*n))
    bt.set_right(flat_list2(x, 2*n + 1))
    return bt
于 2016-02-11T22:11:04.150 に答える