python - preorden - recorrido de arboles binarios ejercicios resueltos
Impresión de BFS(árbol binario) en orden de nivel con_formateado específico_ (12)
Para empezar, esta pregunta no es una falsificación de esta , sino que se basa en ella.
Tomando el árbol en esa pregunta como ejemplo,
1
/ /
2 3
/ / /
4 5 6
¿Cómo modificarías tu programa para imprimirlo así?
1
2 3
4 5 6
en lugar del general
1
2
3
4
5
6
Básicamente, estoy buscando intuiciones sobre la forma más eficiente de hacerlo: tengo un método que consiste en adjuntar el resultado a una lista y luego recorrerlo en bucle. Una forma más eficiente podría ser almacenar el último elemento en cada nivel a medida que se abre, e imprimir una nueva línea después.
Ideas?
¿por qué no mantener la cola en espera y verificar cuándo se procesan todos los nodos del nivel actual?
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);
}
}
Aquí mi código imprime el nivel del árbol por nivel, así como al revés
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);
}
Aquí en mi código, la función BFS imprime el nivel del árbol por nivel, que también llena los datos en una matriz int para imprimir el árbol al revés. (Tenga en cuenta que se utiliza un poco de intercambio al imprimir el árbol al revés, lo que ayuda a lograr nuestro objetivo). Si el intercambio no se realiza entonces para un árbol como
8
/ /
1 12
/ /
5 9
/ /
4 7
/
6
o / p será
6
7 4
9 5
12 1
8
pero el o / p tiene que ser
6
4 7
5 9
1 12
8
esta es la razón por la que se necesitaba el intercambio de parte en esa matriz.
Creo que lo que espera es imprimir los nodos en cada nivel separados por un espacio o una coma y los niveles se separan por una nueva línea. Así es como codificaría el algoritmo. Sabemos que cuando hacemos una búsqueda de amplitud en un gráfico o árbol e insertamos los nodos en una cola, todos los nodos en la cola que salgan estarán al mismo nivel que el anterior o un nuevo nivel que sea el nivel primario + 1 y nada más.
Entonces, cuando esté en un nivel, siga imprimiendo los valores de los nodos y tan pronto como encuentre que el nivel del nodo aumenta en 1, inserte una nueva línea antes de comenzar a imprimir todos los nodos a ese nivel.
Este es mi código que no usa mucha memoria y solo se necesita la cola para todo.
Asumiendo que el árbol comienza desde la raíz.
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
Al final, todo lo que necesita es la cola para todo el procesamiento.
El siguiente código imprimirá cada nivel de árbol binario en una nueva línea:
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)
Esta es la primera búsqueda de amplitud, por lo que puede usar una cola y hacer esto recursivamente de una manera simple y compacta ...
# 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)
Mi solución es similar a la de Alex Martelli, pero separo el recorrido de la estructura de datos del procesamiento de la estructura de datos. Puse la carne del código en iterLayers para mantener printByLayer corto y dulce.
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()
que imprime lo siguiente cuando se ejecuta:
1
2 3
4 5 6
7
Para aquellos que simplemente están interesados en visualizar árboles binarios (y no tanto en la teoría detrás de la búsqueda de amplitud), hay una función de show en el paquete binarytree . Aplicado al ejemplo dado en la pregunta,
1__
/ /
2 3
/ / /
4 5 6
que imprime
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++;
}
}
}
Solo construye un nivel a la vez, por ejemplo:
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)
Edición : si está interesado en obtener un pequeño ahorro en la memoria "auxiliar" máxima consumida (nunca teniendo simultáneamente todo este nivel y el siguiente nivel en dicha memoria "auxiliar"), por supuesto puede usar collection.deque lugar de list , y consuma el nivel actual a medida que popleft (a través de popleft ) en lugar de simplemente hacer un bucle. La idea de crear un nivel a la vez (a medida que consume --o iterar en-- el anterior) permanece intacta - cuando necesita distinguir niveles, es más directo que usar una única información adicional de deque más grande ( como la profundidad, o el número de nodos que quedan en un nivel dado).
Sin embargo, una lista que solo se agrega a (y está en bucle, en lugar de "consumida") es bastante más eficiente que un deque (y si push_back soluciones en C ++, de manera similar, un std :: vector con solo push_back para construirlo, y un bucle para luego usarlo, es más eficiente que un std :: deque). Dado que todo lo que se produce ocurre primero, luego toda la iteración (o consumo), una alternativa interesante si la memoria está estrechamente restringida podría ser utilizar una lista de todos modos para representar cada nivel, luego .reverse antes de comenzar a consumirla (con llamadas .pop ) - No tengo grandes árboles alrededor para verificar por medición, pero sospecho que este enfoque aún sería más rápido (y en realidad consumiría menos memoria) que deque (suponiendo que la implementación subyacente de la lista [[o std :: vector]] en realidad recicla la memoria después de algunas llamadas a pop [[o pop_back ]] - y con la misma suposición de deque, por supuesto ;-).
Suena como el primer paso para mí.
El primer recorrido se implementa con una queue . Aquí, simplemente inserte en la cola un token especial que indique que se debe imprimir una nueva línea. Cada vez que se encuentra el token, imprima una nueva línea y vuelva a insertarlo en la cola (al final, esa es la definición de una cola).
Inicie el algoritmo con una cola que contenga la raíz seguida del token especial de nueva línea.
Una versión que no requiere almacenamiento extra:
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 << " ";
}
}
PD, perdón por el código C ++, no soy muy fluido en Python todavía.
Una versión simple basada en Bread First Search, este código es aplicable para gráficos en general y también puede usarse para árboles binarios.
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
>>>
Otra versión basada en Recursión, que es específica de árbol 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
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()