Perfect Binary Tree с правильными данными

Question

У меня возникли проблемы с попыткой заполнить данные идеальным бинарным деревом с известным количеством узлов с правильными данными. В принципе, у меня есть реализация, которая создает это:

 7 
    5  6 
1 2 3 4 

Однако, я ищу, чтобы создать дерево, как это:

 7 
    3  6 
1 2 4 5 

Моя текущей реализации для вставки узлов дерева выглядит следующим образом.

def _add_node(self, val, ref = None): 
    # reference to root of tree 
    ref = self.root if ref is None else ref 

    if ref.right is None: 
     ref.right = Node(val, ref) 
     return 
    elif ref.left is None: 
     ref.left = Node(val, ref) 
     return 
    else: 
     parent = (val - 1)/2 
     if parent % 2 == 0: 
      self._add_node(val, ref.left) 
     else: 
      self._add_node(val, ref.right) 

Учитывая x узлы создать дерево с помощью range(x) и вызывая add_node(i) для каждой итерации. Это отлично работает, за исключением того, что его порядок неверен.

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

Answer 1

Это, кажется, проблема с заказом, в который вы вводите данные. Как вы передаете данные?

Также подумайте о своей реализации. Вы проверяете, является ли правильный ребенок пустым, и если вы размещаете узел там. Однако, если вы не переходите на левый узел. Именно здесь происходит эта проблема.

Предполагая, что вы передаете данные в обратном хронологическом порядке, вы начинаете с 7 в корне. Затем вы переместитесь на 6, которые вы разместите в нужном узле. Затем перейдите к 5; вы проверяете, является ли правильный узел пустым, а это не потому, что он заполнен 6, поэтому вы переходите, чтобы проверить, свободен ли левый узел и что он есть. Итак, вы поместите там 5.

Вы видите эту проблему?

Вам нужно выяснить способ обойти эту проблему, но, надеюсь, это было хорошо, помогая вам отлаживать.

Удачи!