Заполненное уровнем двоичное дерево

Question

Чтобы лучше понять рекурсивные функции, я пытаюсь создать скрипт Python для двоичного дерева, которое вставляет значения, полностью заполняя уровни, прежде чем перейти к следующей.

Это моя реализация дерева-узла:

class Node:
    def __init__(self, value):
        self.value = value
        self.right_child = None
        self.left_child = None
        self.parent = None

class Tree:
    def __init__(self):
        self.root = None

У меня сейчас проблемы с установкой условий для соответствия этим критериям.

Пример: здесь я добавляю по порядку следующие числа: 12, 5, 18, 2, 9, 15, 19, 13, 17. Таким образом, единственное условие для помещения вещей на следующий уровень - что родитель заполнен.

  _12_______
 /          \
 5       __18_
/ \     /     \
2 9    15_   19
/   \
13  17

Это то, что я имею до сих пор:

def insert(self,value):
    if(self.root==None):
            self.root=Node(value)
    else:
            self._insert(value,self.root)

def _insert(self, value, curNode):
        if(curNode.left_child==None):
                curNode.left_child=Node(value)
                curNode.left_child.parent = curNode

        elif(curNode.right_child==None):
                curNode.right_child=Node(value)    
                curNode.right_child.parent = curNode    

        else:
                self._insert(value,curNode.left_child)

, что дает:

          _12_
         /    \
       __5   18
      /   \
    __2_  9
   /    \
  15_  19
 /   \
13  17

Таким образом, игнорируя всех правильных детей. Проблема, конечно, в последнем else моего кода. Как я могу сделать так, чтобы учитывались как левый, так и правый потомки узла?

Answer 1

Для этого вам не нужна структура узлов с указателями влево и вправо. Просто сохраните все дерево в массиве, чтобы дочерние элементы узла с индексом N находились в 2*N+1 и 2*N+2:

def print_tree(items, pos, level):
    if pos >= len(items):
        return
    print('.' * level, items[pos])
    print_tree(items, pos * 2 + 1, level + 1)
    print_tree(items, pos * 2 + 2, level + 1)


print_tree([12, 5, 18, 2, 9 , 15, 19, 13, 17], 0, 0)

печать

 12
. 5
.. 2
... 13
... 17
.. 9
. 18
.. 15
.. 19

что ты и хочешь.

Это называется двоичная куча .

Если вы ищете дерево поиска (которое поддерживает порядок значений) и хотите сохранить его сбалансированным, взгляните на https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Answer 2

Не уверен, что это лучший способ сделать это, но я попытался написать что-то похожее на подход, который вы пробовали. Вместо того, чтобы сразу идти к левому узлу, мы записываем оба узла, а затем выполняем итерацию, чтобы мы их увидели. Итак, сначала root, затем root.left, root.right, root.left.left, root.left.right, root.right.left ... и т. Д.

class Node:
    def __init__(self, value):
        self.value = value
        self.right_child = None
        self.left_child = None
        self.parent = None

class Tree:
    def __init__(self):
        self.root = None

    # record nodes that need processing.
    nodes_to_process = []

    def insert(self,value):
        if(self.root==None):
            self.root=Node(value)
        else:
            # add the node to be processed
            self.nodes_to_process.append(self.root)
            self._insert(value)

    def _insert(self,value):
        # the current node is the next node in the list.
        curNode = self.nodes_to_process[0]

        if(curNode.left_child==None):
            curNode.left_child=Node(value)
            curNode.left_child.parent = curNode
            # reset the list, since we've inserted.
            self.nodes_to_process = []

        elif(curNode.right_child==None):
            curNode.right_child=Node(value)    
            curNode.right_child.parent = curNode   
            # reset the list, since we've inserted.
            self.nodes_to_process = []

        else:
            # insert the two child nodes.
            self.nodes_to_process.append(curNode.left_child)
            self.nodes_to_process.append(curNode.right_child)
            # Remove the node we've just examined.
            self.nodes_to_process.pop(0)
            self._insert(value)

Вот быстрый тест.

tree = Tree()        

for number in [12, 5, 18, 2, 9 , 15, 19, 13, 17]:
    tree.insert(number)

print(tree.root.value) # 12
print(tree.root.left_child.value) #5
print(tree.root.left_child.left_child.value) # 2
print(tree.root.left_child.left_child.left_child.value) # 13
print(tree.root.left_child.left_child.right_child.value) # 17

Answer 3

ответ Георга - это умный способ представить это.Однако, если вам интересно, как бы вы работали с древовидной структурой, чтобы получить тот же результат, вы можете разделить проблему на две части: сначала найдите самый мелкий узел, который не завершен, а затем добавьте в него новый узел.Это один из способов сделать это:

class Node:
    def __init__(self, value):
        self.value = value
        self.right_child = None
        self.left_child = None
        self.parent = None

class Tree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            # Find shallowest incomplete node (ignore returned depth)
            node, _ = Tree._next_insertion_node(self.root)
            # Add new node to it
            if node.left_child is None:
                node.left_child = Node(value)
            else:
                node.right_child = Node(value)

    @staticmethod
    def _next_insertion_node(node, level=0):
        # Returns shallowest incomplete node and its depth
        if node.left_child is None or node.right_child is None:
            return node, level
        node_left, level_left = Tree._next_insertion_node(node.left_child, level + 1)
        node_right, level_right = Tree._next_insertion_node(node.right_child, level + 1)
        if level_left <= level_right:
            return node_left, level_left
        else:
            return node_right, level_right

    def print(self):
        Tree._print_node(self.root)

    @staticmethod
    def _print_node(node, level=0):
        if node is None: return
        print(' ' * (level * 2), '*', node.value)
        Tree._print_node(node.left_child, level + 1)
        Tree._print_node(node.right_child, level + 1)

numbers = [12, 5, 18, 2, 9 , 15, 19, 13, 17]
tree = Tree()
for number in numbers:
    tree.insert(number)
tree.print()
# * 12
#   * 5
#     * 2
#       * 13
#       * 17
#     * 9
#   * 18
#     * 15
#     * 19