Блог

Я хочу создать двоичное дерево из словаря родителей (ключей) и их дочерних элементов (значений в виде кортежей (one_child, second_child)):

 {1:(2,3), 2:(4,5), 4:(6, None), 3:(7,8), ...}   #they are in random order
  

Двоичное дерево должно быть создано без использования рекурсии.

Мой класс Node:

 class Node:
    def __init__(self,key):
        self.left = None
        self.right = None
        self.val = key
  

То, что я пытался, было:
То, что я пробовал, было:

 self.root = self.Node(found_root)
parents = list(dictionary)
p = 0
while (p != len(parents)-1):
    curr_node = self.Node(parents[p], self.Node(dictionary.get(parents[p])[0]),self.Node(dictionary.get(parents[p])[1]))
    p  = 1
  

Вы можете создать пользовательский метод вставки в вашем Node классе, а затем создание дерева может быть выполнено простым итерационным переходом по словарю:

 class Node:
   def __init__(self, head = None):
     self.head, self.left, self.right = head, None, None
   def __contains__(self, head):
     if head == self.head:
        return True
     return (False if self.left is None else head in self.left) or (False if self.right is None else head in self.right)
   def insert(self, head, vals):
     if self.head is None:
        self.head, self.left, self.right = head, Node(vals[0]), Node(vals[1])
     elif self.head == head:
        self.left, self.right = Node(vals[0]), Node(vals[1])
     else:
        getattr(self, 'left' if self.left and head in self.left else 'right').insert(head, vals)

n = Node()
d = {1:(2,3), 2:(4,5), 4:(6, None), 3:(7,8)}
for a, b in d.items():
   n.insert(a, b)
  

Это создает правильное дерево, поскольку можно легко показать, что исходные входные данные могут быть получены путем обхода экземпляра узла:

 def to_dict(_n):
  yield (_n.head, (getattr(_n.left, 'head', None), getattr(_n.right, 'head', None)))
  if _n.left:
    yield from to_dict(_n.left)
  if _n.right:
    yield from to_dict(_n.right)

print(dict(to_dict(n)))
  

Вывод:

 {1: (2, 3), 2: (4, 5), 4: (6, None), 6: (None, None), None: (None, None), 5: (None, None), 3: (7, 8), 7: (None, None), 8: (None, None)}