트리 파이썬에 새 값 삽입

Nov 24 2020

나는 다음과 같은 나무가 있습니다.

tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]

숫자는 각 노드의 루트를 나타내고 없음은 값이없는 자식을 나타냅니다.

예를 들어, 기본 루트는 4이고 [[None, 1, None], 2, [None, 3, None]]은 왼쪽의 하위 트리이고이 [None, 6, [None, 7, None]] 오른쪽에있는 하위 트리입니다. 왼쪽 서브 트리의 주요 루트는 2 등입니다.

내 문제는이 트리에 값을 삽입하고 싶다는 것입니다.

예를 들어 값 5를 추가하고 싶습니다.

tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]

내 함수는 추가 할 트리와 정수라는 두 개의 인수를 사용합니다. 예를 들어 다음과 같이 재귀 함수를 사용해야합니다.

def insert(tree,int):
    cur = tree
    prev = None
    while cur != None:
        prev = cur
        if int < cur[1]:
            cur = cur[0]
        else :
            cur = cur[2]

미리 감사드립니다

답변

2 Maaddy Nov 24 2020 at 09:00

재귀를 언급 했으므로 다음은 재귀를 사용하는 솔루션입니다.

def insert_node(root, node):
    if root == [None]:  #corner case of an empty tree
        root.append(node)
        root.append(None)   #now root will be : [None, node, None]
        return
    if node <= root[1]:  #we need to go left
        if root[0] == None:
            root[0] = [None, node, None]
            return
        else:
            insert_node(root[0], node)
    else:               #we need to go right
        if root[2] == None:
            root[2] = [None, node, None]
            return
        else:
            insert_node(root[2], node)

솔루션 테스트 :

tree = [None]   #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)

이 함수는 노드를 삽입 할 올바른 위치에 도달 할 때까지 반복적으로 트리를 탐색합니다. 이진 검색 트리이기 때문에 노드 왼쪽에있는 자식이 해당 노드보다 작아야하고 오른쪽에있는 자식이 더 커야한다는 조건을 보장해야합니다. 그렇기 때문에 새 노드와 현재 순회 루트의 비교에 따라 lef / right로 이동합니다.