연결된 목록을 사용하여 이진 트리 탐색

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)과 같은 반품 관련 오류가있는 것으로 보입니다.

특히 b 및 c에 자식이있는 BTNode(a, BTNode(b), BTNode(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 

전체 탐색을위한 출력은 다음과 같습니다. 오른쪽에서 절대로 제대로 링크하지 않는다는 것을 알 수 있습니다. 나는 수리를 학생을위한 운동으로 남겨 둘 것입니다. :-) 물론 영업 UPDATE

, 문제의 고정 부분에

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.