Stampa BFS (Albero Binario) nel Livello Ordine con formatting_ _specific
https://stackoverflow.com/questions/1894846
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Per cominciare, la questione non è un duplicato di questo , ma si basa su di esso.
Prendendo l'albero in questa domanda come un esempio,
1
/ \
2 3
/ / \
4 5 6
Come si modificare il programma per stampare così,
1
2 3
4 5 6
, piuttosto che il generale
1
2
3
4
5
6
Sono fondamentalmente alla ricerca di intuizioni sul modo più efficace per farlo - Ho un metodo che comporti aggiungendo il risultato a un elenco e quindi loop attraverso di essa. Un modo più efficiente potrebbe essere quella di memorizzare l'ultimo elemento in ogni livello come è spuntato, e stampare una nuova linea dopo.
idee?
Soluzione
Basta costruire un livello alla volta, per esempio:.
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)
Modifica : se siete interessati a ottenere un piccolo risparmio di massimo consumo di memoria "ausiliaria" (non avendo mai contemporaneamente tutto questo livello e il livello successivo in tale memoria "ausiliaria"), si può ovviamente usare collection.deque invece di list, e consumare il livello attuale, come si va (via popleft) invece di looping. L'idea di creare un livello alla volta (come si consumano iterate --o on-- quello precedente) rimane intatto - quando si ha bisogno di distinguere i livelli, è solo più diretto rispetto all'utilizzo di un unico grande deque più informazioni ausiliarie ( quali profondità, o il numero di nodi rimanenti in un dato livello).
Tuttavia, un elenco che viene aggiunto solo per (e loop su, piuttosto che "consumato") è un po 'più efficiente di un deque (e se siete dopo soluzioni C ++, in modo simile, uno std :: vector utilizzando solo push_back per la costruzione di esso, e un ciclo per poi usarlo, è più efficiente di uno std :: deque). Poiché tutta la producendo avviene prima, poi tutte le iterazioni (o tempo), un'alternativa interessante se memoria è strettamente vincolata potrebbe essere quella di utilizzare un elenco comunque per rappresentare ogni livello, allora .reverse prima di iniziare a consumare esso (con chiamate .pop) - non ho grandi alberi intorno per controllare attraverso la misurazione, ma ho il sospetto che questo approccio sarebbe ancora più veloce (e in realtà meno memoria che consumano) rispetto deque (partendo dal presupposto che l'implementazione sottostante della lista [ [o std :: vector]] in realtà non riciclare memoria dopo un paio di telefonate al pop [[o pop_back]] - e con lo stesso presupposto per deque, naturalmente; -).
Altri suggerimenti
attraversamento in ampiezza per me.
Larghezza-primo attraversamento è realizzato con una coda rel="noreferrer"> . Qui, è sufficiente inserire nella coda un gettone speciale che indicano che una nuova riga deve essere stampata. Ogni volta che viene trovato il token, stampare una nuova riga e re-inserire il gettone nella coda. (Alla fine - questa è la definizione di una coda)
Inizia l'algoritmo con una coda che contiene la radice seguita dalla speciale del token di nuova riga.
Questa è ricerca in ampiezza, in modo da poter utilizzare una coda e ricorsivamente fare questo in modo semplice e compatto ...
# 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)
perché non tenere sentinella in coda e controllare quando tutti i nodi di livello attuale vengono elaborati.
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);
}
}
La mia soluzione è simile a Alex Martelli di, ma mi separano attraversamento della struttura dati dalla lavorazione della struttura dati. Ho messo la carne del codice in iterLayers per mantenere printByLayer breve e dolce.
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()
che stampa il seguente quando eseguire:
1
2 3
4 5 6
7
Un semplice versione a base di pane prima ricerca, Questo codice è applicabile per i grafici in generale e può essere utilizzato per gli alberi binari pure.
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
>>>
Un'altra versione base di ricorsione, che è specifico per albero binario
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
Ecco il mio codice stampa il livello di albero per livello così come a testa in giù
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);
}
Qui nel mio codice funzione BFS stampa il livello di albero per livello, che riempie anche i dati in un array int per la stampa l'albero a testa in giù. (Notare che c'è è usato un po 'di scambio durante la stampa l'albero a testa in giù che aiuta a raggiungere il nostro obiettivo). Se lo scambio non viene eseguita poi per un albero come
8
/ \
1 12
\ /
5 9
/ \
4 7
/
6
O / P sarà
6
7 4
9 5
12 1
8
ma l'O / P deve essere
6
4 7
5 9
1 12
8
questo il motivo per cui è stato necessario parte scambiando in tale matrice.
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()
Questo è principalmente lo stesso codice fornito da Alex Martelli tranne questo viene modificato per 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)
Il codice seguente stamperà ogni livello di albero binario nella nuova linea:
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++;
}
}
}
Credo che ciò che si aspetta è quello di stampare i nodi ad ogni livello sia separato da uno spazio o una virgola e livelli separati da una nuova linea. Questo è come vorrei codificare fino dell'algoritmo. Sappiamo che quando facciamo una ricerca in ampiezza su un grafico o un albero e inserire i nodi in una coda, tutti i nodi nella coda in uscita saranno sia allo stesso livello di quello precedente o un nuovo livello che è livello padre + 1 e niente altro.
Quindi, quando si è ad un livello di continuare a stampare i valori dei nodi e, non appena si scopre che il livello del nodo aumenta di 1, quindi si inserisce una nuova riga prima di iniziare a stampare tutti i nodi a quel livello.
Questo è il mio codice è necessario che non usa molta memoria e solo la coda per tutto.
Supponendo che inizia albero dalla radice.
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
Alla fine tutto ciò che serve è la coda per tutta l'elaborazione.
Per coloro che sono semplicemente interessati a visualizzare alberi binari (e non tanto nella teoria che sta dietro di ricerca in ampiezza), c'è una funzione show nel pacchetto BinaryTree. Applicato all'esempio indicato nella domanda,
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)
che stampa
1
/ \
2 3
/ / \
4 5 6
Ecco un succo Python che stampa l'albero per livello. L'idea è di utilizzare BFS e mantenere un intero indicatore di livello che indica la fine dell'ultimo nodo del livello. Questo è simile al metodo sentinella di Naresh, ma senza la necessità di inserire una sentinella all'interno della coda, dal momento che questo si ottiene l'indicatore di livello.
Questo algoritmo ha una complessità spaziale di 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)
che consente di stampare qualcosa del tipo:
19
7 43
3 11 23 47
2 5 17 37 53
Se si desidera utilizzare un separatore \t, sarebbe simile:
19
7 43
3 11 23 47
2 5 17 37 53
Questa sostanza è disponibile all'indirizzo https://gist.github.com/lopespm/993f0af88cf30b7f8c9e17982518b71b
Una versione che non richiede capacità di archiviazione:
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 << " ";
}
}
P.S. dispiace per il codice C ++, io non sono molto fluente in Python ancora.
