python 中的递归 class 定义

Question

对不起，如果我的英语不好，我的母语是韩语。
我正在 Python 3 中实现二叉搜索树，但我无法实现我的目标。
这是代码：

class Node(object):

    def __init__(self, key=None, data=None):
        self.key = key
        self.data = data

class BinarySearchTree(object):
    keyfunc = None  # Will it be worse when using lambda x: x as default?
    
    def __init__(self, node=None):
        self.root = node
        self.left = None
        self.right = None
        # I don't want default to be NoneType, but don't know how for now.

    def add(self, key, data=None):
        node = Node(key, data)
        if self.root is None:
            self.root = node
            return
        parent = self.root.key
        if self.keyfunc is None:
            if key < parent:
                if self.left is None:
                    self.left = __class__(node)
                else:
                    self.left.add(key, data)
                        
            elif key > parent:
                if self.right is None:
                    self.right = __class__(node)
                else:
                    self.right.add(key, data)
        else:
            if keyfunc(key) < keyfunc(parent):
                if self.left is None:
                    self.left = __class__(node)
                else:
                    self.left.add(key, data)
            elif keyfunc(key) > keyfunc(parent):
                if self.right is None:
                    self.right = __class__(node)
                else:
                    self.right.add(key, data)
    def inorder(self):
        if self.root:
            if self.left:
                self.left.inorder()
            print(self.root.key, end=' ')
            if self.right:
                self.right.inorder()

if __name__ == '__main__':
    bst1 = BinarySearchTree()
    arr = [2,6,4,3,2,7,8,1,9,5]
    for key in arr:
        bst1.add(key)
    bst1.inorder()

无论如何都可以，但我想要的是：

即使根节点没有子节点，我也希望 bst1.left（或 bst1.right）的类型始终为 BinarySearchTree。
这样，我可以允许空树与其他树保持一致，并且我也可以删除 add().

if self.left is None

我不想在 class 定义之后手动执行 bst1.left = BinarySearchTree(None)，因为它需要应用于所有节点。

我尝试了self.left = BinarySearchTree(None)（当然结果递归不好），并尝试使用 __new__() 方法和 Metaclasses 作为其他 Whosebug 问题的回答，但无法提出解决方案。
如能得到帮助，将不胜感激

Answer 1

考虑用具有 None 根的空树对象替换 NoneType 子树。另外，为了回答您代码注释中的问题，我认为默认 keyfunc = lambda x: x 是合理的，它进一步简化了您的代码。

class BinarySearchTree:
    def __init__(self, node, keyfunc=lambda x: x):
        self.root = node
        self.keyfunc = keyfunc
        if node is not None:
            self.left = self.new_empty()
            self.right = self.new_empty()

    def new_empty(self):
        """Create a new empty child for this tree"""
        return BinarySearchTree(None, self.keyfunc)
    
    def add(self, key, data=None):
        node = Node(key, data)
        if self.root is None:
            self.root = node
            self.left = self.new_empty()
            self.right = self.new_empty()
        else:
            parent = self.root.key
            if self.keyfunc(key) < self.keyfunc(parent):
                self.left.add(key, data)
            elif self.keyfunc(key) > self.keyfunc(parent):
                self.right.add(key, data)

    def inorder(self):
        if self.root is not None:
            self.left.inorder()
            print(self.root.key, end=' ')
            self.right.inorder()

为了方便使用，您也可以选择添加如下定义：

def __bool__(self):
    return self.root is not None

这让您可以简化测试以查看节点是否为空，方法是在 inorder 方法中执行类似 if self: 而不是 if self.root is not None: 或 if self.left: 来查看如果有左子树而不是 if self.left.root is not None:.

python 中的递归 class 定义

recursive class definition in python

python

recursion

binary-tree

class

recursive-datastructures