Я пытаюсь сделать рекурсивную функцию вставки для моего класса двоичного дерева поиска, но когда я его тестирую, он продолжает говорить, что корень равен None после того, как я попытался вставить новый узел. У меня есть класс DSATreeNode, который принимает аргументы для ключа и значения узла, а также определил функцию улулong>() для DSATreeNode.
class DSABinarySearchTree():
def __init__(self):
self._root = None
def insert(self, key, value):
return self._insertRec(key, value, self._root)
def _insertRec(self, key, value, curNode):
if curNode != None:
if key < curNode._key:
if curNode.getLeft() == None:
curNode.setLeft(DSATreeNode(key, value))
else:
self._insertRec(key, value, curNode.getLeft())
elif key > curNode._key:
if curNode.getRight() == None:
curNode.setRight(DSATreeNode(key, value))
else:
self._insertRec(key, value, curNode.getRight())
else:
curNode = DSATreeNode(key, value)
if __name__ == "__main__":
print("Testing tree creation and traversal")
myTree = DSABinarySearchTree()
myTree.insert(1, "one")
print("root: ", str(myTree._root))
def _insertRec(self, key, value, curNode):
if curNode != None:
...
else:
curNode = DSATreeNode(key, value)
Это твоя проблема. Когда вы назначаете curNode
, это обновляет нетself._root
. Он повторно связывает имя curNode
с новым значением (которое затем теряется при выходе из функции).
Похоже, вы ожидаете, что curNode
будет указателем на self._root
, а это не так.