从文本文件创建二进制（家族）树

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): 
     ... 

文件看起来像这样（结构：亲子）：

预Vla的
米尔 - 波尔
预卡兹
抹胸的Ras
DRA-卢巴
Lud-司法部
SVA-米尔
STA-预
将罐站
卡兹-PRA
SVA-JAR
VLA-铃
将罐路德
铃-LAD
VLA-全部
铃-Vla的
米尔 - 铃
波尔-DRA
波尔抹胸

不知何故，我需要解析它以某种适当的结构（字典，touple？），然后从中制作一棵树。这是一棵二叉树，所以一个父母最多有两个孩子。

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