python实现二叉搜索树的put()函数，如果键已经在树中，就替换有效载荷，而不是用同一个键插入新节点

Question

class BinarySearchTree:
def init(self):
self.root = None
self.size = 0

def length(self):
    return self.size

def __len__(self):
    return self.size

def __iter__(self):
    return  self.root.__iter__()

class TreeNode:
def init(self,key,val,left=None,right=None,parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent

def hasLeftChild(self):
    return self.leftChild

def hasRightChild(self):
    return self.rightChild

def isLeftChild(self):
    return self.parent and\
           self.parent.leftChild == self

def isRightChild(self):
    return self.parent and\
           self.parent.rightChild == self

def isRoot(self):
    return not self.parent

def isLeaf(self):
    return not (self.rightChild or self.leftChild)

def hasAnyChildren(self):
    return self.rightChild or self.leftChild

def hasBothChildren(self):
    return self.rightChild and self.leftChild

def replaceNodeData(self,key,value,lc,rc):
    self.key = key
    self.payload = value
    self.leftChild = lc
    self.rightChild = rc
    if self.hasLeftChild():
        self.leftChild.parent = self
    if self.hasRightChild():
        self.rightChild.parent = self

def put(selt,key,val):
if selt.root:
selt._put(key,val,selt.root)
else:
selt.root = TreeNode(key,val)
selt.size = selt.size + 1

def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
elif key == currentNode.key:#如果键已在树中，就替换有效载荷
currentNode.val = val
elif key > currentNode.key:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)

if name=='main':
tree = BinarySearchTree()
tree.put('a',2)
tree.put('b',14)
tree.put('c',9)
tree.put('d',7)
tree.put('c',26)

print(tree['c'])

问题:报错该如何修改?我写的put()函数是否正确?

Answer 1

BinarySearchTree类中并没有put方法。
put 方法(移动)放在BinarySearchTree类中。

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    def length(self):
        return self.size
     
    def __len__(self):
        return self.size
     
    def __iter__(self):
        return  self.root.__iter__()
    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
            self.size = self.size + 1
    
    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        elif key == currentNode.key:
            currentNode.val = val
            currentNode.replaceNodeData(currentNode.key,val,currentNode.leftChild,currentNode.rightChild)
        elif key > currentNode.key:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)
         
    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                   return res.payload
            else:
                   return None
        else:
            return None
     
    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)
     
    def __getitem__(self,key):
        return self.get(key)
 
 
class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
 
    def hasLeftChild(self):
        return self.leftChild
     
    def hasRightChild(self):
        return self.rightChild
     
    def isLeftChild(self):
        return self.parent and\
               self.parent.leftChild == self
     
    def isRightChild(self):
        return self.parent and\
               self.parent.rightChild == self
     
    def isRoot(self):
        return not self.parent
     
    def isLeaf(self):
        return not (self.rightChild or self.leftChild)
     
    def hasAnyChildren(self):
        return self.rightChild or self.leftChild
     
    def hasBothChildren(self):
        return self.rightChild and self.leftChild
     
    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self
 
 
if __name__=='__main__':
    tree =BinarySearchTree()
    tree.put('a',2)
    tree.put('b',14)
    tree.put('c',9)
    tree.put('d',7)
    tree.put('c',26)
    print(tree.get('c'))