Impression BFS (arbre binaire) en ordre de niveau avec formatage spécifique
pour commencer, cette question n'est pas un dup de celui-ci , mais construit sur elle.
la Prise de l'arbre en question comme un exemple,
1
/
2 3
/ /
4 5 6
comment modifier votre programme pour l'imprimer ainsi,
1
2 3
4 5 6
plutôt que le général
1
2
3
4
5
6
je suis fondamentalement la recherche d'intuitions sur la façon la plus efficace de le faire - j'ai une méthode impliquant en ajoutant le résultat à une liste, et en la passant en boucle. Un moyen plus efficace pourrait être de stocker le dernier élément dans chaque niveau comme il est popped, et imprimer une nouvelle ligne après.
idées?
12 réponses
il suffit de construire un niveau à la fois, par exemple:
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)
Edit : si vous êtes désireux d'obtenir une petite économie dans la mémoire "auxiliaire" maximum consommé (ne jamais avoir simultanément tout ce niveau et le niveau suivant dans une telle mémoire "auxiliaire"), vous pouvez bien sûr utiliser collection.deque au lieu de list , et consommer le niveau actuel que vous allez (via popleft ) au lieu de simplement boucler. L'idée de créer un niveau à la fois (comme vous consumer --or iterate on-- the previous one) reste intact -- quand vous avez besoin de distinguer les niveaux, c'est juste plus direct que d'utiliser un seul grand deque plus des informations auxiliaires (comme la profondeur, ou le nombre de noeuds restant dans un niveau donné).
cependant, une liste qui n'est annexée qu'à (et bouclée, plutôt que "consommée") est un peu plus efficace qu'une deque (et si vous êtes après c++ solutions, de la même manière, un vecteur std::en utilisant juste push_back pour pour le construire, et une boucle pour ensuite l'utiliser, est plus efficace qu'un std::deque). Puisque toute la production se produit d'abord, puis toutes les itérations (ou la consommation), une alternative intéressante si mémoire est étroitement contraint pourrait être d'utiliser une liste de toute façon pour représenter chaque niveau, puis .reverse il avant de commencer à le consommer (avec .pop appels) -- Je n'ai pas de grands arbres autour de vérifier par mesure, mais je soupçonne que cette approche serait encore plus rapide (et en fait moins gourmande en mémoire) que deque (en supposant que l'implémentation sous-jacente de list [[ou std::vector]] ne recycle en fait la mémoire après quelques appels à pop [[ou pop_back ]] -- et avec la même hypothèse pour deque, bien sûr;-).
sonne comme largeur-première traversée pour moi.
Largeur-première traversée est mise en œuvre avec une file . Ici, insérez simplement dans la file d'attente un jeton spécial qui indique qu'une nouvelle ligne doit être imprimée. Chaque fois que le jeton est trouvé, imprimez une nouvelle ligne et réinsérez le jeton dans la file d'attente (à la fin -- c'est la définition d'une file d'attente).
Démarrer l'algorithme avec une file contenant la racine suivi du jeton newline spécial.
c'est la première recherche de largeur, de sorte que vous pouvez utiliser une file d'attente et de façon récursive faire cela d'une manière simple et compacte ...
# 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)
pourquoi ne pas garder sentinal dans la file d'attente et vérifier quand tous les noeuds dans le niveau courant sont traités.
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);
}
}
ma solution est similaire à celle D'Alex Martelli, mais je sépare traversée de la structure de données du traitement de la structure de données. J'ai mis la viande du code dans iterLayers pour garder printByLayer court et doux.
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()
qui imprime ce qui suit lors de l'exécution:
1
2 3
4 5 6
7
une Version simple basée sur la recherche Bread First, ce code est applicable aux graphiques en général et peut être utilisé pour les arbres binaires aussi bien.
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
>>>
une autre version basée sur la récursion, qui est spécifique à l'arbre binaire
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
ici mon code imprime le niveau de l'arbre par niveau aussi bien qu'à l'envers
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);
}
ici dans mon code la fonction BFS imprime le niveau de l'arbre par niveau, qui remplit également les données dans un tableau int pour imprimer l'arbre à l'envers. (notez qu'un peu d'échange est utilisé lors de l'impression de l'arbre à l'envers qui aide à atteindre notre objectif). Si l'échange n'est pas effectuée alors pour un arbre comme
8
/ \
1 12
\ /
5 9
/ \
4 7
/
6
o/p sera
6
7 4
9 5
12 1
8
mais l'o/p doit être
6
4 7
5 9
1 12
8
c'est la raison pour laquelle le changement de pièce était nécessaire dans ce tableau.
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()
le code suivant imprimera chaque niveau de l'arbre binaire dans une nouvelle ligne:
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++;
}
}
}
pour ceux qui sont simplement intéressés à visualiser les arbres binaires (et pas tellement dans la théorie derrière la largeur-première recherche), il y a une fonction show dans le paquet binarytree . Appliquée à l'exemple donné dans la question,
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)
qui imprime
1__
/ \
2 3
/ / \
4 5 6
je pense que ce que vous attendez est d'imprimer les noeuds à chaque niveau soit séparé par un espace ou une virgule et les niveaux soient séparés par une nouvelle ligne. C'est comme ça que je coderais l'algorithme. Nous savons que lorsque nous effectuons une première recherche étendue sur un graphe ou un arbre et insérons les noeuds dans une file d'attente, tous les noeuds de la file d'attente sortant seront soit au même niveau que le précédent ou un nouveau niveau qui est le niveau parent + 1 et rien d'autre.
ainsi quand vous êtes à un niveau de conserver l'impression des valeurs de nœud et dès que vous trouvez que le niveau du nœud augmente de 1, puis vous insérez une nouvelle ligne avant de commencer à imprimer tous les nœuds à ce niveau.
C'est mon code qui n'utilise pas beaucoup de mémoire et seulement la file d'attente est nécessaire pour tout.
si l'arbre part de la racine.
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
à la fin tout ce dont vous avez besoin est la file d'attente pour tout le traitement.
une version qui ne nécessite pas de stockage supplémentaire:
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. désolé pour le code C++, Je ne parle pas encore très couramment en Python.