Чтобы лучше понять рекурсивные функции, я пытаюсь создать скрипт 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
моего кода. Как я могу сделать так, чтобы учитывались как левый, так и правый потомки узла?