Как создать двоичное дерево, используя dict?

Question

Я хочу создать двоичное дерево из словаря родителей (ключей) и их потомков (значения в виде кортежей (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

Answer 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)}