为什么我的 insert() 函数没有插入新的根节点？

Question

我正在尝试为我的二叉搜索树 class 创建一个递归插入函数，但是当我测试它时，在我尝试插入一个之后它一直说根是 None新节点。我有一个 class DSATreeNode，它接受节点键和值的参数，并且也为 DSATreeNode 定义了 str() 函数。

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

Answer 1

def _insertRec(self, key, value, curNode):
    if curNode != None:
        ...
    else:
        curNode = DSATreeNode(key, value)

这是你的问题。当您分配给 curNode 时，不会更新 self._root。它将名称 curNode 重新绑定到一个新值（然后在函数退出时丢失。）

您似乎希望 curNode 成为指向 self._root 的指针，但事实并非如此。

为什么我的 insert() 函数没有插入新的根节点？

Why is my insert() function not inserting a new root node?

python

recursion

tree

binary-search-tree