我在下面提供了一个将生成如下输出的程序:
100
12 230
8 32 205 323
10 43 201 213 999
39 225
38
37
您可以立即运行它。它以数字作为输入,并将它们添加到 BST,然后打印结果,然后要求下一个输入:
class Node:
def __init__(self, value):
self.value = value
self.left = self.right = None
class BST:
PADDING = 3 # Space between horizontally adjacent node labels
def __init__(self, *values):
self.root = None
for value in values:
self.insert(value)
def insert(self, value):
def insert(root, value):
if not root:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
self.root = insert(self.root, value)
def __repr__(self):
def indent(lines, margin):
if margin >= 0:
return margin
spaces = " " * -margin
lines[:] = [spaces + line for line in lines]
return 0
def merge(left, right):
if not left or not right:
return left or right
offsetright = max(len(leftline) + BST.PADDING - (len(rightline) - len(rightline.lstrip()))
for leftline, rightline in zip(left, right)
)
indent(right, -indent(left, offsetright))
return [
leftline + rightline[len(leftline):]
for leftline, rightline in zip(left, right)
] + left[len(right):] + right[len(left):]
def buildlines(node):
if not node:
return []
lines = merge(buildlines(node.left), buildlines(node.right))
label = str(node.value)
half = len(label) >> 1
if not lines:
return [" "*half + "*", label]
i = lines[0].index("*")
if not node.right:
lines[0] = " "*i + ""
i += 2
elif not node.left:
i = indent(lines, i - 2)
lines[0] = " "*i + ""
else:
dist = len(lines[0]) - 1 - i
lines[0] = f"{' '*i}{''*((dist >> 1) - 1)}{''*((dist - 1) >> 1)}"
i += dist >> 1
j = indent(lines, i - half)
return [" "*(i + max(0, half - i)) + "*", " "*j + label] + lines
return "\n".join(buildlines(self.root)[1:])
tree = BST()
while True:
val = int(input("insert value: "))
tree.insert(val)
print(tree)