时间戳

首页 > 解决方案 > “节点”对象没有用于二叉树实现的属性“插入”

python - “节点”对象没有用于二叉树实现的属性“插入”

问题描述

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

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继承到类中，但是我很难实现这两种解决方案，请你们指导我完成这两种解决方案，用书面代码进行解释会非常有帮助我 。NodeBST

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

标签： pythonpython-3.xdata-structuresbinary-search-treeobject-reference

解决方案

解决该问题的一种方法是提供Nodesa 方法，根据其值与自身值的比较情况将另一个附加到它，并让树class调用它。然后树类实例可以调用它的头部Node来执行此操作。下面的代码显示了如何做到这一点。

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

这些特殊值被称为“哨兵值”，确保它们与任何可能的合法值区分开来是很重要的。在 Python 中，您可以创建一个内置（基本上没有功能）object类的实例来获取一个。

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

推荐阅读