以特定格式按级别顺序打印 BFS（二叉树）

Question

首先，这个问题不是 这个，但建立在它的基础上。

以该问题中的树为例，

    1 
   / \
  2   3
 /   / \
4   5   6

您将如何修改程序来打印它，

1
2 3
4 5 6

而不是一般情况，

1 
2 
3 
4 
5 
6

我基本上是在寻找最有效方法的直觉 - 我有一个涉及附加的方法结果到一个列表，然后循环遍历它。更有效的方法可能是在弹出时存储每个级别中的最后一个元素，然后打印出新行。

有想法吗？

Answer 1

这里我的代码逐层打印树以及颠倒

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

该数组中需要交换部分的原因。

Answer 2

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()

Answer 3

对于那些仅仅对可视化二叉树感兴趣（而不是对广度优先搜索背后的理论感兴趣）的人来说，show 函数。 python.org/pypi/binarytree" rel="nofollow noreferrer">binarytree 包。应用于问题中给出的示例，

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

Answer 4

这与 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)

Answer 5

以下代码将把二叉树的每一层打印到新行中：

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++;
        }
     }
}

Answer 6

我认为您期望的是打印每个级别的节点，由空格或逗号分隔，并且级别由新行分隔。这就是我编写算法的方式。我们知道，当我们对图或树进行广度优先搜索并将节点插入队列时，队列中出现的所有节点将要么与前一个节点处于同一级别，要么处于父级别的新级别+ 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

最后，您所需要的只是用于所有处理的队列。

Answer 7

这是按级别打印树的 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  

This gist is available在 https://gist.github.com/lopespm/993f0af88cf30b7f8c9e17982518b71b

Answer 8

利用队列（恒定空间复杂度）

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)

Answer 9

BT / BST 的级序遍历

在 BASH 中，您只需在 .txt 文件中创建/维护节点，即可轻松实现 BT / BST，而无需使用任何哈希数组/映射等。

这是我的破解方法。 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

对于root (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

Answer 10

不需要额外存储的版本：

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 还不太流利。

Answer 11

一次只构建一个级别，例如：

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用于构建它的 code>push_back 以及用于然后使用它的循环比 std::deque 更有效。由于所有的生产首先发生，然后是所有的迭代（或消耗），一个有趣的替代方案如果内存受到严格限制可能是无论如何使用一个列表来表示每个级别，然后 .reverse< /code> 在你开始使用它之前（使用 .pop 调用）——我周围没有大树可以通过测量来检查，但我怀疑这种方法仍然会更快（实际上比 deque 消耗更少的内存（假设列表 [[或 std::vector]] 的底层实现实际上在几次调用 pop [[或 pop_back]] ——当然，对于双端队列也有相同的假设；-)。

Answer 12

对我来说听起来像是广度优先遍历。

广度优先遍历是通过队列实现的。在这里，只需在队列中插入一个特殊标记，指示必须打印换行符。每次找到令牌时，打印一个换行符并将令牌重新插入队列中（在末尾——这是队列的定义）。

使用包含根的队列开始算法，后跟特殊的换行符。

Answer 13

我的解决方案与 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

Answer 14

这是广度优先搜索，因此您可以使用队列并以简单而紧凑的方式递归地执行此操作......

# 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)

Answer 15

为什么不将sentinal保留在队列中并检查当前级别中的所有节点何时被处理。

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);
    }
}

Answer 16

基于面包优先搜索的简单版本，此代码适用于一般图，也可用于二叉树。

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