Печать BFS (двоичное дерево) в порядке уровня с _специфическим форматированием_

Начнем с того, что этот вопрос не является дубликом этого, но основывается на нем.

Взяв дерево в этом вопросе в качестве примера,

Как бы вы изменили свою программу для ее печати,

1
2 3
4 5 6

а не общий

В основном я ищу интуицию на самом эффективном способе сделать это - у меня есть метод, включающий добавление результата в список, а затем его прокрутку. Более эффективным способом может быть сохранение последнего элемента на каждом уровне по мере его всплывания и последующая распечатка новой строки.

Идеи?

Ответ 1

Просто создайте один уровень за раз, например:

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) вместо простого цикла. Идея создания одного уровня за раз (по мере того, как вы потребляете - или итерации на предыдущем) остается неповрежденной - когда вам нужно различать уровни, это просто более прямое, чем использование одного большого значения плюс дополнительная информация ( таких как глубина или количество узлов, оставшихся на заданном уровне).

Однако список, который добавляется только (и зацикливается, а не "потребляется" ), довольно эффективен, чем deque (и если вы после С++-решений, совершенно аналогично, std::vector, используя просто push_back для его создания, а цикл для его использования более эффективен, чем std:: deque). Поскольку все производственные операции происходят сначала, то вся итерация (или потребление), интересная альтернативная , если память жестко ограничена, может заключаться в том, чтобы использовать список в любом случае для представления каждого уровня, затем .reverse он перед вами начать с его потребления (с вызовами .pop). У меня нет больших деревьев для проверки по измерениям, но я подозреваю, что этот подход все равно будет быстрее (и на самом деле менее трудоемким), чем deque (если предположить, что базовая реализация списка [[или std::vector]] фактически перерабатывает память после нескольких вызовов на pop [[или pop_back]] - и с тем же предположением для deque, конечно; -).

Ответ 2

Похоже на обход в ширину для меня.

Обход первого пути реализуется с помощью queue. Здесь просто добавьте в очередь специальный токен, указывающий, что должна быть напечатана новая строка. Каждый раз, когда маркер найден, печатайте новую строку и повторно вставляйте токен в очередь (в конце - это определение очереди).

Запустите алгоритм с очередью, содержащей корень, за которой следует специальный токен новой строки.

Ответ 3

Это первый поиск по ширине, поэтому вы можете использовать очередь и рекурсивно сделать это простым и компактным способом...

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

Ответ 4

почему бы не оставить посланника в очереди и проверить, когда обрабатываются все узлы текущего уровня.

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

Ответ 5

Мое решение похоже на Alex Martelli's, но я отделяю обход структуры данных от обработки структуры данных. Я поместил мясо кода в 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()

который печатает следующие данные при запуске:

Ответ 6

Простая версия, основанная на первом поиске хлеба. Этот код применим для графиков в целом и может также использоваться для двоичных деревьев.

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

Ответ 7

Здесь мой код печатает уровень дерева по уровню, а также вверх дном.

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 для печати дерева вверх дном. (обратите внимание, что при печати дерева вверх дном используется бит обмена, что помогает достичь нашей цели). Если обмен не выполняется, то для дерева, подобного

o/p будет

но o/p должно быть

это причина, почему в этом массиве была нужна своп-часть.

Ответ 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()

Ответ 9

Следующий код будет печатать каждый уровень двоичного дерева в новой строке:

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

Ответ 10

Для тех, кто просто интересуется визуализацией бинарных деревьев (и не столько в теории, лежащей в основе поиска по ширине), в 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

Ответ 11

Версия, которая не требует дополнительного хранения:

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 children*/) {
        ++nodesInNextLayer;
        nodes.push_back(child);
    }
    std::cout << node.value;
    if (0 == --nodesInThisLayer) {
        std::cout << std::endl;
        nodesInThisLayer = nodesInNextLayer; 
        nodesInNextLayer = 0;
    } else {
        std::cout << " ";
    }
}

P.S. извините за код С++, я пока еще не очень уверен в Python.