Durchlaufen einer binären Struktur mit verknüpften Liste

Question

Ich versuche, eine Preorder-Traversal von binären Baum mit einer verknüpften Liste zu tun.

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 

ich immer immer '7 -> 1 -> 2' anstelle von '7 -> 1 -> 2 -> 3 -> 4 -> 5' als meine Ausgabe in Preorder-Funktion. Ich bin mir nicht ganz sicher warum. Könnte mir bitte jemand sagen, wie ich meinen aktuellen Code bearbeiten kann, um dieses Problem zu beheben?

Answer 1

Sie scheinen einen Fehler in Ihrem Vorbestellung Code zu haben, der Rückgaben wie LLNode(value, None) behandelt.

Insbesondere, wenn Sie durchlaufen, wo weder b noch c Kinder hat, werden Sie nicht ordnungsgemäß zusammengeführt. Sie werden einen anderen Blick auf Ihre Logik für diesen Fall haben wollen.

Answer 2

Sie haben das Ende der Liste nicht korrekt zurückgegeben. Ich fügte etwas Debugging-Instrumentarium hinzu, um den Betrieb von _preorder zu verfolgen - das ist etwas, das Sie tun sollte, bevor Sie hier bekanntgeben. Debugging ist eine kritische Fähigkeit.

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 

Ausgang für den vollständigen Durchlauf ist unten. Sie können sehen, dass Sie nie auf der richtigen Seite richtig verknüpfen; Ich werde die Reparatur als Übung für den Studenten verlassen. :-)

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 

---

REAKTION AUF OP UPDATE

Offensichtlich dass festen Teil des Problems. Nun wollen wir sehen, was passiert, wenn man von den Anrufen Rückkehr für den Knoten 1 linken und rechten Teilbäume, und versuchen, diese richtig in die lineare Liste zu verknüpfen:

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.