二进制搜索树在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

看起来您在每个递归调用中都引用了同一个对象：自己。RecvesBST（self.top.left，数据）通过使用'self.top'而不是参数'top'的函数。试试这样的东西：

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

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

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

Answer 2

我已经重构了您的类，使它们的名称有意义（Node和BST）。

我认为代码中的主要错误是总是引用“self”，并且总是从同一个实例调用。如果你这样做，你总是在节点上得到相同的数据，这就是为什么你的递归永远不会结束，因为它总是在同一个节点上被阻塞。我认为更容易将节点引用作为参数传递，并从中进行适当的递归调用，此外，您正在分配左变量和右变量，但从不返回任何内容。检查代码：

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

class BST(object):
    def __init__(self):
        self.top = None

    def recursBST(self, node, data):            
        if node is None:
            node = Node(data)                
        elif self.top.root > data:
            node.left = self.recursBST(node.left, data)
        elif  self.top.root < data:
            node.right = self.recursBST(node.right, data)

        return node

    def insert(self, data):
        self.top = self.recursBST(self.top, data)

conv = BST()
conv.insert(8)
conv.insert(3)
conv.insert(6)
conv.insert(1)
conv.insert(-1)
conv.insert(10)
conv.insert(14)
conv.insert(50)

还要记住在任何python类上添加“对象”。这是python 2.7上引入的一个特性，所以不包含它是一种不好的做法。查看此项以获取更多信息。

额外好处：您可以通过执行顺序横切来检查插入算法是否正确，之后，元素应按递增顺序打印（在本例中）。但这取决于你：）

Answer 3

缺少提供递归终止条件并更改递归状态的代码：

从…起https://en.wikipedia.org/wiki/Recursion_termination

在计算中，递归终止是指满足某些条件，递归算法停止调用自己并开始返回值。只有在每次递归调用时，递归算法更改其状态并向基本情况移动时才会发生这种情况。

若递归从未结束，那个么它必须运行到最大递归深度限制。

在代码中没有遇到这个问题的唯一情况是没有顶层节点，否则递归是无限的。

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

http://www.pythontutor.com/

这样你就能对实际发生的事情有一个印象，如果这是你想要实现的。

FMc提供的问题评论已经很好地回答了您面临的问题（引用）：

通常，BST有三种方法：insert（），delete（），和search（）。您当前的实现通过执行与插入相关的工作（创建节点）和与搜索相关的工作来混淆事情。此外，还有一个相关的样式注释增加了这种普遍的混淆：通常类是事物或名词（BinarySearchTree或Node），而不是动作（createnode或createbinarysearchtree）。