python - 二分木と連結リスト:

Question

ノードクラスがあるとします：

class Node:

    def __init__(self, data, link=None):
        self.data = data
        self.link = link

class BTNode:

    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

二分探索木の順不同走査の連結リストを作成したい。

私がこれまでに持っているものは次のとおりです。

def inorder(root):

    root = _inorder(root)[0] # return head of linked list

# helper function that returns the head and tail of the linked list. 
def _inorder(root):

    if root is None:
        return None, None

    else:
        temp = Node(root.item)
        if root.left:
            left_head, left_tail = _inorder(root.left)
            left_tail.link = temp
        if root.right:
            right_head, right_tail = _inorder(root.right)
            temp.link = right_head

        return left_head, right_tail

テスト：

if __name__ == '__main__':
    a1 = BTNode('A')
    a2 = BTNode('B')
    a3 = BTNode('C')
    a4 = BTNode('D')
    a5 = BTNode('G')
    a6 = BTNode('E')
    a7 = BTNode('F')
    a1.left = a2
    a1.right = a3
    a2.right = a4
    a4.left = a5
    a3.left = a6
    a3.right = a7
    x = inorder(a1)

ただし、次のエラーが表示されます。

UnboundLocalError: ローカル変数 'left_head' が代入前に参照されました

代わりに次のようなことをすると:

def _inorder(root):

    if root is None:
        return None, None

    else:
        temp = Node(root.item)
        #if root.left:
        left_head, left_tail = _inorder(root.left)
        left_tail.link = temp
        #if root.right:
        right_head, right_tail = _inorder(root.right)
        temp.link = right_head

        return left_head, right_tail

その後、エラーは次のようになります。

Answer 1

最初のケースでは:

    if root.left:
        left_head, left_tail = _inorder(root.left)
        left_tail.link = temp
    if root.right:
        right_head, right_tail = _inorder(root.right)
        temp.link = right_head

    return left_head, right_tail

どちらの if も入力しないと、left_head も right_tail も割り当てられません。

2 番目のエラーは、最初のチェックが原因です。

if root is None:
    return None, None

この割り当てが与えられたもの：

    left_head, left_tail = _inorder(root.left)

left_head と left_tail の両方を None にします。これにより、次の行に表示される爆発が発生します。