如何使PreOrder，InOrder，PostOrder起作用? [英] How do I get the PreOrder,InOrder,PostOrder to work?
问题描述
我如何使PreOrder，InOrder，PostOrder起作用?
How i get the PreOrder,InOrder,PostOrder to work?
这是我当前的代码和实现，请参见InOrder()，PreOrder()，PostOrder().我有来自Geek4Geek的参考资料( https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/).
Here are my current code and implementation, see InOrder(),PreOrder(),PostOrder(). I have a reference from Geek4Geek (https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/).
当我执行print(bst.InOrder())时，它返回None吗?
When i do a print(bst.InOrder()) it 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
我应该怎么做才能使打印工作正常?
What should I do get the print to work?
推荐答案
代码查看并修复
第一个问题是 size 使用 get 会返回树的值，而不是节点.为了解决这个问题，我们将您的 get 函数重写为 find ，但是这次它返回一个节点-
The first problem is that size uses get which returns a value of the tree, not a node. To fix this we rewrite your get function as find, but this time it returns a node -
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 来获取节点.如果该节点存在，则返回值-
We don't need to duplicate this logic in get. Instead we make a call to find which gets the node. If the node is present, then we return the value -
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 -
Next, in the size function, we will use find to get the node. And similar to how you wrote a put2 helper, we can write size2 which handles the looping -
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)
这意味着我们没有在 Node 类中定义 size -
This means we do not define 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()，但是返回错误的答案.
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
深度
因此，如果我执行depth('B')，则应该返回3.由于B到F，深度级别为3.如果我执行depth('F')，则应该返回0.根F没有深度
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 -
We can write depth very similar to how we wrote 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
您做得很好！您的代码没有问题，如下所示-
And you did a great job! There is no problem with your code, as demonstrated below -
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...这是我分配给我的代码
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 ，我会说这是一个坏习惯.问题在于，所有树逻辑都在类中纠结在一起.在答案的这一部分中，我将向您展示您的 bst 模块的总修订版.
You don't actually need put2 or size2 and I would say they are a bad practice. The problem is that all of the tree logic is tangled up in the class. In this section of the answer, I will show you a total revision of your bst module.
首先，我们从一个基本的 node 接口开始.除了分配属性，我们还需要一个简单的 __ init __ 构造函数.需要 key 和 val . left 和 right 是可选的，如果未指定，则默认为 None -
First we begin with a basic node interface. Instead of assigning properties, all we need a simple __init__ constructor. key and val are required. left and right are optional and default to None if not specified -
# 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 -
Now we write a plain put function. Notice there's no references to special variables like self. Another thing of key importance is that we never mutate (overwrite) nodes by reassigning the left or right properties. Instead a new node is created -
# 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 -
We will continue writing plain functions in this way. Next we define get which is a specialization of 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 .用法将在下面演示-
Here we will deviate with size a bit. This time it will not take a key argument. Instead the caller will be able to call size on any node. Usage will be demonstrated below -
# bst.py (continued)
def size(t):
if not t:
return 0
else:
return 1 + size(t.left) + size(t.right)
如果我们可以从节点列表中构建树，那将很方便.这是对 createBalancedTree 的改进，后者反复调用 .put .我们可以称之为 from_list -
It would be convenient if we could build trees from a list of nodes. This is an improvement from createBalancedTree which calls .put over and over. We can call it 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 -
We can implement from_list easily in our bst module -
# 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 和 from_list .该类中的复杂逻辑为零-
Here's the biggest difference of the module. We write the bst class but it is a simple wrapper around your plain functions, put, find, get, size, and from_list. There is zero complex logic in the 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 模块-
We're all done. We will write our main program which imports from our bst module -
# 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 它！这是编写可重用功能的核心原则:每个功能只能做一个 事情-
Remember how I said size does not take a key argument? That's because it can be called on any node. So to find the size of a specific node, we first find it, then size it! This is a core principle of writing reusable functions: each function should do only 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 模块可以以面向对象的方式(上面)或以功能的方式(下面)使用.这种双重界面使我们的模块具有极大的灵活性，因为它可以用于多种样式-
An understated advantage of the technique we used is that our bst module can be used in an object-oriented way (above) or in a functional way (below). This dual interface makes our module extremely flexible as it can be used in a variety of styles -
# 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've written extensively about the techniques used in this answer. Follow the links to see them used in other contexts with additional explanation provided -
我想反转堆栈，但是我不知道如何使用递归来反转此堆栈…我如何反转堆栈无需使用递归
这篇关于如何使PreOrder，InOrder，PostOrder起作用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
