二进制搜索树顺序不起作用 (python)

Question

我一直在忙着学习对象和 classes，当我终于觉得我设法围绕如何在 python 中构建二叉搜索树时，我运行成问题。这是我的代码：

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

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

    def add(self,current,value):
        if self.root == None:
            self.root = node(value)
        else:
            if value < current.value:
                if current.left == None:
                    current.left = node(value)
                else:
                    self.add(current.left,value)
            if value > current.value:
                if current.right == None:
                    current.right = node(value)
                else:
                    self.add(current.right,value)

    def visit(self,node):
        print(node.value)

    def inorder(self,current):
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
root = node(2)
Tree.root = root
Tree.add(Tree.root,7)

Tree.inorder(Tree.root)

在运行代码之后，我得到一个错误：AttributeError: 'NoneType' object has no attribute 'left'。错误来自 inorder 函数，显然我插入函数的值是一个没有类型的对象。如您所见，树的根是一个节点对象，因此它应该具有 class 中编码的属性“left”。如果有人可以帮助我解决我的错误，我将不胜感激。提前致谢！

编辑：我应该注意，我检查了根是否是具有 isinstance() 函数的节点，并且确实返回了 True。

Answer 1

我想你应该先检查电流是否 None 然后再访问它的左右。

  def inorder(self, current):
        if current:
            self.inorder(current.left)
            self.visit(current)
            self.inorder(current.right)

Answer 2

您的设计有一些问题。树应该是唯一知道根的对象。您不必传递根目录。请注意这样使用起来更简单：

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

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

    def add(self,value,current=None):
        if not self.root:
            self.root = node(value)
            return

        if not current:
            current = self.root

        if value < current.value:
            if not current.left:
                current.left = node(value)
            else:
                self.add(value,current.left)
        else:
            if not current.right:
                current.right = node(value)
            else:
                self.add(value, current.right)

    def visit(self,node):
        print(node.value)

    def inorder(self,current=-1):
        if current == -1:
            current = self.root
        if not current:
            return
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
Tree.add(2)
Tree.add(7)

Tree.inorder()

二进制搜索树顺序不起作用 (python)

Binary Search Tree inorder not working (python)

python

binary-search-tree