gpt4 book ai didi

python - 在python中逐级打印二叉树

转载 作者:太空狗 更新时间:2023-10-30 00:20:39 24 4
gpt4 key购买 nike

我想按以下方式打印我的二叉树:

                   10

6 12

5 7 11 13

我已经编写了用于插入节点的代码,但无法编写用于打印树的代码。所以请帮忙解决这个问题。我的代码是:

class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
self.parent=None

class binarytree:
def __init__(self):
self.root=None
self.size=0

def insert(self,data):
if self.root==None:
self.root=Node(data)

else:
current=self.root
while 1:
if data < current.data:
if current.left:
current=current.left
else:
new=Node(data)
current.left=new
break;
elif data > current.data:
if current.right:
current=current.right
else:
new=Node(data)
current.right=new
break;
else:
break



b=binarytree()

最佳答案

这是我的尝试,使用递归并跟踪每个节点的大小和子节点的大小。

class BstNode:

def __init__(self, key):
self.key = key
self.right = None
self.left = None

def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BstNode(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BstNode(key)
else:
self.left.insert(key)

def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)

def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = '%s' % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle

# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.key
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 self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.key
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 = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.key
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


import random

b = BstNode(50)
for _ in range(50):
b.insert(random.randint(0, 100))
b.display()

示例输出:

                              __50_________________________________________ 
/ \
________________________43_ ________________________99
/ \ /
_9_ 48 ____________67_____________________
/ \ / \
3 11_________ 54___ ______96_
/ \ \ \ / \
0 8 ____26___________ 61___ ________88___ 97
/ \ / \ / \
14_ __42 56 64_ 75_____ 92_
/ \ / / \ / \ / \
13 16_ 33_ 63 65_ 72 81_ 90 94
\ / \ \ / \
25 __31 41 66 80 87
/ /
28_ 76
\
29

关于python - 在python中逐级打印二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34012886/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com