我试图在python中实现trees ds,但无法理解我做错了什么?

fcipmucu  于 2021-08-20  发布在  Java
关注(0)|答案(3)|浏览(402)

这是我用过的代码。
节点类

class Node:
    def __init__(self,val):
        self.data = val
        self.leftChild = None
        self.rightChild = None

类树:

def __init__(self,val):
    self.root = Node(val)
    self.head = self.root

插入函数

def insert(self,val):
        head = self.root
        if head:
            if val > head.data:
                if not head.rightChild:
                    head.rightChild = Tree(val)
                    print("{} inserted in Right Tree".format(val))
                else:
                    head.rightChild.insert(val)
            elif val < head.data:
                if not head.leftChild:
                    head.leftChild = Tree(val)
                    print("{} inserted in Left Tree".format(val))
                else:
                    head.leftChild.insert(val)

遍历函数

def inorder(self): 
    head = self.head
    if head:
        head.leftChild.inorder() #line 33
        print(head.data) #line 34
        head.rightChild.inorder() #line 35

这里有一些明显的错误,因为当我执行主函数时:

if __name__ == "__main__":
    n = int(input("Enter the value for the root node : "))
    a = list(map(int,input("Enter the values to be inserted in the tree : ").split()))
    root = Tree(5)
    for i in a:
        root.insert(i)
    #print(root.data) #line 56
    #print(root.leftChild.data) #line 57
    #print(root.rightChild.data) #line 58
    #root.inorder() #line59

以下是我遇到的错误:
在运行print(root.data)、print(root.leftchild)和root.(rightchild)时

Enter the value for the root node : 5
Enter the values to be inserted in the tree : 1 6
1 inserted in Left Tree
6 inserted in Right Tree
Traceback (most recent call last):
  File "trees.py", line 56, in <module>
    print(root.data)
AttributeError: 'Tree' object has no attribute 'data'

在运行root.inoorder()时

Enter the value for the root node : 5
Enter the values to be inserted in the tree : 1 6
1 inserted in Left Tree
6 inserted in Right Tree
Traceback (most recent call last):
  File "trees.py", line 59, in <module>
    root.inorder()
  File "trees.py", line 33, in inorder
    head.leftChild.inorder()
  File "trees.py", line 33, in inorder
    head.leftChild.inorder()
AttributeError: 'NoneType' object has no attribute 'inorder'

请有人详细说明我做错了什么,我应该做什么。还有为什么我错了(如果可能的话)。

zu0ti5jz

zu0ti5jz1#

您的树类init应该如下所示:

class Tree:

    def __init__(self,val):
        self.data = val # value here
        self.leftChild =  # insert left chile here
        self.rightChild = # insert right child here

        self.root = Node(val)
        self.head = self.root

您试图从类树中获取数据,但没有提到类中的值数据,leftchild和right child也是如此

ecfsfe2w

ecfsfe2w2#

您的inorder函数检查head是否正确 NONE 但若海德的左或右孩子是 NONE 然后你打电话来 .inorder()NONE 这是一个错误。
对于你应该使用的数据 root.head.data 而不是 root.data 因为树对象没有任何数据变量。

u0njafvf

u0njafvf3#

至于错误: print(root.data) attributeerror:“树”对象没有属性“数据”
这显示了代码中的错误: Node 类示例具有 data 属性,而不是 Tree 类示例。因此,如果要显示根目录的数据,应参考:

root.head.data

但是,您的代码中有更多代码受到这种混淆的影响。请看我回答的第二部分。 head.leftChild.inorder() attributeerror:“非类型”对象没有属性“顺序”
发生这种情况是因为您没有首先检查 head.leftChild 也许是 None . 你的代码只检查了这一点 head 不是 None ,但有时 head.leftChildNone .

其他问题/备注 elif val < head.data: 将跳过已存在的值

当要插入的值已在树中时,将跳过该值。如果这是你的目的,那就好了。然而,如果您希望您的树接受并存储重复的值,那么这应该是正确的 else: .
这个 Tree 类不应同时定义 roothead 成员。
它们在意义上是等价的——你应该只保留一个。因为这是一棵树,所以选择它听起来更合乎逻辑 root 作为一个名字。 head 在链表实现中更常用作名称。
构造 Tree 不应创建根节点。
树可以有0个节点。这是一个有效的概念。所以 Tree 构造函数不应该要求为根节点传递值。它应该只创建没有任何节点的示例,初始化 root 作为 None .
这个 insert 方法不应创建其他 Tree 示例。
它应该创造 Node 直接引用。您的实现将创建一个 Tree 每个值的示例,从而创建一个 Node 每个人。这太过分了,占用的内存比需要的多得多。这个想法就是创造一个 Tree 示例,以及0或更多 Node 示例。
定义一个 insert 方法论 Node .
因为上一点,因为你已经设计了 insert 方法是递归的(这很好),您应该在 Node 班级。这个 Tree 类将有一个简单的 insert 方法调用上具有相同名称的方法 root 成员。
定义一个 inorder 方法论 Node .
与上述相同的原则是: inorder 是递归的,如果要迭代节点,请在 Node 班级。
方法不应设计为打印。
打印应该与这些数据结构实现分开(需要调试时除外)。而不是 inorder 打印,使其产生值。这样,调用者就可以自由地决定他们想对这些值做什么。
以下是您的代码版本,其中考虑了以上几点:

class Node:
    def __init__(self, val):
        self.data = val
        self.leftChild = None
        self.rightChild = None

    def insert(self, val):  # Define on Node class
        if val > self.data:
            if not self.rightChild:
                self.rightChild = Node(val)  # You should create a Node
            else:
                self.rightChild.insert(val)
        else:  # Also store duplicates (if that is what you want)
            if not self.leftChild:
                self.leftChild = Node(val)
            else:
                self.leftChild.insert(val)

    def inorder(self): 
        if self.leftChild:
            yield from self.leftChild.inorder()
        yield self.data   # Don't print. Yield!
        if self.rightChild:
            yield from self.rightChild.inorder()

class Tree:
    def __init__(self):  # No value argument
        # No need for both a head and a root member
        self.root = None

    def insert(self, val):
        if self.root:
            self.root.insert(val)  # Let the Node class do the job
        else:
            self.root = Node(val)  # First node

    def inorder(self): 
        if self.root:
            yield from self.root.inorder()  # Let the Node class do the job

然后,您可以将其用作:

data = [1,2,3,4,5]
tree = Tree()  # Create an instance of the tree without arguments
for val in data:
    tree.insert(val)

# Iterate the values of the tree, and print them.

print(*tree.inorder())

相关问题