Résumé des exercices Exericces du cours MOOC sur les structures de données de l'Université du Zhejiang - Partage de code sur la plateforme de programmation - 2024

Description du problème

Étant donné un arbre, vous devez lister toutes les feuilles dans l'ordre de haut en bas, et de gauche à droite.

**Spécification d'entrée :**Chaque fichier d'entrée contient un cas de test. Pour chaque cas, la première ligne donne un entier positif N (≤10) qui est le nombre total de nœuds dans l'arbre - et donc les nœuds sont numérotés de 0 à N-1. Ensuite, N lignes suivent, chacune correspond à un nœud, et donne les indices des enfants gauche et droit du nœud. Si l'enfant n'existe pas, un '-' sera placé à la position. Toute paire d'enfents est séparée par un espace.

**Spécification de sortie :**Pour chaque cas de test, imprimez sur une ligne tous les indices des feuilles dans l'ordre de haut en bas, et de gauche à droite. Il doit y avoir exactement un espace entre tous les nombres adjacents, et aucun espace supplémentaire à la fin de la ligne.

Exemple d'entrée :

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Exemple de sortie :

4 1 5

Implémentation

L'approche consiste d'abord à construire un arbre binaire, puis à effectuer un parcours en largeur de l'arbre tout en enregistrant les informatiosn des nœuds feuilles.

astuce: lors de la construction de l'arbre, si le paramètre d'entrée est une référence à un tableau, vous pouvez utiliser le mode DEBUG pour observer tous les éléments actuellement présents dans l'arbre arbre construireArbre (noeud (&T)[TAILLE_MAX])

#include <iostream>
#include <queue>
#define TAILLE_MAX 10
#define NOUD_NULL -1
typedef int Arbre;

struct noeud
{
    int valeur;
    int enfant_gauche;
    int enfant_droit;
}T[TAILLE_MAX];

Arbre construireArbre (noeud (&T)[TAILLE_MAX])
{
    int n;
    int racine = -1;
    std::cin >> n;
    bool est_racine[TAILLE_MAX] = { false };
    if (n == 1)
    {
        T[0].valeur = 0;
        T[0].enfant_gauche = NOUD_NULL;
        T[0].enfant_droit = NOUD_NULL;
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        char gauche, droite;
        std::cin >> gauche >> droite;
        T[i].valeur = i;
        if (gauche != '-')
        {
            T[i].enfant_gauche = gauche - '0';
            est_racine[T[i].enfant_gauche] = true;
        }
        else T[i].enfant_gauche = NOUD_NULL;

        if (droite != '-')
        {
            T[i].enfant_droit = droite - '0';
            est_racine[T[i].enfant_droit] = true;
        }
        else T[i].enfant_droit = NOUD_NULL;

        if (gauche == '-' && droite == '-')
        {
            est_racine[i] = true;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (!est_racine[i])
        {
            racine = i;
            return racine;
        }
    }
    return racine;
}
/*
	Utilisation d'une file : la racine est ajoutée à la file,
			boucle : un nœud est retiré de la file, le nœud est visité, et ses enfants gauche et droit sont ajoutés à la file
*/
void parcoursLargeur(Arbre racine)
{	
	bool premier_affichage = true;
	Arbre r = racine;
	Arbre courant;
	std::queue<Arbre> file;		//la file ne stocke que les numéros de nœuds
	file.push(T[r].valeur);		//ajout de la racine à la file
	while (!file.empty())
	{	
		//retrait de la file
		courant = file.front();
		file.pop();

		//visite des nœuds feuilles
		if (T[courant].enfant_gauche == NOUD_NULL && T[courant].enfant_droit == NOUD_NULL)
		{
			if (premier_affichage)
			{
				std::cout << courant;
				premier_affichage = false;
			}
			else std::cout << ' ' << courant;
		}

		//ajout des enfants gauche et droit à la file
		if (T[courant].enfant_gauche != NOUD_NULL)
		{
			file.push(T[courant].enfant_gauche);
		}
		if (T[courant].enfant_droit != NOUD_NULL)
		{
			file.push(T[courant].enfant_droit);
		}
		
	}
}
int main()
{	
	Arbre r;
	r = construireArbre(T);	//r est la racine du arbre
	parcoursLargeur(r);
	return 0;
}