リンクリストを使用してバイナリツリーをトラバースする

Question

リンクリストを使用してバイナリツリーのプリオーダトラバーサルを実行しようとしています。

class BTNode: 
"""A node in a binary tree.""" 

    def __init__(self: 'BTNode', item: object, 
      left: 'BTNode' =None, right: 'BTNode' =None) -> None: 

     self.item, self.left, self.right = item, left, right 


class LLNode: 
    """A node in a linked list.""" 

    def __init__(self: 'LLNode', item: object, link: 'LLNode' =None) -> None: 

     self.item, self.link = item, link 

    def __str__(self: 'LLNode') -> str: 
     """Return an informative string showing self 

     >>> b = LLNode(1, LLNode(2, LLNode(3))) 
     >>> str(b) 
     '1 -> 2 -> 3' 
     """ 
     return str(self.item) + (' -> ' + str(self.link) if self.link else '') 




def preorder(root: BTNode) -> LLNode: 
    """Return the first node in a linked list that contains every value from the 
    binary tree rooted at root, listed according to an preorder traversal. 

    >>> b = BTNode(1, BTNode(2), BTNode(3)) 
    >>> repr(preorder(b)) 
    'LLNode(1, LLNode(2, LLNode(3)))' 
    >>> b2 = BTNode(4, BTNode(5)) 
    >>> b3 = BTNode(7, b, b2) 
    >>> str(preorder(b3)) 
    '7 -> 1 -> 2 -> 3 -> 4 -> 5' 
    """ 

    return _preorder(root)[0] 

def _preorder(root: BTNode) -> (LLNode, LLNode): 
    """Return the first and last nodes in a linked list that contains every 
    value from the binary tree rooted at root, listed according to an preorder 
    traversal. 
    """ 

    if not root: 
     return None, None 

    left_head, left_tail = _preorder(root.left) 

    right_head, right_tail = _preorder(root.right) 

    # change from right_tail = left_tail to right_tail = left_head 
    if not right_tail: 
     right_tail = left_head 

    if not left_head: 
     left_head = right_head 

    if left_tail: 
     left_tail.link = right_head 

    root_node = LLNode(root.item, left_head) 

    return root_node, right_tail 

私は常に取得しています代わりに '7 - - > 1> 2' 'を7 - > 1 - > 2 - > 3 - > 5 - > 4' 行きがけ機能の私の出力として。なぜ私は確信していません。誰かがこの問題を解決するために私の現在のコードを編集する方法を教えてください。

Answer 1

プリペイドのコードでは、LLNode(value, None)のような返品を処理する際にエラーが発生しているようです。

BTNode(a, BTNode(b), BTNode(c))bとcのどちらも子を持っていない場合は、正しくマージしません。この場合のロジックをもう一度見たいと思うでしょう。

Answer 2

リストの末尾が正しく返されていません。 _preorderの動作をトレースするためのデバッグ計測を追加しました。は、ここに投稿する前に実行する必要があります。デバッグは非常に重要なスキルです。

indent = "" 
def _preorder(root: BTNode) -> (LLNode, LLNode): 
    """Return the first and last nodes in a linked list that contains every 
    value from the binary tree rooted at root, listed according to an preorder 
    traversal. 
    """ 
    global indent 
    print(indent, " ENTER", root.item if root else "NULL") 

    if not root: 
     return None, None 

    indent += " " 
    left_head, left_tail = _preorder(root.left) 
    print (indent, root.item, "Left ", left_head, left_tail, str(left_head)) 
    right_head, right_tail = _preorder(root.right) 
    print (indent, root.item, "Right", right_head, right_tail, str(right_head)) 

    if not right_tail: 
     right_tail = left_tail 

    if not left_head: 
     left_head = right_head 

    if left_tail: 
     left_tail.link = right_head 

    root_node = LLNode(root.item, left_head) 

    print (indent, "LEAVE", root.item, right_tail.item if right_tail else "NULL") 
    indent = indent[2:] 
    return root_node, right_tail 

完全なトラバーサルの出力は以下のとおりです。右側には決して正しくリンクされていないことがわかります。私は修理を学生のための練習として残します。 :-)明らかにOPのUPDATE

、あなたの問題の固定部分TO

ENTER 7 
    ENTER 1 
     ENTER 2 
     ENTER NULL 
     2 Left None None None 
     ENTER NULL 
     2 Right None None None 
     LEAVE 2 NULL 
    1 Left 2 None 2 
     ENTER 3 
     ENTER NULL 
     3 Left None None None 
     ENTER NULL 
     3 Right None None None 
     LEAVE 3 NULL 
    1 Right 3 None 3 
    LEAVE 1 NULL 
    7 Left 1 -> 2 None 1 -> 2 
    ENTER 4 
     ENTER 5 
     ENTER NULL 
     5 Left None None None 
     ENTER NULL 
     5 Right None None None 
     LEAVE 5 NULL 
    4 Left 5 None 5 
     ENTER NULL 
    4 Right None None None 
    LEAVE 4 NULL 
    7 Right 4 -> 5 None 4 -> 5 
    LEAVE 7 NULL 

Main: 7 -> 1 -> 2 

---

応答。さて、あなたは、ノード1の左と右のサブツリーの呼び出しから戻ったときに何が起こるかを見て、適切に線形リストにそれらをリンクしてみましょう：デバッグのため

left_head, left_tail = _preorder(root.left) 
# returns 2, None 
right_head, right_tail = _preorder(root.right) 
# returns 3, None 

if not right_tail: 
    right_tail = left_head 
# right_tail is now node 2; this isn't correct: node 3 should be in that spot. 

if not left_head: 
# left_head is node 2; not an issue now 

if left_tail: 
# left_tail is None; not an issue now 

return root_node, right_tail 
# You return nodes 1 and 2; 
# you never linked node 2 to node 3. 
# You need to fix this.