python 按顺序打印二叉树
我和我的朋友正在做一些使用 Python 3.1 编程的学校作业,但遇到了困难。我们正在编写一棵二叉树,它工作得很好,除非我们想以一种创建句子的方式按顺序打印所有节点(所有单词按顺序依次排成一行)。我们一直在互联网上寻找有关如何进行的线索,并且我们已经在这个小事情上工作了大约两个小时。任何建议/帮助都会很棒。
我们的程序/二叉树:
class Treenode:
def __init__(self, it = None, le = None, ri = None):
self.item = it
self.left = le
self.right = ri
class Bintree:
def __init__(self):
self.item = None
self.left = None
self.right = None
def put(self, it = None):
key = Treenode(it)
if self.item == None:
self.item = key
return
p = self.item
while True:
if key.item < p.item:
if p.left == None:
p.left = key
return
else:
p = p.left
elif key.item > p.item:
if p.right == None:
p.right = key
return
else:
p = p.right
else:
return
def exists(self, it):
key = it
p = self.item
if p == key:
return True
while True:
if key < p.item:
if p.left == None:
return False
else:
p = p.left
elif key > p.item:
if p.right == None:
return False
else:
p = p.right
else:
return
def isEmpty(self):
if self.item == None:
return True
else:
return False
def printtree (Treenode):
if Treenode.left != None:
printtree (Treenode.left)
print (Treenode.item)
if Treenode.right != None:
printtree (Treenode.right)
当我们运行程序时,我们得到一种打印,如下所示:“bintree.Treenode object at 0x02774CB0”,这不是我们想要的。
我们通过运行以下命令来使用树:
import bintree
tree = bintree.Bintree()
print(tree.isEmpty()) # should give True
tree.put("solen")
print(tree.isEmpty()) # should give False
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")
tree.put("upp")
tree.put("himlarunden")
tree.put("manen")
tree.put("seglar")
tree.put("som")
tree.put("en")
tree.put("svan")
tree.put("uti")
tree.put("midnattsstuden")
print(tree.exists("visa")) # should give False
print(tree.exists("ban")) # should give True
tree.printtree() # print sorted
此外,倒数第二行给我们“None”而不是“True”,这很奇怪。
Me and my friend are doing some school work with programming in Python 3.1 and are VERY stuck. We're programming a binary tree and it's working fine except when we want to print all the nodes in inorder in a way that would create a sentence (all the words in inorder just after one another in a row). We have been looking all over the internet for clues as to how to procede and we've been working with this little thing for like two hours. Any advice/help would be awesome.
Our program/Binary tree:
class Treenode:
def __init__(self, it = None, le = None, ri = None):
self.item = it
self.left = le
self.right = ri
class Bintree:
def __init__(self):
self.item = None
self.left = None
self.right = None
def put(self, it = None):
key = Treenode(it)
if self.item == None:
self.item = key
return
p = self.item
while True:
if key.item < p.item:
if p.left == None:
p.left = key
return
else:
p = p.left
elif key.item > p.item:
if p.right == None:
p.right = key
return
else:
p = p.right
else:
return
def exists(self, it):
key = it
p = self.item
if p == key:
return True
while True:
if key < p.item:
if p.left == None:
return False
else:
p = p.left
elif key > p.item:
if p.right == None:
return False
else:
p = p.right
else:
return
def isEmpty(self):
if self.item == None:
return True
else:
return False
def printtree (Treenode):
if Treenode.left != None:
printtree (Treenode.left)
print (Treenode.item)
if Treenode.right != None:
printtree (Treenode.right)
We get a sort of print when we run the program which looks like this: "bintree.Treenode object at 0x02774CB0", which is not what we want.
We use the tree by running this:
import bintree
tree = bintree.Bintree()
print(tree.isEmpty()) # should give True
tree.put("solen")
print(tree.isEmpty()) # should give False
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")
tree.put("upp")
tree.put("himlarunden")
tree.put("manen")
tree.put("seglar")
tree.put("som")
tree.put("en")
tree.put("svan")
tree.put("uti")
tree.put("midnattsstuden")
print(tree.exists("visa")) # should give False
print(tree.exists("ban")) # should give True
tree.printtree() # print sorted
Also, the second last row gives us "None" instead of "True", which is wierd.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
要打印二叉树,如果要打印叶子,则只需打印值;否则,您先打印左孩子,然后打印右孩子。
To print a binary tree, if you are printing a leaf you just print the value; otherwise, you print the left child then the right child.
print(tree.exists("visa"))
返回None
,因为在exists()
的最后一行有return< /code> 语句没有任何值(默认为
None
)。另外,您不应将
printtree
参数命名为Treenode
,因为它是现有类的名称,可能会导致混乱。它应该看起来更像是:另一件事是调用
printtree
- 它是一个函数,而不是Bintree
方法,所以我想你应该将其称为printtree(tree).
print(tree.exists("visa"))
returnsNone
, because in the last line ofexists()
there'sreturn
statement without any value (which defaults toNone
).Also you shouldn't name a
printtree
argumentTreenode
since it's a name of an existing class and that might lead to confusion. It should look more like:Another thing is calling
printtree
- it's a function, notBintree
method, so I suppose you should call itprinttree(tree)
.使测试更容易的一种方法是使用 -assert()- 而不是打印内容然后返回代码。
http://docs.python.org/reference/simple_stmts.html#the -assert-statement
如果条件不成立,则会引发错误。我知道这并不能修复你的错误,但让事情变得不那么模糊总是有助于调试。
One way to make testing easier is to use -assert()- instead of printing things and then referring back to your code.
http://docs.python.org/reference/simple_stmts.html#the-assert-statement
It raises an error if its condition is not true. I know that doesn't fix your bug but making things less ambiguous always helps debugging.
您没有指定 printtree() 的起始情况。您正在定义如何正确地递归树,但是对 printtree() 的调用没有可以开始的节点。尝试设置默认检查以查看参数是否传入,以及参数是否不是从二叉树的头节点开始。
倒数第二行打印 None 的原因是,在您的 contains 方法中,对于查找等于 key 的 `p.item' 的情况,您只有一个“return”,而不是“return True” 。
You are not specifying a starting case for printtree(). You're defining how to recurse through your tree correctly, but your call to printtree() has no node to start at. Try setting a default check to see if a parameter is passed in, and if one isn't start at the head node of the bintree.
The reason your second to last line is printing None is because, in your exists method, you just have a "return", rather than a "return True", for the case of finding a `p.item' that is equal to key.