2022-05-10 19:50

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

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.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.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'])
``````