如何使用字典创建二叉树

Question

我想从父项(键(及其子项(值，作为元组(one_child，second_child((的字典中创建一个二叉树：

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

二叉树应在不使用递归的情况下创建。

我的节点类：

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