首先,这个问题不是这个问题的重复,而是建立在它之上。
以那个问题中的树为例,
1
/ \
2 3
/ / \
4 5 6
你会如何修改你的程序来打印它,
1
2 3
4 5 6
而不是一般的
1
2
3
4
5
6
我基本上是在寻找最有效的方法的直觉——我有一种方法涉及将结果附加到列表中,然后循环遍历它。一种更有效的方法可能是在弹出的每个级别中存储最后一个元素,然后打印出一个新行。
想法?
首先,这个问题不是这个问题的重复,而是建立在它之上。
以那个问题中的树为例,
1
/ \
2 3
/ / \
4 5 6
你会如何修改你的程序来打印它,
1
2 3
4 5 6
而不是一般的
1
2
3
4
5
6
我基本上是在寻找最有效的方法的直觉——我有一种方法涉及将结果附加到列表中,然后循环遍历它。一种更有效的方法可能是在弹出的每个级别中存储最后一个元素,然后打印出一个新行。
想法?
一次只构建一个级别,例如:
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]
while thislevel:
nextlevel = list()
for n in thislevel:
print 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(3, Node(5), Node(6)))
traverse(t)
编辑:如果您希望在最大消耗的“辅助”内存中节省一点点(在这种“辅助”内存中永远不会同时拥有所有这个级别和下一个级别),您当然可以使用collection.deque
而不是list
,并消耗当前随你去水平(通过popleft
)而不是简单地循环。一次创建一个级别的想法(当您使用 - 或迭代 - 前一个级别时)保持不变 - 当您确实需要区分级别时,它比使用单个大双端队列加上辅助信息更直接(例如深度,或保留在给定级别中的节点数)。
但是,仅附加到(并循环,而不是“消耗”)的列表比双端队列更有效(如果您在 C++ 解决方案之后,非常相似,一个 std::vector 仅使用push_back
for构建它,然后使用它的循环比 std::deque 更有效)。由于所有生产首先发生,然后是所有迭代(或消耗),如果内存受到严格限制,一个有趣的替代方法可能是使用列表来表示每个级别,然后.reverse
在开始使用它之前(通过.pop
调用) - 我周围没有大树可以通过测量来检查,但我怀疑这种方法仍然比deque
(假设 list [[or std::vector]] 的底层实现在对 [[or ]] 的几次调用之后实际上确实回收了内存pop
——pop_back
当然,对于双端队列也有相同的假设;-)。
我的解决方案类似于 Alex Martelli 的解决方案,但我将数据结构的遍历与数据结构的处理分开。我将代码的内容放入 iterLayers 中,以保持 printByLayer 简短而甜美。
from collections import deque
class Node:
def __init__(self, val, lc=None, rc=None):
self.val = val
self.lc = lc
self.rc = rc
def iterLayers(self):
q = deque()
q.append(self)
def layerIterator(layerSize):
for i in xrange(layerSize):
n = q.popleft()
if n.lc: q.append(n.lc)
if n.rc: q.append(n.rc)
yield n.val
while (q):
yield layerIterator(len(q))
def printByLayer(self):
for layer in self.iterLayers():
print ' '.join([str(v) for v in layer])
root = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
root.printByLayer()
运行时打印以下内容:
1
2 3
4 5 6
7
这是广度优先搜索,因此您可以使用队列并以简单紧凑的方式递归地执行此操作...
# built-in data structure we can use as a queue
from collections import deque
def print_level_order(head, queue = deque()):
if head is None:
return
print head.data
[queue.append(node) for node in [head.left, head.right] if node]
if queue:
print_level_order(queue.popleft(), queue)
为什么不将哨兵保留在队列中并检查当前级别的所有节点何时被处理。
public void printLevel(Node n) {
Queue<Integer> q = new ArrayBlockingQueue<Integer>();
Node sentinal = new Node(-1);
q.put(n);
q.put(sentinal);
while(q.size() > 0) {
n = q.poll();
System.out.println(n.value + " ");
if (n == sentinal && q.size() > 0) {
q.put(sentinal); //push at the end again for next level
System.out.println();
}
if (q.left != null) q.put(n.left);
if (q.right != null) q.put(n.right);
}
}
基于面包优先搜索的简单版本,此代码通常适用于图,也可用于二叉树。
def printBfsLevels(graph,start):
queue=[start]
path=[]
currLevel=1
levelMembers=1
height=[(0,start)]
childCount=0
print queue
while queue:
visNode=queue.pop(0)
if visNode not in path:
if levelMembers==0:
levelMembers=childCount
childCount=0
currLevel=currLevel+1
queue=queue+graph.get(visNode,[])
if levelMembers > 0:
levelMembers=levelMembers-1
for node in graph.get(visNode,[]):
childCount=childCount+1
height.append((currLevel,node))
path=path+[visNode]
prevLevel=None
for v,k in sorted(height):
if prevLevel!=v:
if prevLevel!=None:
print "\n"
prevLevel=v
print k,
return height
g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13]}
printBfsLevels(g,1)
>>>
[1]
1
2 3 6
4 5 6 7
8 9 13
>>>
另一个基于递归的版本,特定于二叉树
class BinTree:
"Node in a binary tree"
def __init__(self,val,leftChild=None,rightChild=None,root=None):
self.val=val
self.leftChild=leftChild
self.rightChild=rightChild
self.root=root
if not leftChild and not rightChild:
self.isExternal=True
def getChildren(self,node):
children=[]
if node.isExternal:
return []
if node.leftChild:
children.append(node.leftChild)
if node.rightChild:
children.append(node.rightChild)
return children
@staticmethod
def createTree(tupleList):
"Creates a Binary tree Object from a given Tuple List"
Nodes={}
root=None
for item in treeRep:
if not root:
root=BinTree(item[0])
root.isExternal=False
Nodes[item[0]]=root
root.root=root
root.leftChild=BinTree(item[1],root=root)
Nodes[item[1]]=root.leftChild
root.rightChild=BinTree(item[2],root=root)
Nodes[item[2]]=root.rightChild
else:
CurrentParent=Nodes[item[0]]
CurrentParent.isExternal=False
CurrentParent.leftChild=BinTree(item[1],root=root)
Nodes[item[1]]=CurrentParent.leftChild
CurrentParent.rightChild=BinTree(item[2],root=root)
Nodes[item[2]]=CurrentParent.rightChild
root.nodeDict=Nodes
return root
def printBfsLevels(self,levels=None):
if levels==None:
levels=[self]
nextLevel=[]
for node in levels:
print node.val,
for node in levels:
nextLevel.extend(node.getChildren(node))
print '\n'
if nextLevel:
node.printBfsLevels(nextLevel)
## 1
## 2 3
## 4 5 6 7
## 8
treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
tree= BinTree.createTree(treeRep)
tree.printBfsLevels()
>>>
1
2 3
4 5 6 7
8 None
在这里,我的代码逐级以及颠倒打印树
int counter=0;// to count the toatl no. of elments in the tree
void tree::print_treeupsidedown_levelbylevel(int *array)
{
int j=2;
int next=j;
int temp=0;
while(j<2*counter)
{
if(array[j]==0)
break;
while(array[j]!=-1)
{
j++;
}
for(int i=next,k=j-1 ;i<k; i++,k--)
{
temp=array[i];
array[i]=array[k];
array[k]=temp;
}
next=j+1;
j++;
}
for(int i=2*counter-1;i>=0;i--)
{
if(array[i]>0)
printf("%d ",array[i]);
if(array[i]==-1)
printf("\n");
}
}
void tree::BFS()
{
queue<node *>p;
node *leaf=root;
int array[2*counter];
for(int i=0;i<2*counter;i++)
array[i]=0;
int count=0;
node *newline=new node; //this node helps to print a tree level by level
newline->val=0;
newline->left=NULL;
newline->right=NULL;
newline->parent=NULL;
p.push(leaf);
p.push(newline);
while(!p.empty())
{
leaf=p.front();
if(leaf==newline)
{
printf("\n");
p.pop();
if(!p.empty())
p.push(newline);
array[count++]=-1;
}
else
{
cout<<leaf->val<<" ";
array[count++]=leaf->val;
if(leaf->left!=NULL)
{
p.push(leaf->left);
}
if(leaf->right!=NULL)
{
p.push(leaf->right);
}
p.pop();
}
}
delete newline;
print_treeupsidedown_levelbylevel(array);
}
在我的代码中,函数 BFS 逐级打印树,它还将数据填充到 int 数组中,用于颠倒打印树。(请注意,在颠倒打印树时使用了一些交换,这有助于实现我们的目标)。如果没有执行交换,那么对于像这样的树
8
/ \
1 12
\ /
5 9
/ \
4 7
/
6
o/p 将是
6
7 4
9 5
12 1
8
但 o/p 必须是
6
4 7
5 9
1 12
8
这就是为什么在该数组中需要交换部分的原因。
class TNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class BST:
def __init__(self, root):
self._root = root
def bfs(self):
list = [self._root]
while len(list) > 0:
print [e.data for e in list]
list = [e.left for e in list if e.left] + \
[e.right for e in list if e.right]
bst = BST(TNode(1, TNode(2, TNode(4), TNode(5)), TNode(3, TNode(6), TNode(7))))
bst.bfs()
对于那些只对二叉树可视化感兴趣的人(而不是对广度优先搜索背后的理论感兴趣),二叉树包show
中有一个函数。应用于问题中给出的示例,
from binarytree import Node, show
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)
show(root)
哪个打印
1
/ \
2 3
/ / \
4 5 6
这与 Alex Martelli 提供的代码基本相同,只是针对 python 3 进行了修改。
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]
while thislevel:
nextlevel = list()
for n in thislevel:
print (n.value,' ', end=''),
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(3, Node(5), Node(6)))
traverse(t)
下面的代码会将二叉树的每一层打印到新行:
public void printbylevel(node root){
int counter = 0, level = 0;
Queue<node> qu = new LinkedList<node>();
qu.add(root);
level = 1;
if(root.child1 != null)counter++;
if(root.child2 != null)counter++;
while(!qu.isEmpty()){
node temp = qu.remove();
level--;
System.out.print(temp.val);
if(level == 0 ){
System.out.println();
level = counter;
counter = 0;
}
if(temp.child1 != null){
qu.add(temp.child1);
counter++;
}
if(temp.child2 != null){
qu.add(temp.child2);
counter++;
}
}
}
我认为您期望的是打印每个级别的节点,或者用空格或逗号分隔,并且级别用新行分隔。这就是我编写算法的方式。我们知道,当我们在图或树上进行广度优先搜索并将节点插入队列时,队列中的所有节点都将与前一个级别相同或新级别,即父级别+ 1,仅此而已。
因此,当您处于某个级别时,请继续打印节点值,并且一旦您发现节点的级别增加 1,则在开始打印该级别的所有节点之前插入新行。
这是我的代码,它不使用太多内存,所有事情都只需要队列。
假设树从根开始。
queue = [(root, 0)] # Store the node along with its level.
prev = 0
while queue:
node, level = queue.pop(0)
if level == prev:
print(node.val, end = "")
else:
print()
print(node.val, end = "")
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
prev = level
最后,您需要的只是所有处理的队列。
这是一个按级别打印树的 Python 要点。它背后的想法是使用 BFS 并保留一个级别标记整数,该整数标记级别的最后一个节点。这类似于 Naresh 的哨兵方法,但不需要在队列中插入哨兵,因为这是通过级别标记完成的。
该算法的空间复杂度为 O(2 tree_height )
# Print tree by levels - using BFS
# Time complexity of O(n)
# Space complexity: O(2^tree_height)
from collections import deque
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_levels_tree(root: Node):
q = deque()
q.append(root)
level, level_marker = 0, 1
while q:
if (level_marker == 0):
level, level_marker = level + 1, len(q)
print("", end = '\n')
level_marker -= 1
node = q.popleft()
if (node is None):
continue
print(node.data, " ", end = '')
q.append(node.left)
q.append(node.right)
# Some examples
tree = Node(19, Node(7, Node(3), Node(11)), Node(19))
print_levels_tree(tree)
left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
tree = Node(19, left, Node(43))
print_levels_tree(tree)
left = Node(7, Node(3, Node(2), Node(5)), Node(11, None, Node(17, Node(13))))
right = Node(43, Node(23, None, Node(37, Node(29, None, Node(31)), Node(41))), Node(47, None, Node(53)) )
tree = Node(19, left, right)
print_levels_tree(tree)
打印如下内容:
19
7 43
3 11 23 47
2 5 17 37 53
如果你想使用\t
分隔符,它看起来像:
19
7 43
3 11 23 47
2 5 17 37 53
此要点可在https://gist.github.com/lopespm/993f0af88cf30b7f8c9e17982518b71b获得
利用队列(恒定空间复杂度)
def bfs(self, queue=None):
if(queue is None):
queue = deque([self.root])
elif(not queue):
return
currNode = queue.pop()
print(currNode.data)
if currNode.left:
queue.appendleft(currNode.left)
if currNode.right:
queue.appendleft(currNode.right)
self.bfs(queue)
BT / BST 的级别顺序遍历
在 BASH 中,您可以轻松实现 BT / BST,而无需使用任何哈希数组/映射等,只需在 .txt 文件中创建/维护节点即可。
这是我的破解。2个小功能print_level()
和print_root()
,会做。脚本可以从任何给定的用户指定的根节点打印任何级别的节点信息。
#!/bin/bash
print_level(){
echo $cs
call_flag=0
for row in $cs; do if [[ `grep "^${row}:" ~/btree-data.txt` ]]; then call_flag=1; fi; done
if [[ $call_flag == 1 ]]; then rs="$cs"; print_root; fi
}
print_root(){
if [[ ${flag} == 0 ]]; then echo "${rs}"; flag=1; fi
cs=""
for r in $rs; do cs+="$(grep "^${r}:" ~/btree-data.txt | cut -d':' -f2 | sed "s/,/ /") "; done
print_level
echo
}
flag=0
echo -e "\n\n
# It reads a file ~/btree-data.txt (as shown below).
# -- One can easily implement CRUD operation to maintain BT/BST using a .txt file.
#
# -- Here .txt file ROW's Format is: NODE:left_leaf_node,right_leaf_node
#
# 100:50,200
# 50:20,60
# 200:300
# 300:350
# 60:55,75
# 20:10,25
# 10:5
# 350:320
# 25:27
# 5:2
# 320:310,325
# 2:3
## ----------------- BTree Diagram -------------------------------------------------------------------------
# 100
# 50 200
# 20 60 300
# 10 25 55 75 350
# 5 27 320
# 2 310 325
# 3
## ----------------- BTree Diagram -------------------------------------------------------------------------
\n\n"
echo -ne "\n-- Enter which root: "; read rs
print_root
echo -e "\n\n"
当你跑步时,吐口水:
$ ./btree-bash-level-print.sh
# It reads a file ~/btree-data.txt (as shown below).
# -- One can easily implement CRUD operation to maintain BT/BST using a .txt file.
#
# -- Here .txt file ROW's Format is: NODE:left_leaf_node,right_leaf_node
#
# 100:50,200
# 50:20,60
# 200:300
# 300:350
# 60:55,75
# 20:10,25
# 10:5
# 350:320
# 25:27
# 5:2
# 320:310,325
# 2:3
## ----------------- BTree Diagram -------------------------------------------------------------------------
# 100
# 50 200
# 20 60 300
# 10 25 55 75 350
# 5 27 320
# 2 310 325
# 3
## ----------------- BTree Diagram -------------------------------------------------------------------------
-- Enter which root: 100
100
50 200
20 60 300
10 25 55 75 350
5 27 320
2 310 325
3
对于根 (300),
-- Enter which root: 300
300
350
320
310 325
对于根 (50),
-- Enter which root: 50
50
20 60
10 25 55 75
5 27
2
3
不需要额外存储的版本:
std::deque<Node> bfs;
bfs.push_back(start);
int nodesInThisLayer = 1;
int nodesInNextLayer = 0;
while (!bfs.empty()) {
Node front = bfs.front();
bfs.pop_front();
for (/*iterate over front's children*/) {
++nodesInNextLayer;
nodes.push_back(child);
}
std::cout << node.value;
if (0 == --nodesInThisLayer) {
std::cout << std::endl;
nodesInThisLayer = nodesInNextLayer;
nodesInNextLayer = 0;
} else {
std::cout << " ";
}
}
PS 对不起 C++ 代码,我对 Python 还不是很流利。