이진 트리에 단순 목록으로 변환하는 방법

Question

이의 내가 목록과 같이 있다고 가정 해 봅시다 :

flat_list = [None, 10, 5, 15, None, None, 11, 22] 

내가 아는 자리 잡고 목록에서 트리를 생성하는 알고리즘은 같이 간다 :

def create_tree_from_nested_list(node_list): 
    if not node_list: 
     return node_list 
    d, l, r = node_list 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_nested_list(l)) 
    tree.set_right(create_tree_from_nested_list(r)) 
    return tree 

코드의 출력은 위의 것 :

10 
(l) 5 
(r) 15 
(l)  11 
(r)  22 

어떻게 나무에 평면 목록에 함수를 만드는 방법에 대해 갈 것이라고 있도록 왼쪽 사람 인덱스 위치 2*i에 저장되고 올바른 위치는 인덱스 위치 2 * i + 1에 저장되며 출력은 중첩 목록의 출력과 동일합니다. 어떤 도움을 주셔서 감사합니다.

Answer 1

중첩 목록 코드를 수정하여 일반 목록에서 작업 할 수 있습니다. 하위 트리 목록을 쉽게 나눌 수있는 방법이 없으므로 전체 평면 목록과 함께 빌드하려는 노드의 인덱스를 인수로 전달하는 것이 좋습니다. 지수는 1의 기본이있을 것이다 (그래서 당신은 루트 노드를 통과 할 필요가 없습니다) : (

def create_tree_from_flat_list(node_list, index=1): 
    if index >= len(node_list) or node_list[index] is None: 
     return None 
    d = node_list[index] 
    l = index * 2 
    r = l + 1 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_flat_list(node_list, l)) 
    tree.set_right(create_tree_from_flat_list(node_list, r)) 
    return tree 

그것은이 기능에 별도의 d, l 및 r 변수를 가지고 모든 필수 아니라 그들이 사용 된 곳에서 각각 계산할 수 있습니다). 필자는 함수를 중첩 목록 버전과 더 분명하게 평행하게 만들기 위해이 방법을 사용했습니다. l 및 r은 왼쪽 및 오른쪽 하위 트리의 루트 인덱스입니다.

예 출력 : 귀도의 사랑을

> print(create_tree_from_flat_list([None, 10, 5, 15, None, None, 11, 22])) 
10 
(l) 5 
(r) 15 
(l)  11 
(r)  22