'Node' 对象没有用于二叉树实现的属性 'insert'

Question

我知道以前有人问过这类问题，我不是盲目问你们这个问题，因为我已经回答过以前的问题，但我完全不明白。这是下面的代码：

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

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

    def insert(self,data):
        if self.head is None:
            self.head=Node(data)

        if self.head:
            if data<self.head.data:
                if self.head.left is None:
                    self.head.left=Node(data)
                else:
                    self.head.left.insert(data)

            if data>self.head.data:
                if self.head.right is None:
                    self.head.right=Node(data)
                else:
                    self.head.right.insert(data)  #Actual error point

l1=BST()
l1.insert(2)
l1.insert(4)
l1.insert(6) #Getting the error while inserting this

我知道我需要将 insert 方法放入 Node class 或继承 Node class 属性到 BST class 但是我很难实现这两种解决方案，你们能不能请大家引导我完成这两种解决方案，书面代码的解释对我来说真的很有帮助。

你可能会厌倦看到这些问题，你们都是专家，你知道这对初学者来说有多难，尤其是我不想从不清楚的概念开始。

Answer 1

解决这个问题的一种方法是给 Node 一个方法，根据它的值与它自己的值的比较来附加另一个方法，并让树 class 调用它。然后树 class 实例可以调用它的头 Node 来做这件事。下面的代码展示了如何做到这一点。

值得注意的是，我还更改了树 class，因此通过在创建时将 head 设为具有唯一数据值的 Node，树将永远不会为空。这样做意味着唯一需要检查空树的时间是在尝试将数据附加到树时引发 TypeError 时——而不是一遍又一遍地递归地在 Node.attach() 方法。以这种方式实现它使代码更简单并且运行更快。检查是通过查看树的头部是否不是不可能是真实数据的特殊值来完成的。

这样的特殊值被称为“sentinel values" and it's important to make sure they're distinguishable from any possible legal value. In Python you can create an instance of the built-in (largely featureless) object class 得到一个。

class BinaryTree:
    SENTINEL = object()  # Unique value.

    def __init__(self):
        self.head = Node(self.SENTINEL)

    def insert(self, data):
        try:
            self.head.attach(data)
        except TypeError:
            if self.head.data is self.SENTINEL:  # Empty tree?
                self.head.data = data  # First is special case.
            else:
                raise

    def print(self):
        self.head.print()
        print()


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

    def attach(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.attach(data)
        elif data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.attach(data)

    def print(self):
        if self.left:
            self.left.print()
        print(self.data, end=' ')
        if self.right:
            self.right.print()


if __name__ == '__main__':

    tree = BinaryTree()
    tree.insert(2)
    tree.insert(4)
    tree.insert(6)
    tree.print()  # -> 2 4 6

'Node' 对象没有用于二叉树实现的属性 'insert'

'Node' object has no attribute 'insert' for Binary Tree Implementation

python

python-3.x

data-structures

binary-search-tree

object-reference