python - 为什么我的参数/对象显示为 NoneType 对象？

Question

我正在自学二叉搜索树，在这个程序中，我在树中插入数据，但发生错误'NoneType'对象没有属性'data'错误。

from collections import deque
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(rnode, data):
    if data > rnode.data:
        insert(rnode.right, data)
        rnode.right.data = data
        return print('Node inserted')
    if data < rnode.data:
        insert(rnode.left, data)
        rnode.left.data = data
        return print('Node inserted')

def bfs():
    q = deque()
    temp = self.root
    while temp:
        print(temp.data)
        q.append(temp.left)
        q.append(temp.right)
        temp = q.popleft()


root = Node(8)
insert(root, 3)
bfs()

错误:

Exception has occurred: AttributeError
'NoneType' object has no attribute 'data'
  File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 9, in insert
    if data > rnode.data:
  File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 14, in insert
    insert(rnode.left, data)
  File "/home/mayank/Documents/datastructures/binarysearchtree.py", line 29, in <module>
    insert(root, 3)

救命!!

Answer 1

您的 insert 函数假定 rnode.right 和 rnode.left 始终引用可以插入值的树，但是如果 rnode 是叶子(最终在插入新值时)，则情况并非如此，insert 需要为新值创建一个新节点。

def insert(rnode, data):
    if data > rnode.data:
        if rnode.right is None:
            rnode.right = Node(data)
        else:
            insert(rnode.right, data)
    if data < rnode.data:
        if rnode.left is None:
            rnode.left = Node(data)
        else:
            insert(rnode.left, data)