代码审查和修复
第一个问题是size uses get它返回一个value树的，不是node。为了解决这个问题，我们重写了你的get充当find，但这次它返回一个节点 -
class BST:
root=None
def put(self, key, val): # ...
def put2(self, node, key, val): # ...
def createTree(self): # ...
def createBalancedTree(self): # ...
def find(self,key):
p = self.root
while p is not None:
if p.key == key:
return p # return p
elif p.key > key:
p = p.left
else:
p = p.right
return None # return None, not "None"
我们不需要重复这个逻辑get。相反，我们打电话给find获取节点。如果节点存在，那么我们返回值 -
class BST:
# ...
def get(self, key):
p = self.find(key) # call to find
if not p:
return None
else:
return p.val # return p.val
接下来，在size函数，我们将使用find来获取节点。类似于你写的put2帮手，我们可以写size2它处理循环 -
class BST:
# ...
def size(self,key):
return self.size2(self.find(key)) # find, not get
def size2(self, subtree): # define size2 like you did put2
if not subtree:
return 0
else:
return 1 + self.size2(subtree.left) + self.size2(subtree.right)
这意味着我们没有定义size in the Node class -
class Node:
left = None
right = None
key = 0
val = 0
def __init__(self, key, val):
self.key = key
self.val = val
# do not define "size" on the Node class
让我们用你的来测试一下createBalancedTree() -
bst = BST()
bst.createBalancedTree()
# F
# / \
# A G
# \ \
# B H
# \ \
# C I
# \ \
# D J
# \
# E
print(bst.size('F')) # 10
print(bst.size('A')) # 5
print(bst.size('H')) # 3
print(bst.size('D')) # 2
height
在您的帮助下也进行了更新，我尝试了相同的方法来查找 height()，但它返回了错误的答案。
我们可以写height如同size -
class BST:
# ...
def height(self,key):
return self.height2(self.find(key))
def height2(self,subtree):
if not subtree:
return 0
else:
return max(self.height2(subtree.left), self.height2(subtree.right)) + 1
depth
因此，如果我执行深度（'B'），它应该返回 3。由于 B 到 F，深度级别为 3。如果我执行深度（'F'），它应该返回 0。因为没有深度在根 F
我们可以写depth和我们写的非常相似find -
class BST:
# ...
def depth(self,key):
p = self.root
d = 0
while p is not None:
if p.key == key:
return d
elif p.key > key:
p = p.left
else:
p = p.right
d = d + 1
return None
你做得很好！您的代码没有问题，如下所示 -
bst2 = BST()
bst2.createTree()
# F
# / \
# D I
# / \ / \
# C E G J
# / \
# B H
# /
# A
print(bst2.depth("F")) # 5
print(bst2.depth("I")) # 3
print(bst2.depth("B")) # 2
print(bst2.depth("Z")) # 0
改进
你能解释一下为什么需要put2以及需要size2？抱歉，我没有带出来put2...这是我的作业的给定代码
你实际上并不需要put2 or size2我想说这是一种不好的做法。问题是所有的树逻辑都在类中纠缠在一起。在答案的这一部分中，我将向您展示您的总体修订版bst module.
首先我们从一个基本的开始node界面。我们不需要分配属性，只需要一个简单的__init__构造函数。key and val是必要的。left and right是可选的，默认为None如果没有指定 -
# bst.py
class node:
def __init__(self, key, val, left = None, right = None):
self.key = key
self.val = val
self.left = left
self.right = right
现在我们写一个简单的put功能。请注意，没有引用特殊变量，例如self。另一件至关重要的事情是，我们永远不会通过重新分配节点来改变（覆盖）节点left or right特性。取而代之的是一个新的node被建造 -
# bst.py (continued)
def put(t, k, v):
if not t:
return node(k, v)
elif k < t.key:
return node(t.key, t.val, put(t.left, k, v), t.right)
elif k > t.key:
return node(t.key, t.val, t.left, put(t.right, k, v))
else:
return node(t.key, v, t.left, t.right)
我们将继续以这种方式编写简单的函数。接下来我们定义get这是一个专业find -
# bst.py (continued)
def get(t, k):
r = find(t, k)
if not r:
return None
else:
return r.val
def find(t, k):
if not t:
return None
elif k < t.key:
return find(t.left, k)
elif k > t.key:
return find(t.right, k)
else:
return t
这里我们将偏离size一点点。这次将不再需要key争论。相反，调用者将能够调用size在任何节点上。下面将演示用法 -
# bst.py (continued)
def size(t):
if not t:
return 0
else:
return 1 + size(t.left) + size(t.right)
如果我们可以从节点列表构建树，那就很方便了。这是一个改进createBalancedTree哪个调用.put一遍又一遍。我们可以称之为from_list -
# main.py
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = bst.from_list(nodes)
我们可以实施from_list轻松地在我们的bst模块 -
# bst.py (continued)
def from_list(l):
t = None
for (k,v) in l:
t = put(t, k, v)
return t
这是该模块最大的区别。我们写的是bst类，但它是普通函数的简单包装，put, find, get, size, and from_list。类中复杂逻辑为零——
# bst.py (continued)
class bst:
def __init__(self, t): self.t = t
def put(self, k, v): return bst(put(self.t, k, v))
def find(self, k): return bst(find(self.t, k))
def get(self, k): return get(self.t, k)
def size(self): return size(self.t)
def from_list(l): return bst(from_list(l))
我们都完成了。我们将写下我们的main从我们导入的程序bst模块 -
# main.py
from bst import bst
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = bst.from_list(nodes)
# F
# / \
# A G
# \ \
# B H
# \ \
# C I
# \ \
# D J
# \
# E
记住我是怎么说的size不需key争论？那是因为它可以在任何节点上调用。所以为了find the size对于一个特定的节点，我们首先find它，那么size它！这是编写可重用函数的核心原则：每个函数应该只做one thing -
print(t.find('F').size()) # 10
print(t.find('A').size()) # 5
print(t.find('H').size()) # 3
print(t.find('D').size()) # 2
功能性的
我们使用的技术的一个低调的优点是我们的bst模块可以以面向对象的方式（上图）或函数式的方式（下图）使用。这种双接口使我们的模块极其灵活，因为它可以用于多种风格 -
# functional.py
from bst import from_list, find, size
nodes = \
[("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]
t = from_list(nodes)
print(size(find(t, 'F'))) # 10
print(size(find(t, 'A'))) # 5
print(size(find(t, 'H'))) # 3
print(size(find(t, 'D'))) # 2
补充阅读
我已经写了大量关于这个答案中使用的技术的文章。点击链接查看它们在其他上下文中的使用情况，并提供附加说明 -
-
在 BST Python 中删除节点 https://stackoverflow.com/a/66340109/633183
-
我想反转堆栈，但我不知道如何使用递归来反转堆栈...如何在不使用递归的情况下反转堆栈 https://stackoverflow.com/a/65532663/633183
-
用Python找到所有迷宫的解决方案 https://stackoverflow.com/a/65512563/633183
-
递归返回链表的中间节点 https://stackoverflow.com/a/61963040/633183
