python - python中的二叉搜索树递归实现

Question

我正在尝试使用递归在 Python 中实现二叉搜索树。我被困在我的程序中发生的一些无限递归中。我通过传递地址和数据对函数 RecursBST 进行递归调用，直到顶部向下遍历到它的左子或右子的 None 值.

class createnode:
    def __init__(self,data):
        self.root=data
        self.left=None
        self.right=None

class createbinarysearchtree:
    def __init__(self, data = None):
        self.top=None   

    def RecursBST(self,top,data):            
        if self.top is None:
            self.top=createnode(data)                
        elif  self.top.root>data:
            self.top.left=self.RecursBST(self.top.left,data)
        elif  self.top.root<data:
            self.top.right=self.RecursBST(self.top.right,data)

conv=createbinarysearchtree();
conv.RecursBST(conv.top,50)
conv.RecursBST(conv.top,40)

我遇到了以下错误:

 self.top.left=self.RecursBST(self.top.left,data)
RuntimeError: maximum recursion depth exceeded

Answer 1

您的代码缺少提供递归终止条件和更改递归状态的代码:

来自 https://en.wikipedia.org/wiki/Recursion_termination

In computing, recursion termination is when certain conditions are met and a recursive algorithm stops calling itself and begins to return values.This happens only if, with every recursive call, the recursive algorithm changes its state and moves toward the base case.

如果递归永远不会结束，那么它必须遇到最大递归深度限制。

您在代码中不会遇到此问题的唯一情况是没有顶级节点，否则递归是无限的。

有一个很好的工具，您可以使用它来可视化您的代码或其他答案中提供的代码的作用:

http://www.pythontutor.com/

以便您了解实际发生的情况以及这是否是您想要实现的目标。

这是在您的问题的另一个答案中运行 bones.felipe 提供的代码的最终结果:

FMc 对您的问题的评论已经很好地回答了您面临的问题(引用):

Typically a BST has three methods: insert(), delete(), and search(). Your current implementation is confusing things by performing insertion-related work (creating a node) with search-related work. Also, there's a related style note that adds to this general confusion: normally classes are things or nouns (BinarySearchTree or Node) not actions (createnode or createbinarysearchtree).