python - 在 Python 中实现 BST 的打印 - 重构参数的问题
问题描述
我发现
从 BcK在这里打印 BST 的一个很好的实现。我想在我的代码中实现它,但我真的不知道我应该更改哪些参数的名称以便它可以在我的代码中工作。你能帮我解决这个问题吗?我想我必须改变left
,right
正如他所说,但我不知道我应该改变它。我复制的定义是print_tree
,上面的一切都是我的,所以我只需要改变一些print_tree
东西
class Node:
def __init__(self,x):
self.key = x
self.left = None
self.right = None
self.p = None
class BST:
def __init__(self):
self.root = None
def BSTsearch(self,k):
x = self.root
while x!=None and x.key!=k:
if k<x.key:
x=x.left
else:
x=x.right
return x
def BSTinsert(self, z):
x = self.root
y = None
while x != None:
y=x
if z.key<x.key:
x=x.left
else:
x=x.right
z.p=y
if y==None:
self.root=z
else:
if z.key<y.key:
y.left=z
else:
y.right=z
def bstDelete(self, z):
if z.left == None and z.right == None:
if z == self.root:
self.root = None
else:
if z == z.p.left:
z.p.left = None
else:
z.p.right = None
elif z.left != None and z.right != None:
y = self.bstMinimum(z.right)
z.key = y.key
self.bstDelete(y)
else:
if z.left != None:
z.left.p=z.p
if z==self.root:
self.root=z.left
else:
if z==z.p.left:
z.p.left=z.left
else:
z.p.right=z.left
else:
z.right.p=z.p
if z==self.root:
self.root=z.right
else:
if z==z.p.left:
z.p.left=z.left
else:
z.p.right=z.left
def bstMinimum(self, x):
while x.left != None:
x = x.left
return x
def BSTinOrder(self, x):
if x == None: return
self.BSTinOrder(x.left)
print(x.key)
self.BSTinOrder(x.right)
def bstGetRoot(self):
return self.root
def print_tree(root, val="val", left="left", right="right"):
def display(root, val=val, left=left, right=right):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if getattr(root, right) is None and getattr(root, left) is None:
line = '%s' % getattr(root, val)
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if getattr(root, right) is None:
lines, n, p, x = display(getattr(root, left))
s = '%s' % getattr(root, val)
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if getattr(root, left) is None:
lines, n, p, x = display(getattr(root, right))
s = '%s' % getattr(root, val)
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = display(getattr(root, left))
right, m, q, y = display(getattr(root, right))
s = '%s' % getattr(root, val)
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
lines, *_ = display(root, val, left, right)
for line in lines:
print(line)
tree = BST()
tree.BSTinsert(Node(5))
tree.BSTinsert(Node(3))
tree.BSTinsert(Node(7))
tree.BSTinsert(Node(2))
tree.BSTinsert(Node(4))
tree.BSTinsert(Node(9))
#tree.BSTinOrder(tree.bstGetRoot())
tree.print_tree(tree.bstGetRoot())
解决方案
你快到了。
首先,既然你已经把print_tree
你的类放在你应该把self
它作为第一个参数。
def print_tree(self, root, val="val", left="left", right="right"):
其次,如您所见, 的默认参数print_tree
是根据您对Node
. 也就是说,在您的 中Node
,您已将节点值定义为self.key
,因此传递"key"
给val
参数。
tree.print_tree(tree.bstGetRoot(), val="key")
就是这样 !
推荐阅读
- git - git rebase 和 git reset 的区别
- php - PHP SoapClient - 使用变量创建请求
- c# - 在 Xamarin API 中向用户显示消息
- java - 从 Android 的 WebView 中的 Blob Url 下载 PDF 文件
- python - 循环时使用正则表达式在href中间查找内容
- html - Youtube iframe 自动播放在 Chromium 中不起作用,但在 Manjaro Linux 上的 Firefox 中起作用
- typescript - Hapi.js:“类扩展值未定义不是构造函数或空值”
- android - 无法为导航抽屉 + BottomAppBar 中的选定项目设置颜色/背景选择
- java - 在 JAVA 中对立体声 WAV 文件进行采样 - 获取幅度
- unity3d - 游戏架构 P2P 加入中游