对节点和树使用单独 class 的二叉树实现

Question

我是 Python 和数据结构的新手。在学习二叉树时，我发现所有可用的实现都在节点 class 内具有树的方法。

但我想以不同的方式实现它，与节点 class 一起，将有一个二叉树 class，其中将包含二叉树的方法。

这是我想出的代码，但它引发了我传递给函数 insertleft() 和 insertright().

的参数错误

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

class Bt():
    def __init__(self, root):
        self.root = root

    def insertleft(temp.left, data):    
        if (temp.left == None):
            temp.left.data = data
        elif(data<temp.left.data):
            t1 = temp.left
            insertleft(t1.left, data)
        elif(data>temp.left.data):
            t1 = temp.left
            insertright(t1.left, data)

    def insertright(temp.right, data):  
        if (temp.right == None):
            temp.right.data = data
        elif(data<temp.right.data):
            t1 = temp.right
            insertleft(t1.right, data)
        elif(data>temp.right.data):
            t1 = temp.right
            insertright(t1.right, data)


    def insert(self, data):
        temp = self.root
        if(temp.data = None):
            temp.data = data
        elif(data<temp.data):
            insertleft(temp.left, data)
        elif(data>temp.data):
            insertright(temp.right, data)


r = Bt()
r.root = Node(5)
r.insert(4)
r.insert(6)

这些是我收到的错误：

def insertleft(temp.left, data):  
                      ^
SyntaxError: invalid syntax

我不确定正确的语法应该是什么。预先感谢您的帮助

Answer 1

当您定义一个函数时，您还定义您将接受的参数。但是在 class 内部，只要该方法不是静态方法或 class 方法，第一个参数就应该是 self 或表示实例化对象本身的变量。

在您的例子中，您在调用函数时已经传递了 temp.left 和 temp.right 的值。将函数定义更改为仅使用 temp 应该可以正常工作。或者更易读，node 因为那是你实际指的。

您的 insertleft 和 insertright 函数与 insert 做同样的事情，并且没有必要包含它们。只需修改 insert 函数即可。

最终结果应如下所示：

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

class Bt():
    def __init__(self, root=None):  #Added default value
        self.root = Node(root)

    def insert(self, data):
        if self.root.data is None:
            self.root.data = data   #Set the root data if it doesn't exist.
        else:
            self._insert(self.root, data)   #Prime the helper function with root node

    def _insert(self, node, data):    #Insert helper function to do the insertion
        if data < node.data:    #Check if data needs to be inserted on the left
            if node.left is None:   #Set left node if it doesn't exist
                node.left = Node(data)
            else:                   #Else let the left node decide where it goes as a child
                self._insert(node.left, data)
        else:                   #Else data needs to be inserted on the right
            if node.right is None:  #Set right node if it doesn't exist
                node.right = Node(data)
            else:                   #Else let the right node decide where it goes as a child
                self._insert(node.right, data)


r = Bt(5)
r.insert(4)
r.insert(6)

现在您只是缺少打印树和数据的函数...以及访问数据。

Answer 2

二叉搜索树中的每个节点都被视为另一个二叉搜索树。因此我们不需要为 node.

创建单独的 class

对节点和树使用单独 class 的二叉树实现

Binary Tree implementation with Separate class for node and tree

oop

binary-tree

binary-search-tree

data-structures

python-3.x