Python方法没有返回red b的节点对象

Question

我正在用Python实现一个红黑树。我有两个班，红黑树和树节点。__setitem__是在下面显示的代码之外定义的。你知道吗

我的代码的问题是，当我试图将键-1添加到我的树中时，在_put方法中创建了一个TreeNode对象，但是该对象没有正确返回。调用方方法“put”未接收任何对象。你知道吗

代码用于添加键5和2，但是由于某些原因，不能以下面尝试的方式返回键为-1的TreeNode对象。请参阅底部的控制台输出。你知道吗

非常感谢您对我们的任何帮助。谢谢

class RedBlackTree:
  def put(self, key, val):
    if self.root:
        newNode = self._put(key, val, self.root)
        print("put RECEIVED ", newNode)
        print("put has newNode, who's key is ", newNode.key, 
              " and parent's key is ", newNode.parent.key)
        self.rbInsertFixup(newNode)
    else: # there is no root
        self.root = TreeNode(key, val, parent = self.sentinal, 
                             left = self.sentinal,
                             right = self.sentinal)
        newNode = self.root
        self.rbInsertFixup(newNode)

  def _put(self, key, val, currentNode):
    if key < currentNode.key:
        if currentNode.leftChild != self.sentinal:
            self._put(key, val, currentNode.leftChild)
        else: # currentNode has no child
            newNode = TreeNode(key, val, parent = currentNode, 
            left = self.sentinal, right = self.sentinal )
            currentNode.leftChild = newNode
            print("_put RETURNS ", newNode)
            return newNode
    else: # symetric to THEN clause above, with 'left' chnaged to 'right'
    ...
class TreeNode():
  def __init__(self, key, val, 
             left = None, right = None, 
             parent = None, color = 'red'):
    self.key = key
    self.payload = val
    self.leftChild = left
    self.rightChild = right
    self.parent = parent
    self.color = color
    ...
t = RedBlackTree()
t[5] = 'five'
t[2] = 'two'
t[-1] = 'negative one'

控制台输出如下。。。你知道吗

('_put RETURN ', <__main__.TreeNode instance at 0x106bd45a8>)
('put RECEIVED ', <__main__.TreeNode instance at 0x106bd45a8>)
("put has newNode, who's key is ", 2, " and parent's key is ", 5)
('_put RETURN ', <__main__.TreeNode instance at 0x106bd45f0>)
('put RECEIVED ', None)
Traceback (most recent call last):
  File "RB-Tree.py", line 383, in <module>
    t[-1] = 'negative one'
  File "RB-Tree.py", line 105, in __setitem__
    self.put(k, v)
  File "RB-Tree.py", line 35, in put
    print("put has newNode, who's key is ", newNode.key, " and parent's     key is ", newNode.parent.key)
AttributeError: 'NoneType' object has no attribute 'key'

`

Answer 1

返回值未存储在此if子句中

if currentNode.leftChild != self.sentinal:
    self._put(key, val, currentNode.leftChild)

改成

if currentNode.leftChild != self.sentinal:
    newNode = self._put(key, val, currentNode.leftChild)
    return newNode

问题解决了。你知道吗