[JAVA] Mémorandum d'arbre bifurqué pour les débutants (Partie 2 Recherche d'arbres bifurqués)

Cliquez ici pour Partie 1

Exploration d'arbres bifurqués

Lorsque vous utilisez une structure de données, vous devez être en mesure de rechercher des données. Il existe deux politiques de recherche principales pour l'arbre bifurqué. Première recherche de largeur et première recherche de profondeur.

Recherche de priorité de largeur

La recherche avec priorité à la largeur fait référence à une recherche qui regarde dans l'ordre de la plus proche de la racine.

Recherche de priorité de profondeur

La recherche avec priorité à la profondeur fait référence à une recherche qui trace un arbre le long d'un côté. Il existe trois types de recherche de priorité de profondeur: l'ordre de passage (précommande), l'ordre de passage (dans l'ordre) et l'ordre de retour (post-ordre). Dans l'ordre d'arrivée, regardez d'abord le parent, puis l'enfant de gauche et enfin l'enfant de droite. Dans l'ordre de passage, regardez d'abord l'enfant de gauche, puis le parent et enfin l'enfant de droite. Dans l'ordre de retour, regardez d'abord l'enfant gauche, puis l'enfant droit et enfin le parent. La recherche est réalisée en appliquant ces algorithmes de manière récursive à partir de la racine.

Maintenant, créons un programme qui génère des données de nœud en fonction de celles-ci. Pour plus de simplicité, considérez des dichotomies qui n'ont pas d'éléments vides lors de l'utilisation d'un tableau de longueur 7.

Exemple d'implémentation

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

void breadthFirstSearch(string binaryTree[], int nodeNum);
void preorder(string binaryTree[], int nodeNum, int nodeIndex);
void inorder(string binaryTree[], int nodeNum, int nodeIndex);
void postorder(string binaryTree[], int nodeNum, int nodeIndex);

void breadthFirstSearch(string binaryTree[], int nodeNum)
{
  for (int i = 0; i < nodeNum; i++) {
    cout << binaryTree[i] + " ";
  }
  cout << endl;
}

void preorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  cout << binaryTree[nodeIndex] + " ";
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void inorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  cout << binaryTree[nodeIndex] + " ";
  inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void postorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
  cout << binaryTree[nodeIndex] + " ";
}


int main()
{
  string binaryTree[7] = {"Président", "Responsable conception", "Responsable ingénieur", "Créateur de personnages",
                          "Concepteur d'interface utilisateur", "Ingénieur serveur", "Ingénieur infrastructure"};

  breadthFirstSearch(binaryTree, 7);

  preorder(binaryTree, 7, 0);
  cout << endl;
  inorder(binaryTree, 7, 0);
  cout << endl;
  postorder(binaryTree, 7, 0);
  cout << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void breadthFirstSearch(String[] binaryTree, int nodeNum) {
		for (int i = 0; i < nodeNum; i++) {
			System.out.print(binaryTree[i] + " ");
		}
		System.out.println("");
	}

	public static void preorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		System.out.print(binaryTree[nodeIndex] + " ");
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void inorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		System.out.print(binaryTree[nodeIndex] + " ");
		inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void postorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
		System.out.print(binaryTree[nodeIndex] + " ");
	}

	public static void main(String[] args) {
		String[] binaryTree = {"Président", "Responsable conception", "Responsable ingénieur", "Créateur de personnages",
													 "Concepteur d'interface utilisateur", "Ingénieur serveur", "Ingénieur infrastructure"};

		breadthFirstSearch(binaryTree, 7);

		preorder(binaryTree, 7, 0);
		System.out.println();
		inorder(binaryTree, 7, 0);
		System.out.println();
		postorder(binaryTree, 7, 0);
		System.out.println();

	}
}

Explication sur la mise en œuvre

La recherche de priorité de largeur lorsqu'une dichotomie est réalisée à l'aide d'un tableau est facile car elle ne lit le tableau que dans l'ordre depuis le début. Dans le cas de l'ordre de destination, il est réalisé en donnant l'index du nœud en cours de visualisation à l'argument nommé nodeIndex et récurrent. Puisque l'ordre de passage et de retour est différent, il peut être obtenu en remplaçant simplement les lignes dans l'ordre de passage. L'idée de récidive est difficile, mais si vous êtes débutant, réfléchissez lentement à ce que ce programme signifie. Les résultats de l'exécution sont les suivants.

Président Directeur du département Design Ingénieur Responsable du département Concepteur de personnages UI Designer Ingénieur serveur Ingénieur infrastructure
Président Département Design Concepteur de personnages Concepteur UI Ingénieur Département Ingénieur serveur Ingénieur infrastructure
Concepteur de personnages Responsable du département Design UI Designer Président Ingénieur serveur Ingénieur Responsable département Ingénieur infrastructure
Character Designer UI Designer General Manager of Design Department Ingénieur serveur Ingénieur infrastructure Directeur général du département Ingénieur Président

Avez-vous compris la recherche d'arbres bifurqués?

Partie 3 est ici