bester Weg, um einen binären Baum aus einer Liste in Python

Question

Angenommen, jeder Knoten self.left, self.right und self.data, was ist der beste Weg, um einen binären Baum zu konstruieren, nicht ein binärer Suchbaum (BST), aus einer Liste, wo die Zahlen zu konstruieren sind pro Level angegeben. Wo die erste Nummer Level 1 ist, sind die nächsten 2 Level 2, die nächsten 4 sind Level 3 und so weiter. Zum Beispiel

input: [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 

konstruiert einen Baum:

  3 
    / \ 
    5   2 
    /\   /\ 
    1 4  6 7 
    /\ /\  /\ /\ 
8 9 10 11 12 13 14 

Eine Lösung ist:

for node at index i, 
left child index = 2i+1 
right child index = 2i+2 

Sie fragen, ob es andere Möglichkeiten

Answer 1

Hier ist ein Weg, um Ihre Lösung zu implementieren : Erstellen Sie eine Liste von Baumknoten, von denen jeder mit der ursprünglichen Datenliste übereinstimmt. Dann können wir die linken und rechten Links reparieren.

import logging 

logging.basicConfig(level=logging.DEBUG) 
logger = logging.getLogger(__name__) 

class Tree(object): 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 

    def __repr__(self): 
     left = None if self.left is None else self.left.data 
     right = None if self.right is None else self.right.data 
     return '(D:{}, L:{}, R:{})'.format(self.data, left, right) 

def build_tree_breadth_first(sequence): 
    # Create a list of trees 
    forest = [Tree(x) for x in sequence] 

    # Fix up the left- and right links 
    count = len(forest) 
    for index, tree in enumerate(forest): 
     left_index = 2 * index + 1 
     if left_index < count: 
      tree.left = forest[left_index] 

     right_index = 2 * index + 2 
     if right_index < count: 
      tree.right = forest[right_index] 

    for index, tree in enumerate(forest): 
     logger.debug('[{}]: {}'.format(index, tree)) 
    return forest[0] # root 

def main(): 
    data = [3, 5, 2, 1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14] 
    root = build_tree_breadth_first(data) 
    print 'Root is:', root 

if __name__ == '__main__': 
    main() 

Ausgang:

DEBUG:__main__:[0]: (D:3, L:5, R:2) 
DEBUG:__main__:[1]: (D:5, L:1, R:4) 
DEBUG:__main__:[2]: (D:2, L:6, R:7) 
DEBUG:__main__:[3]: (D:1, L:8, R:9) 
DEBUG:__main__:[4]: (D:4, L:10, R:11) 
DEBUG:__main__:[5]: (D:6, L:12, R:13) 
DEBUG:__main__:[6]: (D:7, L:14, R:None) 
DEBUG:__main__:[7]: (D:8, L:None, R:None) 
DEBUG:__main__:[8]: (D:9, L:None, R:None) 
DEBUG:__main__:[9]: (D:10, L:None, R:None) 
DEBUG:__main__:[10]: (D:11, L:None, R:None) 
DEBUG:__main__:[11]: (D:12, L:None, R:None) 
DEBUG:__main__:[12]: (D:13, L:None, R:None) 
DEBUG:__main__:[13]: (D:14, L:None, R:None) 
Root is: (D:3, L:5, R:2) 

Answer 2

Eine Möglichkeit, es zu tun ist, eine fringe der aktuellen Blätter zu bauen.

Unter der Annahme einer Node Klasse:

class Node(object): 
    def __init__(self, data): 
     self.data = data 
     self.left = '*' 
     self.right = '*' 
    def __str__(self): 
     return f'<{self.data}, {self.left}, {self.right}>' # Py 3.6 

Dann können Sie einfach die fringe verwalten und durchlaufen die data:

from collections import deque 

data = [3,5,2,1,4,6,7,8,9,10,11,12,13,14] 
n = iter(data) 
tree = Node(next(n)) 
fringe = deque([tree]) 
while True: 
    head = fringe.popleft() 
    try: 
     head.left = Node(next(n)) 
     fringe.append(head.left) 
     head.right = Node(next(n)) 
     fringe.append(head.right) 
    except StopIteration: 
     break 

print(tree) 
# <3, <5, <1, <8, *, *>, <9, *, *>>, <4, <10, *, *>, <11, *, *>>>, <2, <6, <12, *, *>, <13, *, *>>, <7, <14, *, *>, *>>>