Создание двоичного (семейного) дерева из текстового файла

Question

Мне нужно написать несколько методов для семейного двоичного дерева, но я застрял на инициализации самого дерева, может ли кто-нибудь помочь мне с ним/указать на какую-то помощь?

class FamilyTree: 

    class Node: 
     def __init__(self, data, left=None, right=None): 
      self.data = data 
      self.left = left 
      self.right = right 
    class Queue: 
     def __init__(self): 
      self.pole = [] 
     def enqueue(self, data): 
      self.pole.append(data) 
     def dequeue(self): 
      if self.is_empty(): 
       return None 
      return self.pole.pop(0) 
     def is_empty(self): 
      return self.pole==[] 
    def __init__(self, file_name): 
     ... 

файл выглядит следующим образом (структура: родитель-ребенок):

Pre-VLA
Мир-Бол
Pre-Каз
Бюстгальтер-Ras
Дра-Луб
Lud- Moj
Сва-Мир
Sta-Pre
Jar-Sta
Каз-Пра
Сва-Jar
VLA-бох
Jar-Луд
бох-Lad
VLA-Sve
бох-VLA
Мир-бох
Бол-Дра
Бол-Бюстгальтер

мне как-то нужно разобрать его в какой-то соответствующей структуры (ДИКТ , touple?), а затем сделать из него дерево. Это двоичное дерево, поэтому у одного родителя самое большее 2 ребенка.

Answer 1

Вот несколько извилистый способ создания (не обязательно двоичного) дерева из вашего файла. Дерево фактически хранится в словаре с отцом как ключи и список детей как значения.

from collections import defaultdict 

nodes = [] 
with open('tree.txt') as f: 
    content = f.readlines() 
    for line in content: 
     for node in line.split('-'): 
      nodes.append(node.rstrip()) 

bTree = defaultdict(list) 
for father, children in zip(nodes[0::2], nodes[1::2]): 
    print 'Inserting (' + father + ', ' + children + ')' 
    bTree[father].append(children) 
print(bTree) 

В зависимости от того, что вам нужно сделать, это может сделать трюк и быть легче реализовать, чем древовидный класс.

Answer 2

Это создает двоичное дерево из вашего файла. Он вызывает исключение для примера файла, который вы указали, поскольку у некоторых из них есть два родителя, поэтому это не действительное дерево.

(я назвал файл «parent_child.txt» и сохранил его, когда код будет сохранен.)

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

    def __str__(self): 
     return self.str_tree() 

    def str_tree(self, level=0): 
     tree = "{space}{data}\n".format(space=" " * level, data=str(self.data)) 
     if self.left is not None: 
      tree += self.left.str_tree(level + 1) 
     if self.right is not None: 
      tree += self.right.str_tree(level + 1) 
     return tree 

    def add_child(self, child): 
     if self.left is None: 
      self.left = child 
     elif self.right is None: 
      self.right = child 
     else: 
      raise Exception("Node {} already has two children".format(self.data)) 

class FamilyTree(object): 
    def __init__(self, file_name): 
     self.root = self.generate_tree_from_file(file_name) 

    def __str__(self): 
     return str(self.root) 

    @staticmethod 
    def generate_tree_from_file(file_name): 
     data_to_node = {} 
     has_parent = set() 
     with open(file_name) as file_handle: 
      for line in file_handle: 
       line = line.rstrip('\n') 
       parent, child = line.split("-") 
       child_node = get_or_create(data_to_node, child) 
       parent_node = get_or_create(data_to_node, parent) 
       if child in has_parent: 
        raise Exception("Multiple parents for child {}".format(child)) 
       has_parent.add(child) 
       parent_node.add_child(child_node) 

     no_parent = data_to_node.viewkeys() - has_parent 
     if len(no_parent) > 1: 
      raise Exception("The tree has more than one root: {}".format(", ".join(no_parent))) 
     return data_to_node[no_parent.pop()] 

def get_or_create(data_to_node, data): 
    if data in data_to_node: 
     return data_to_node[data] 
    data_to_node[data] = Node(data) 
    return data_to_node[data] 

if "__main__" == __name__: 
    print(FamilyTree("parent_child.txt")) 

Он работает для этого файла, в котором каждый ребенок имеет один из родителей:

Pre-Vla 
Mir-Bol 
Pre-Kaz 
Bra-Ras 
Dra-Lub 
Lud-Moj 
Sva-Mir 
Sta-Pre 
Jar-Sta 
Kaz-Pra 
Sva-Jar 
Vla-Boh 
Jar-Lud 
Boh-Lad 
Vla-Sve 
Boh-Vla2 
Mir-Boh2 
Bol-Dra 
Bol-Bra