如何让 PreOrder、InOrder、PostOrder 工作？
How do I get the PreOrder,InOrder,PostOrder to work?
如何让 PreOrder、InOrder、PostOrder 工作？
这是我当前的代码和实现，参见 InOrder()、PreOrder()、PostOrder()。我有来自 Geek4Geek (https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/) 的参考。
当我执行 print(bst.InOrder()) 时 return None?
import os
import pygraphviz as pgv
from collections import deque
from IPython.display import Image, display
class BST:
root=None
def get(self,key):
p = self.root
while p is not None:
if p.key == key:
return p.val
elif p.key > key: #if the key is smaller than current node, then go left (since left are all the small ones)
p = p.left
else: # else if key is bigger than current node, go to right (since right are all the big ones)
p = p.right
return None
def put(self, key, val):
self.root = self.put2(self.root, key, val)
def put2(self, node, key, val):
if node is None:
#key is not in tree, create node and return node to parent
return Node(key, val)
if key < node.key:
# key is in left subtree
node.left = self.put2(node.left, key, val)
elif key > node.key:
# key is in right subtree
node.right = self.put2(node.right, key, val)
else:
node.val = val
return node
# draw the graph
def drawTree(self, filename):
# create an empty undirected graph
G=pgv.AGraph('graph myGraph {}')
# create queue for breadth first search
q = deque([self.root])
# breadth first search traversal of the tree
while len(q) != 0:
node = q.popleft()
G.add_node(node, label=node.key+":"+str(node.val))
if node.left is not None:
# draw the left node and edge
G.add_node(node.left, label=node.left.key+":"+str(node.left.val))
G.add_edge(node, node.left)
q.append(node.left)
if node.right is not None:
# draw the right node and edge
G.add_node(node.right, label=node.right.key+":"+str(node.right.val))
G.add_edge(node, node.right)
q.append(node.right)
# render graph into PNG file
G.draw(filename,prog='dot')
display(Image(filename))
def createTree(self):
self.put("F",6)
self.put('I',9)
self.put("J",10)
self.put("G",7)
self.put("H",8)
# left side of F:6
self.put("D",4)
self.put("C",3)
self.put("B",2)
self.put("A",1)
self.put("E",5)
def createBalancedTree(self):
self.put("F",6)
self.put("A",1)
self.put("B",2)
self.put("C",3)
self.put("D",4)
self.put("E",5)
self.put("G",7)
self.put("H",8)
self.put('I',9)
self.put("J",10)
def find(self, key):
p = self.root
while p is not None:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return
def size(self,key):
return self.size2(self.find(key)) #using the find function which gives the node instead
def size2(self, subtree):
if not subtree: #if given key is not found in entire tree (means not a node in this tree)
return 0
else:
return 1 + self.size2(subtree.left) + self.size2(subtree.right)
def depth(self,key):
p = self.root # set the default node as Root, since we start from Root then top-bottom approach.
if p is not None:
if p.key == key: # if key is root, then return 0 (cus at Root, there is no depth)
return 0
elif p.key > key: # if Key is smaller than current node, then search in the left side
return self.depth2(p.left,key,0)
else: # if key is bigger than current node, search the right side
return self.depth2(p.right,key,0)
def depth2(self,node,key,counter):
# lets say you put a depth(Z), at depth(), it wouldt know Z exits or not, so it will call depth2() to find out. In depth2(), It will check 'Z' throughtout node.key>key and node.key<key..
# still cannot find after all the iteration, then it will return None
if node is not None:
if node.key > key:
return self.depth2(node.left,key,counter+1)
elif node.key < key:
return self.depth2(node.right,key,counter+1)
elif node.key == key:
return counter + 1 # this code will only run when you find your key. So example you do depth(E), it will start from F, then D, then found E. In total 2
else:
return None
def height(self,key):
x = self.root
if x == key:
return 0
else:
return self.height2(self.find(key))
def height2(self,subtree):
if not subtree:
return -1 #Key is not a node in the tree
else:
return max(self.height2(subtree.left), self.height2(subtree.right)) + 1
def InOrder(self):
if self == self.root:
InOrder(self.left)
print(self.key)
InOrder(self.right)
#def PreOrder(self):
#def PostOrder(self):
class Node:
left = None
right = None
key = 0
val = 0
def __init__(self, key, val):
self.key = key
self.val = val
我应该怎么做才能使打印正常工作？
在我看来你的停止条件不正确。 children（和根）的默认值为 None，因此您应该检查 z == None。此外，您似乎在混淆 child 节点和密钥。在我看来，最好的方法是首先找到具有所需键的节点，然后递归地计算该节点上的子树大小。请参阅下面的代码。
# a function in the BST class that finds the node with a specific key
class BST:
def find(self, key):
p = self.root
while p is not None:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return
# the function that you asked about
def getSize(self, key):
subroot = self.find(key)
if subroot:
return subroot.size()
return 0 # if the key is not found return zero
# a function in the node class to find the subtree size with that node as root
class Node:
def size(self):
return 1 + (self.left.size() if self.left else 0) + (self.right.size() if self.right else 0)
代码审查和修复
第一个问题是 size 使用 get，其中 return 是树的 值 ，而不是 节点。为了解决这个问题，我们将您的 get 函数重写为 find，但这次它 return 是一个节点 -
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 来获取节点。如果节点存在，那么我们 return 值 -
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)
这意味着我们没有在Nodeclass-
中定义size
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
身高
Updated with your help as well, i tried the same method for finding height(), but its returning wrong anwers.
我们可以写成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
深度
So if i do a depth('B'), it should return 3. Since B to F, the depth level is 3. And if i do a depth('F'), it should return 0. Since there is no depth in root 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
改进
Could you explain why there is a need for put2 and a need for size2? Sorry, i didnt came out with the put2... it was a given code for my assignment
您实际上并不需要 put2 或 size2，我会说它们是一种不好的做法。问题是所有的树逻辑都在 class 中纠缠在一起。在答案的这一部分，我将向您展示 bst 模块的总修订版。
首先，我们从基本的 node 界面开始。我们不需要分配属性，只需要一个简单的 __init__ 构造函数。 key 和 val 是必需的。 left 和 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 或 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)
我们可以在我们的 bst 模块中轻松实现 from_list -
# bst.py (continued)
def from_list(l):
t = None
for (k,v) in l:
t = put(t, k, v)
return t
这是模块最大的区别。我们编写了 bst class 但它是对普通函数 put、find、get、size 和 from_list。 class -
中的复杂逻辑为零
# 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))
我们都完成了。我们将编写从我们的 bst 模块导入的 main 程序 -
# 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 参数吗？那是因为它可以在任何节点上调用。所以要找到一个特定节点的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
补充阅读
我已经详细介绍了此答案中使用的技术。按照链接查看它们在其他情况下的使用情况，并提供额外的解释 -
I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion
Finding all maze solutions with Python
Return middle node of linked list with recursion
顺序
您应该为关于此代码的每个独特问题打开新的 post。目前的问题与原来的问题有很大的不同。无论如何，按照您现有代码的模式，这就是我可能采用的方法 inorder -
class BST:
# ...
def inorder(self):
return self.inorder2(self.root)
def inorder2(self, t):
if not t: return
yield from self.inorder2(t.left)
yield (t.key, t.val)
yield from self.inorder2(t.right)
另一种写法是使用嵌套函数 -
class BST:
# ...
def inorder(self):
def loop(t):
if not t: return
yield from loop(t.left)
yield t
yield from loop(t.right)
return loop(self.root)
注意 print 是如何从 inorder 函数中分离出来的。这允许调用者使用遍历逻辑并为每个节点选择操作 -
for node in bst.inorder():
print(node.key, node.val)
可重用性
定义 inorder 后，您可以重新定义 BST class -
中的一些其他函数
class BST:
# ...
def find(self, key):
for node in self.inorder():
if node.key == key:
return node
def size(self, key):
p = self.find(key)
if not p: return 0
return sum(1 for _ in BST(p).inorder())
如何让 PreOrder、InOrder、PostOrder 工作？
这是我当前的代码和实现，参见 InOrder()、PreOrder()、PostOrder()。我有来自 Geek4Geek (https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/) 的参考。
当我执行 print(bst.InOrder()) 时 return None?
import os
import pygraphviz as pgv
from collections import deque
from IPython.display import Image, display
class BST:
root=None
def get(self,key):
p = self.root
while p is not None:
if p.key == key:
return p.val
elif p.key > key: #if the key is smaller than current node, then go left (since left are all the small ones)
p = p.left
else: # else if key is bigger than current node, go to right (since right are all the big ones)
p = p.right
return None
def put(self, key, val):
self.root = self.put2(self.root, key, val)
def put2(self, node, key, val):
if node is None:
#key is not in tree, create node and return node to parent
return Node(key, val)
if key < node.key:
# key is in left subtree
node.left = self.put2(node.left, key, val)
elif key > node.key:
# key is in right subtree
node.right = self.put2(node.right, key, val)
else:
node.val = val
return node
# draw the graph
def drawTree(self, filename):
# create an empty undirected graph
G=pgv.AGraph('graph myGraph {}')
# create queue for breadth first search
q = deque([self.root])
# breadth first search traversal of the tree
while len(q) != 0:
node = q.popleft()
G.add_node(node, label=node.key+":"+str(node.val))
if node.left is not None:
# draw the left node and edge
G.add_node(node.left, label=node.left.key+":"+str(node.left.val))
G.add_edge(node, node.left)
q.append(node.left)
if node.right is not None:
# draw the right node and edge
G.add_node(node.right, label=node.right.key+":"+str(node.right.val))
G.add_edge(node, node.right)
q.append(node.right)
# render graph into PNG file
G.draw(filename,prog='dot')
display(Image(filename))
def createTree(self):
self.put("F",6)
self.put('I',9)
self.put("J",10)
self.put("G",7)
self.put("H",8)
# left side of F:6
self.put("D",4)
self.put("C",3)
self.put("B",2)
self.put("A",1)
self.put("E",5)
def createBalancedTree(self):
self.put("F",6)
self.put("A",1)
self.put("B",2)
self.put("C",3)
self.put("D",4)
self.put("E",5)
self.put("G",7)
self.put("H",8)
self.put('I',9)
self.put("J",10)
def find(self, key):
p = self.root
while p is not None:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return
def size(self,key):
return self.size2(self.find(key)) #using the find function which gives the node instead
def size2(self, subtree):
if not subtree: #if given key is not found in entire tree (means not a node in this tree)
return 0
else:
return 1 + self.size2(subtree.left) + self.size2(subtree.right)
def depth(self,key):
p = self.root # set the default node as Root, since we start from Root then top-bottom approach.
if p is not None:
if p.key == key: # if key is root, then return 0 (cus at Root, there is no depth)
return 0
elif p.key > key: # if Key is smaller than current node, then search in the left side
return self.depth2(p.left,key,0)
else: # if key is bigger than current node, search the right side
return self.depth2(p.right,key,0)
def depth2(self,node,key,counter):
# lets say you put a depth(Z), at depth(), it wouldt know Z exits or not, so it will call depth2() to find out. In depth2(), It will check 'Z' throughtout node.key>key and node.key<key..
# still cannot find after all the iteration, then it will return None
if node is not None:
if node.key > key:
return self.depth2(node.left,key,counter+1)
elif node.key < key:
return self.depth2(node.right,key,counter+1)
elif node.key == key:
return counter + 1 # this code will only run when you find your key. So example you do depth(E), it will start from F, then D, then found E. In total 2
else:
return None
def height(self,key):
x = self.root
if x == key:
return 0
else:
return self.height2(self.find(key))
def height2(self,subtree):
if not subtree:
return -1 #Key is not a node in the tree
else:
return max(self.height2(subtree.left), self.height2(subtree.right)) + 1
def InOrder(self):
if self == self.root:
InOrder(self.left)
print(self.key)
InOrder(self.right)
#def PreOrder(self):
#def PostOrder(self):
class Node:
left = None
right = None
key = 0
val = 0
def __init__(self, key, val):
self.key = key
self.val = val
我应该怎么做才能使打印正常工作？
在我看来你的停止条件不正确。 children（和根）的默认值为 None，因此您应该检查 z == None。此外，您似乎在混淆 child 节点和密钥。在我看来，最好的方法是首先找到具有所需键的节点，然后递归地计算该节点上的子树大小。请参阅下面的代码。
# a function in the BST class that finds the node with a specific key
class BST:
def find(self, key):
p = self.root
while p is not None:
if p.key == key:
return p
elif p.key > key:
p = p.left
else:
p = p.right
return
# the function that you asked about
def getSize(self, key):
subroot = self.find(key)
if subroot:
return subroot.size()
return 0 # if the key is not found return zero
# a function in the node class to find the subtree size with that node as root
class Node:
def size(self):
return 1 + (self.left.size() if self.left else 0) + (self.right.size() if self.right else 0)
代码审查和修复
第一个问题是 size 使用 get，其中 return 是树的 值 ，而不是 节点。为了解决这个问题，我们将您的 get 函数重写为 find，但这次它 return 是一个节点 -
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 来获取节点。如果节点存在，那么我们 return 值 -
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)
这意味着我们没有在Nodeclass-
size
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
身高
Updated with your help as well, i tried the same method for finding height(), but its returning wrong anwers.
我们可以写成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
深度
So if i do a depth('B'), it should return 3. Since B to F, the depth level is 3. And if i do a depth('F'), it should return 0. Since there is no depth in root 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
改进
Could you explain why there is a need for
put2and a need forsize2? Sorry, i didnt came out with theput2... it was a given code for my assignment
您实际上并不需要 put2 或 size2，我会说它们是一种不好的做法。问题是所有的树逻辑都在 class 中纠缠在一起。在答案的这一部分，我将向您展示 bst 模块的总修订版。
首先，我们从基本的 node 界面开始。我们不需要分配属性，只需要一个简单的 __init__ 构造函数。 key 和 val 是必需的。 left 和 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 或 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)
我们可以在我们的 bst 模块中轻松实现 from_list -
# bst.py (continued)
def from_list(l):
t = None
for (k,v) in l:
t = put(t, k, v)
return t
这是模块最大的区别。我们编写了 bst class 但它是对普通函数 put、find、get、size 和 from_list。 class -
# 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))
我们都完成了。我们将编写从我们的 bst 模块导入的 main 程序 -
# 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 参数吗？那是因为它可以在任何节点上调用。所以要找到一个特定节点的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
补充阅读
我已经详细介绍了此答案中使用的技术。按照链接查看它们在其他情况下的使用情况，并提供额外的解释 -
I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion
Finding all maze solutions with Python
Return middle node of linked list with recursion
顺序
您应该为关于此代码的每个独特问题打开新的 post。目前的问题与原来的问题有很大的不同。无论如何，按照您现有代码的模式，这就是我可能采用的方法 inorder -
class BST:
# ...
def inorder(self):
return self.inorder2(self.root)
def inorder2(self, t):
if not t: return
yield from self.inorder2(t.left)
yield (t.key, t.val)
yield from self.inorder2(t.right)
另一种写法是使用嵌套函数 -
class BST:
# ...
def inorder(self):
def loop(t):
if not t: return
yield from loop(t.left)
yield t
yield from loop(t.right)
return loop(self.root)
注意 print 是如何从 inorder 函数中分离出来的。这允许调用者使用遍历逻辑并为每个节点选择操作 -
for node in bst.inorder():
print(node.key, node.val)
可重用性
定义 inorder 后，您可以重新定义 BST class -
class BST:
# ...
def find(self, key):
for node in self.inorder():
if node.key == key:
return node
def size(self, key):
p = self.find(key)
if not p: return 0
return sum(1 for _ in BST(p).inorder())