在python中逐级打印二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/34012886/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
print binary tree level by level in python
提问by user2762315
I want to print my binary tree in the following manner:
我想以下列方式打印我的二叉树：
10
6 12
5 7 11 13
I have written code for insertion of nodes but can't able to write for printing the tree. so please help on this . My code is :
我已经编写了用于插入节点的代码，但无法编写用于打印树的代码。所以请帮忙解决这个问题。我的代码是：
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()
采纳答案by Juan Carlos Coto
This has a homeworky sound to it, and if it is, you should mention it. However, it's still a legitimate question.
这有一种家庭作业的声音，如果是，你应该提到它。然而，这仍然是一个合理的问题。
What you're looking for is breadth-first traversal, which lets you traverse a tree level by level. Basically, you use a queue to keep track of the nodes you need to visit, adding children to the backof the queue as you go (as opposed to adding them to the frontof a stack). Get that working first.
您正在寻找的是广度优先遍历，它可以让您逐层遍历树。基本上，您使用队列来跟踪您需要访问的节点，在您访问时将子节点添加到队列的后面（而不是将它们添加到堆栈的前面）。先让它工作。
After you do that, then you can figure out how many levels the tree has (log2(node_count) + 1) and use that to estimate whitespace. If you want to get the whitespace exactly right, you can use other data structures to keep track of how many spaces you need per level. A smart estimation using number of nodes and levels should be enough, though.
完成此操作后，您可以计算出树有多少层 ( log2(node_count) + 1) 并使用它来估计空白。如果您想获得完全正确的空格，您可以使用其他数据结构来跟踪每个级别需要多少空格。不过，使用节点数和级别数进行智能估计就足够了。
回答by Prashant Shukla
Similar question is being answered over hereThis may help following code will print in this format
在这里回答了类似的问题这可能有助于以下代码将以这种格式打印
>>>
1
2 3
4 5 6
7
>>>
Code for this is as below :
代码如下：
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def traverse(rootnode):
thislevel = [rootnode]
a = ' '
while thislevel:
nextlevel = list()
a = a[:len(a)/2]
for n in thislevel:
print a+str(n.value),
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
t = Node(1, Node(2, Node(4, Node(7)),Node(9)), Node(3, Node(5), Node(6)))
traverse(t)
Edited code gives result in this format :
编辑后的代码给出了这种格式的结果：
>>>
1
2 3
4 9 5 6
7
>>>
This is just a trick way to do what you want their maybe a proper method for that I suggest you to dig more into it.
这只是一种做你想做的事情的技巧，他们可能是一种正确的方法，我建议你深入研究它。
回答by Emad Mokhtar
I enhanced Prashant Shukla answerto print the nodes on the same level in the same line without spaces.
我增强了Prashant Shukla 的答案，以在同一行中的同一级别上打印节点，没有空格。
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def __str__(self):
return str(self.value)
def traverse(root):
current_level = [root]
while current_level:
print(' '.join(str(node) for node in current_level))
next_level = list()
for n in current_level:
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current_level = next_level
t = Node(1, Node(2, Node(4, Node(7)), Node(9)), Node(3, Node(5), Node(6)))
traverse(t)
回答by J. V.
Here's my attempt, using recursion, and keeping track of the size of each node and the size of children.
这是我的尝试，使用递归并跟踪每个节点的大小和子节点的大小。
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()
Example output:
示例输出：
__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
回答by Hardmoon
class magictree:
def __init__(self, parent=None):
self.parent = parent
self.level = 0 if parent is None else parent.level + 1
self.attr = []
self.rows = []
def add(self, value):
tr = magictree(self)
tr.attr.append(value)
self.rows.append(tr)
return tr
def printtree(self):
def printrows(rows):
for i in rows:
print("{}{}".format(i.level * "\t", i.attr))
printrows(i.rows)
printrows(self.rows)
tree = magictree()
group = tree.add("company_1")
group.add("emp_1")
group.add("emp_2")
emp_3 = group.add("emp_3")
group = tree.add("company_2")
group.add("emp_5")
group.add("emp_6")
group.add("emp_7")
emp_3.add("pencil")
emp_3.add("pan")
emp_3.add("scotch")
tree.printtree()
result:
结果：
['company_1']
['emp_1']
['emp_2']
['emp_3']
['pencil']
['pan']
['scotch']
['company_2']
['emp_5']
['emp_6']
['emp_7']
