트리 파이썬에 새 값 삽입
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로 이동합니다.