Si donné la structure arborescente suivante ou une similaire à celle-ci:
Je voudrais que la chaîne zyxwvut est revenue. Je sais comment faire cela avec un arbre binaire mais pas un qui peut avoir plus que des nœuds d'enfants. Toute aide serait très appréciée.
3 Réponses :
quelque chose comme ça devrait le faire
Ceci s'appelle un Traversal post-commander d'un arbre : vous imprimez Le contenu de tous les sous-arbres d'un arbre avant d'imprimer le contenu du nœud lui-même.
Ceci peut être fait de manière récursive, comme celui-ci (pseudocode):
Édité pour inclure une image, j'espère que ça ne vous dérange pas. Quant à la préoccupation de l'OP "Je sais comment faire cela avec un arbre binaire mais pas un qui peut avoir plus que des nœuds d'enfants": je pense que les traversées d'arbres fonctionneront sur un arbre avec un nombre quelconque de nœuds d'enfants.
Si vous maintenez une arrachelist (dites node_list) pour suivre le numéro de la ramification des nœuds du nœud d'arborescence actuelle, vous pouvez traverser l'arborescence de la racine jusqu'à la recherche d'un nœud comportant une node vide. De cette façon, vous pourrez identifier les nœuds de feuilles de l'arbre. Une approche récursive fonctionnerait pour cette affaire. Je n'ai pas testé le code mais je crois que cela devrait fonctionner pour ce que vous avez demandé:
Si vous conservez quelque chose de similaire à la classe ci-dessous pour construire votre arbre: P>
public void traverse_tree(Node n){
if(n.node_list.isEmpty()){
System.out.print(n.data);
}
else{
for(Node current_node:n.node_list){
traverse_tree(current_node);
}
System.out.println(n.data);
}
}
Vous rechercheriez essentiellement un «inverse» d'un premier algorithme de largeur. EDIT: Il suffit de lire l'arbre, si vous recherchez
zyxwvut , c'est simplement une première inscription de profondeur ...On dirait que le post-poste traverse moi
Pour clarifier: Voulez-vous imprimer les nœuds de leur profondeur dans l'arbre? Parce que seule par votre exemple, il est compliqué de dire quelle est votre question.