二叉搜索树 cumsum
Binary search tree cumsum
问题:给定一个二叉搜索树,其中的键是数字,我们将定义操作'cumsum'(shorthand 用于累积和)用小于或等于它的所有键的总和来切换树中每个节点的键。
例如,
在这个例子中,
根中的键 5 切换为值 10:根中的原始键(即 5 )和所有比它小的键(即 2 和 3 )的总和。
密钥 3 与值 5 切换:此节点中的原始密钥(意思是 3 )和所有比它更小的密钥(即 2 )的总和。
最右边节点中的键 12 与值 45 交换:该节点中的原始键(意思是 12 )和所有比它更小的键(即 2、3、5、6、8 和 9 )的总和。
请注意,该方法需要是一个包络递归函数的包络函数。另请注意,方法 cumsum 不会 return 一棵新树,而是会更新树本身(就地)
我的尝试:
def cumsum(T):
def cumsum_rec(node,L):
L.append(node.key)
if node.left != None:
cumsum_rec(node.left,L)
if node.right != None:
cumsum_rec(node.right,L)
count = 0
for val in L:
if val < node.key:
count += val
node.key += count
L = []
cumsum_rec(T.root,L)
解释:我遍历树中的每个节点,我将每个原始节点保存在一个辅助列表中,记为'L'。当遍历所有节点时,我在列表 'L' 中查找所有小于当前节点的节点键,并适当地将当前节点的键更新为键为的所有节点的键的总和小于或等于当前节点的键 .
例如,我的实现适用于上例中的树:
t = Binary_search_tree()
t.insert(5,'A')
t.insert(2,'A')
t.insert(9,'A')
t.insert(3,'A')
t.insert(8,'A')
t.insert(12,'A')
t.insert(6,'A')
看起来:
>>> print(t)
5
______/ |__________
2 9
/ |__ __/ |__
# 3 8 12
/ | __/ | / |
# # 6 # # #
/ |
# #
并对其执行 cumsum 操作后:
>>> cumsum(t)
>>> print(t)
10
______/ |____________
2 33
/ |__ __/ |__
# 5 24 45
/ | __/ | / |
# # 16 # # #
/ |
# #
我的问题:
尽管我的实现有效,但为了学习,我有兴趣查看其他可能的实现。您有替代实施方案吗?不需要使用列表作为递归函数的输入?
附录(二叉搜索树的实现和 Tree_node 类 如果您感兴趣的话):
def printree(t, bykey = True):
"""Print a textual representation of t
bykey=True: show keys instead of values"""
#for row in trepr(t, bykey):
# print(row)
return trepr(t, bykey)
def trepr(t, bykey = False):
"""Return a list of textual representations of the levels in t
bykey=True: show keys instead of values"""
if t==None:
return ["#"]
thistr = str(t.key) if bykey else str(t.val)
return conc(trepr(t.left,bykey), thistr, trepr(t.right,bykey))
def conc(left,root,right):
"""Return a concatenation of textual represantations of
a root node, its left node, and its right node
root is a string, and left and right are lists of strings"""
lwid = len(left[-1])
rwid = len(right[-1])
rootwid = len(root)
result = [(lwid+1)*" " + root + (rwid+1)*" "]
ls = leftspace(left[0])
rs = rightspace(right[0])
result.append(ls*" " + (lwid-ls)*"_" + "/" + rootwid*" " + "|" + rs*"_" + (rwid-rs)*" ")
for i in range(max(len(left),len(right))):
row = ""
if i<len(left):
row += left[i]
else:
row += lwid*" "
row += (rootwid+2)*" "
if i<len(right):
row += right[i]
else:
row += rwid*" "
result.append(row)
return result
def leftspace(row):
"""helper for conc"""
#row is the first row of a left node
#returns the index of where the second whitespace starts
i = len(row)-1
while row[i]==" ":
i-=1
return i+1
def rightspace(row):
"""helper for conc"""
#row is the first row of a right node
#returns the index of where the first whitespace ends
i = 0
while row[i]==" ":
i+=1
return i
#######################################################################
class Tree_node():
def __init__(self, key, val):
self.key = key
self.val = val
self.left = None
self.right = None
def __repr__(self):
return "(" + str(self.key) + ":" + str(self.val) + ")"
class Binary_search_tree():
def __init__(self):
self.root = None
def __repr__(self): #no need to understand the implementation of this one
out = ""
for row in printree(self.root): #need printree.py file
out = out + row + "\n"
return out
def lookup(self, key):
''' return node with key, uses recursion '''
def lookup_rec(node, key):
if node == None:
return None
elif key == node.key:
return node
elif key < node.key:
return lookup_rec(node.left, key)
else:
return lookup_rec(node.right, key)
return lookup_rec(self.root, key)
def insert(self, key, val):
''' insert node with key,val into tree, uses recursion '''
def insert_rec(node, key, val):
if key == node.key:
node.val = val # update the val for this key
elif key < node.key:
if node.left == None:
node.left = Tree_node(key, val)
else:
insert_rec(node.left, key, val)
else: #key > node.key:
if node.right == None:
node.right = Tree_node(key, val)
else:
insert_rec(node.right, key, val)
return
if self.root == None: #empty tree
self.root = Tree_node(key, val)
else:
insert_rec(self.root, key, val)
在此先感谢您的帮助!
这是一种不需要保留额外列表的实现;它只是把数字加起来。
def cumsum(T):
def cumsum_rec(node, initial):
if node is None:
return initial
left = cumsum_rec(node.left, initial)
node.key = left + node.key
right = cumsum_rec(node.right, node.key)
return right
cumsum_rec(T.root, 0)
请注意,不需要对值进行额外的比较(我的代码没有 <
),因为所有这些信息都已包含在树的结构中。
问题:给定一个二叉搜索树,其中的键是数字,我们将定义操作'cumsum'(shorthand 用于累积和)用小于或等于它的所有键的总和来切换树中每个节点的键。
例如,
在这个例子中,
根中的键 5 切换为值 10:根中的原始键(即 5 )和所有比它小的键(即 2 和 3 )的总和。
密钥 3 与值 5 切换:此节点中的原始密钥(意思是 3 )和所有比它更小的密钥(即 2 )的总和。
最右边节点中的键 12 与值 45 交换:该节点中的原始键(意思是 12 )和所有比它更小的键(即 2、3、5、6、8 和 9 )的总和。
请注意,该方法需要是一个包络递归函数的包络函数。另请注意,方法 cumsum 不会 return 一棵新树,而是会更新树本身(就地)
我的尝试:
def cumsum(T):
def cumsum_rec(node,L):
L.append(node.key)
if node.left != None:
cumsum_rec(node.left,L)
if node.right != None:
cumsum_rec(node.right,L)
count = 0
for val in L:
if val < node.key:
count += val
node.key += count
L = []
cumsum_rec(T.root,L)
解释:我遍历树中的每个节点,我将每个原始节点保存在一个辅助列表中,记为'L'。当遍历所有节点时,我在列表 'L' 中查找所有小于当前节点的节点键,并适当地将当前节点的键更新为键为的所有节点的键的总和小于或等于当前节点的键 .
例如,我的实现适用于上例中的树:
t = Binary_search_tree()
t.insert(5,'A')
t.insert(2,'A')
t.insert(9,'A')
t.insert(3,'A')
t.insert(8,'A')
t.insert(12,'A')
t.insert(6,'A')
看起来:
>>> print(t)
5
______/ |__________
2 9
/ |__ __/ |__
# 3 8 12
/ | __/ | / |
# # 6 # # #
/ |
# #
并对其执行 cumsum 操作后:
>>> cumsum(t)
>>> print(t)
10
______/ |____________
2 33
/ |__ __/ |__
# 5 24 45
/ | __/ | / |
# # 16 # # #
/ |
# #
我的问题:
尽管我的实现有效,但为了学习,我有兴趣查看其他可能的实现。您有替代实施方案吗?不需要使用列表作为递归函数的输入?
附录(二叉搜索树的实现和 Tree_node 类 如果您感兴趣的话):
def printree(t, bykey = True):
"""Print a textual representation of t
bykey=True: show keys instead of values"""
#for row in trepr(t, bykey):
# print(row)
return trepr(t, bykey)
def trepr(t, bykey = False):
"""Return a list of textual representations of the levels in t
bykey=True: show keys instead of values"""
if t==None:
return ["#"]
thistr = str(t.key) if bykey else str(t.val)
return conc(trepr(t.left,bykey), thistr, trepr(t.right,bykey))
def conc(left,root,right):
"""Return a concatenation of textual represantations of
a root node, its left node, and its right node
root is a string, and left and right are lists of strings"""
lwid = len(left[-1])
rwid = len(right[-1])
rootwid = len(root)
result = [(lwid+1)*" " + root + (rwid+1)*" "]
ls = leftspace(left[0])
rs = rightspace(right[0])
result.append(ls*" " + (lwid-ls)*"_" + "/" + rootwid*" " + "|" + rs*"_" + (rwid-rs)*" ")
for i in range(max(len(left),len(right))):
row = ""
if i<len(left):
row += left[i]
else:
row += lwid*" "
row += (rootwid+2)*" "
if i<len(right):
row += right[i]
else:
row += rwid*" "
result.append(row)
return result
def leftspace(row):
"""helper for conc"""
#row is the first row of a left node
#returns the index of where the second whitespace starts
i = len(row)-1
while row[i]==" ":
i-=1
return i+1
def rightspace(row):
"""helper for conc"""
#row is the first row of a right node
#returns the index of where the first whitespace ends
i = 0
while row[i]==" ":
i+=1
return i
#######################################################################
class Tree_node():
def __init__(self, key, val):
self.key = key
self.val = val
self.left = None
self.right = None
def __repr__(self):
return "(" + str(self.key) + ":" + str(self.val) + ")"
class Binary_search_tree():
def __init__(self):
self.root = None
def __repr__(self): #no need to understand the implementation of this one
out = ""
for row in printree(self.root): #need printree.py file
out = out + row + "\n"
return out
def lookup(self, key):
''' return node with key, uses recursion '''
def lookup_rec(node, key):
if node == None:
return None
elif key == node.key:
return node
elif key < node.key:
return lookup_rec(node.left, key)
else:
return lookup_rec(node.right, key)
return lookup_rec(self.root, key)
def insert(self, key, val):
''' insert node with key,val into tree, uses recursion '''
def insert_rec(node, key, val):
if key == node.key:
node.val = val # update the val for this key
elif key < node.key:
if node.left == None:
node.left = Tree_node(key, val)
else:
insert_rec(node.left, key, val)
else: #key > node.key:
if node.right == None:
node.right = Tree_node(key, val)
else:
insert_rec(node.right, key, val)
return
if self.root == None: #empty tree
self.root = Tree_node(key, val)
else:
insert_rec(self.root, key, val)
在此先感谢您的帮助!
这是一种不需要保留额外列表的实现;它只是把数字加起来。
def cumsum(T):
def cumsum_rec(node, initial):
if node is None:
return initial
left = cumsum_rec(node.left, initial)
node.key = left + node.key
right = cumsum_rec(node.right, node.key)
return right
cumsum_rec(T.root, 0)
请注意,不需要对值进行额外的比较(我的代码没有 <
),因为所有这些信息都已包含在树的结构中。