Печать BFS (двоичное дерево) в порядке уровня с _специфическим форматированием_
Начнем с того, что этот вопрос не является дубликом этого, но основывается на нем.
Взяв дерево в этом вопросе в качестве примера,
1
/ \
2 3
/ / \
4 5 6
Как бы вы изменили свою программу для ее печати,
1
2 3
4 5 6
а не общий
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()
который печатает следующие данные при запуске:
1
2 3
4 5 6
7
Ответ 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 для печати дерева вверх дном. (обратите внимание, что при печати дерева вверх дном используется бит обмена, что помогает достичь нашей цели). Если обмен не выполняется, то для дерева, подобного
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
это причина, почему в этом массиве была нужна своп-часть.
Ответ 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.
