|
arbres binaires sont des structures de données complexes utilisés dans des programmes informatiques pour stocker les données dans la mémoire en utilisant un algorithme de stockage commun . En utilisant ce type d'algorithme , les données peuvent être stockées dans un modèle stable , ce qui rend la récupération et la recherche grâce à des données plus facile. Les programmeurs Java qui conçoivent des arbres binaires sont plus que probablement aussi concevoir des algorithmes pour traverser ces structures de données. Il ya trois façons de traverser arbres binaires : dans l'ordre, en pré-commande , et post-order . Choses que vous devez
Java Development Kit (JDK)
Text Editor
Afficher plus Instructions
1 parcourir l'arborescence binaire à l'aide en ordre de parcours . En supposant que la classe "BT" représente un arbre binaire , le code suivant montre comment imprimer l'arbre en ordre. Chaque noeud dispose d'un pointeur vers la gauche et la droite qui pointe vers des noeuds gauche et droit du noeud courant , et aussi d'un élément de données qui représente la valeur. L' en -ordre va traverser le nœud gauche en premier jusqu'à ce qu'il atteigne nulle, et l'impression nœud du parent avant de traverser à droite et recommencer . L' signifie que n'importe quel nœud imprime uniquement si tous ses nœuds enfants du côté gauche ont imprimé première :
public class BT {
afinde public void (Node x ) {
if ( x == null ) {return; //s'arrête récursivité lorsqu'il n'y a pas Node }
afinde ( x.left ) ; //toujours traverser à gauche firstprint x.data ; //imprimer les données une fois le returnsinOrder de noeud gauche ( x.right ) ; //Traverse droite }
2 parcourir l'arborescence en pré-commande . Cette commande est similaire à l' ordre , sauf que l'impression du nœud vient avant toute traversée . Ainsi, le nœud va imprimer sa valeur , puis traverser à gauche . Puis, lorsque la récursivité revient au noeud après avoir traversé gauche , le nœud sera ensuite traverser à droite . Cela signifie que le nœud sera toujours lui-même imprimer avant de tout enfant nœuds impression:
précommande public void (Node x ) {
if ( x == null) {return; //s'arrête lorsque la récursivité il n'y a pas Node }
impression x.data ; //printinOrder ( x.left ) ; //traverse leftinOrder ( x.right ) ; //Traverse droite }
3 parcourir l'arborescence post-order . C'est le contraire de la traversée de pré-commande. Un nœud sera toujours se tourner vers ses nœuds à gauche ou à droite avant l'impression proprement dite , ce qui signifie que tous les autres nœuds enfants en dessous sont imprimés en premier :
postorder public void (Node x ) {
if ( x == null) {return; //s'arrête récursivité lorsqu'il n'y a pas Node }
afinde ( x.left ) ; //traverse leftinOrder ( x.right ) ; //traverse rightprint x.data ; //print}
|
