递归二叉搜索树实现 - Python

Question

如何在没有辅助函数的情况下在二叉搜索树 class 中实现递归方法？例如，我下面的代码有 add 和 preorder 函数，这些函数是通过我用来传递必要参数的辅助函数实现的。

到目前为止，我尝试在没有助手的情况下实现其中任何一个的一切都失败了，因为我得到以下代码：

preorder_with_helper:

[8, 4, 2, 6, 12, 10, 14]

预购：

Traceback (most recent call last):
  File "/Users/briannakemp/Documents/coding/python/tree_recursion", line 7, in <module>
    class BST:
  File "/Users/briannakemp/Documents/coding/python/tree_recursion", line 37, in BST
    def preorder(self, root=self.root, data=[]) -> [int]:
NameError: name 'self' is not defined

我做错了什么？我的代码如下：

class TreeNode:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

class BST:
  def __init__(self):
    self.root = None

  def add_with_helper(self, value):
    def helper(root):
      if not root: return TreeNode(value)

      if value > root.value:
        root.right = helper(root.right)

      if value < root.value:
        root.left = helper(root.left)
      
      return root

    self.root = helper(self.root)

  def preorder_with_helper(self) -> [int]:
    def helper(root, data):
      if not root: return data

      data.append(root.value)
      if root.left: helper(root.left, data)
      if root.right: helper(root.right, data)

      return data

    return helper(self.root, [])

  def preorder(self, root=self.root, data=[]) -> [int]:
    if not root: return data

    data.append(root.value)
    if root.left: helper(root.left, data)
    if root.right: helper(root.right, data)

    return data




t = BST()
t.add_with_helper(8)
t.add_with_helper(4)
t.add_with_helper(12)
t.add_with_helper(6)
t.add_with_helper(2)
t.add_with_helper(10)
t.add_with_helper(14)

print(t.preorder_with_helper())
print(t.preorder())

Answer 1

您不能将 self.root 作为参数传递 - 您可以这样做：print(t.preorder(t.root))

此外，我认为您的代码正在调用一个 'helper' 函数，它不是 class BST -

的属性

    def preorder(self, root=None, data=[]) -> [int]:
        if not root: return data

        data.append(root.value)
        if root.left: self.preorder(root.left, data)
        if root.right: self.preorder(root.right, data)

        return data

递归二叉搜索树实现 - Python

Recursive Binary Search Tree Implementation - Python

python

recursion

binary-search-tree