python中二叉搜索树递归实现

Question

我尝试在python中使用递归实现二进制搜索树。我被程序中发生的无限递归所困住，我通过传递地址和数据对函数RecursBST进行递归调用，直到顶部遍历到左或右子级的无值为止。在

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)

我遇到了以下错误：

^{pr2}$

Answer 1

在中的每个递归调用中似乎都引用了相同的对象：self.RecursBST（自左上角，数据）通过使用'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

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

来自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提供的代码的最终结果，该代码是对您的问题的另一个答案：

{cd2对你的问题给出了一个很好的答案：

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

Answer 3

我已经重构了您的类，使它们的名称有意义（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类上添加“object”。这是Python2.7中引入的一个特性，因此不包含它是一种不好的做法。有关详细信息，请查看this。在

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