返回二叉搜索树的最小和最大元素-Python
问题描述
如何向我的BST类添加两个不同的函数来计算给定树中的最小和最大元素？那么最小(自我)函数和最大(自我)函数？目前我无法做到这一点，我有一种感觉，这可能与存储整数有关。我的下面的BST可以按原样存储整数吗？class BTNode:
def __init__(self,d,l,r):
self.data = d
self.left = l
self.right = r
t1 = BTNode(15,None,None)
t2 = BTNode(51,None,None)
t = BTNode(5,t1,t2)
t1 = BTNode(21,None,None)
t1 = BTNode(42,t1,None)
t2 = BTNode(18,None,None)
t2 = BTNode(8,t1,t2)
t = BTNode(2,t,t2)
def toString(t):
if t == None:
return "None"
st = str(t.data)+" -> ["
st += toString(t.left)+", "
st += toString(t.right)+"]"
return st
print(toString(t))
# 2
# /
# 5 8
# / /
# 15 51 42 18
# /
# 21
# Depth-First search
def search(t, d):
if t == None: return False
# input("at node: "+str(t.data))
if t.data == d: return True
if search(t.left,d): return True
return search(t.right,d)
print("
test search for 42 then 43")
print(search(t,42))
print(search(t,43))
def printElemsDFS(t):
if t == None:
return
print(t.data)
printElemsDFS(t.left)
printElemsDFS(t.right)
print("
Print elements DFS")
printElemsDFS(t)
# Depth-First search using a stack (needs the Stack class)
def searchDF(t, d):
s = Stack()
s.push(t)
while s.size() > 0:
ptr = s.pop()
if ptr == None:
continue
print(ptr.data) # not needed, for illustration
if ptr.data == d:
return True
s.push(ptr.right)
s.push(ptr.left)
return False
print("
test now searchDF for 42")
print(searchDF(t,42))
print("
test now searchDF for 43")
print(searchDF(t,43))
# Breadth-First search (needs the Queue class)
def searchBF(t, d):
q = Queue()
q.enq(t)
while q.size() > 0:
ptr = q.deq()
if ptr == None:
continue
print(ptr.data) # not needed, for illustration
if ptr.data == d:
return True
q.enq(ptr.left)
q.enq(ptr.right)
return False
print("
test now searchBF for 42")
print(searchBF(t,42))
print("
test now searchBF for 43")
print(searchBF(t,43))
class BTNode:
def __init__(self,d,l,r):
self.data = d
self.left = l
self.right = r
# def updateChild(self, oldChild, newChild):
# if self.left == oldChild:
# self.left = newChild
# elif self.right == oldChild:
# self.right = newChild
# else: raise Exception("updateChild error")
# prints the node and all its children in a string
def __str__(self):
st = str(self.data)+" -> ["
if self.left != None:
st += str(self.left)
else: st += "None"
if self.right != None:
st += ", "+str(self.right)
else: st += ", None"
return st + "]"
class BST:
def __init__(self):
self.root = None
self.size = 0
def __str__(self):
return str(self.root)
def search(self, d):
ptr = self.root
while ptr != None:
if d == ptr.data:
return True
if d < ptr.data:
ptr = ptr.left
else:
ptr = ptr.right
return False
def add(self, d):
if self.root == None:
self.root = BTNode(d,None,None)
else:
ptr = self.root
while True:
if d < ptr.data:
if ptr.left == None:
ptr.left = BTNode(d,None,None)
break
ptr = ptr.left
else:
if ptr.right == None:
ptr.right = BTNode(d,None,None)
break
ptr = ptr.right
self.size += 1
def add(self, d):
if self.root == None:
self.root = BTNode(d,None,None)
else:
self._addRec(d,self.root)
self.size += 1
def _addRec(self,d,ptr):
if d < ptr.data:
if ptr.left == None:
ptr.left = BTNode(d,None,None)
return
return self._addRec(d,ptr.left)
else:
if ptr.right == None:
ptr.right = BTNode(d,None,None)
return
return self._addRec(d,ptr.right)
def count(self, d):
ptr = self.root
count = 0
while ptr != None:
ptr = self._searchNode(ptr,d)
if ptr != None:
count += 1
ptr = ptr.right
return count
def _searchNode(self, ptr, d):
while ptr != None:
if d == ptr.data:
return ptr
if d < ptr.data:
ptr = ptr.left
else:
ptr = ptr.right
return None
def remove(self,d):
if self.root == None: return
if self.root.data == d:
self.size -= 1
return self._removeRoot()
parentPtr = None
ptr = self.root
while ptr != None:
if ptr.data == d:
self.size -= 1
return self._removeNode(ptr,parentPtr)
parentPtr = ptr
if d < ptr.data:
ptr = ptr.left
else:
ptr = ptr.right
# removes the node ptr from the tree
def _removeNode(self, ptr, parentPtr):
# there are 3 cases to consider:
# 1. the node to be removed is a leaf (no children)
if ptr.left == ptr.right == None:
parentPtr.updateChild(ptr,None)
# 2. the node to be removed has exactly one child
elif ptr.left == None:
parentPtr.updateChild(ptr,ptr.right)
elif ptr.right == None:
parentPtr.updateChild(ptr,ptr.left)
# 3. the node to be removed has both children
else:
# find the min node at the right of ptr -- and its parent
parentMinRNode = ptr
minRNode = ptr.right
while minRNode.left != None:
parentMinRNode = minRNode
minRNode = minRNode.left
# replace the data of ptr with that of the min node
ptr.data = minRNode.data
# bypass the min node
parentMinRNode.updateChild(minRNode,minRNode.right)
def _removeRoot(self):
# this is essentially a hack: we are adding a dummy node at
# the root and call the previous method -- it allows us to
# re-use code
parentRoot = BTNode(None,self.root,None)
self._removeNode(self.root,parentRoot)
self.root = parentRoot.left
t = BST()
t.add("cat")
t.add("car")
t.add("cav")
t.add("cat")
t.add("put")
t.add("cart")
t.add("cs")
print(t)
print(t.count("cat"),t.remove("cat"),t.count("cat"),t.size)
print(t)
print(t.count("cat"),t.remove("cat"),t.count("cat"),t.size)
print(t)
print(t.count("put"),t.remove("put"),t.count("put"),t.size)
print(t)
print(t.count("put"),t.remove("put"),t.count("put"),t.size)
print(t)
解决方案
在二叉搜索树中查找最小值等同于沿着左分支查找。在您的实现中，您可以将最后一个非空值保存在临时变量中，一旦找到None，您只需返回该值即可。最大值等同于右分支之后的值。将以下函数添加到您的BST实现中：
def min(self):
last_seen_value = None
ptr = self.root
while ptr is not None:
last_seen_value = ptr.data
ptr = ptr.left
return last_seen_value
示例：
In [1]: t.min()
Out[1]: 'car'
In [2]: t.max()
Out[2]: 'cs'
相关文章