Ancetre

###############################

	Ancetre : Aftab Kanjiani 31/05/2011

##############################


// Parcours par niveau ,
// avoir une variable niveau , qu'on incrémente à chaque boucle
// Utilisez une structure avec le noeud et le niveau
// et à chaque fois dans ma boucle je vais editez ma structure.
//
// Récupéré le niveau de l' ancètre pour que ma formule fonctionne à l'aide d'une liste.

Structure noeudAncetre

	noeud : Noeud<Obj>
	listeIdPère : Liste <noeudAncetre>
	niveau : entier


fin structure

module degréParenté(arbre : ArbreNaire<Obj>, a : entier, b : entier) --> entier

	file : File<Noeud<noeudAncetre>> <- nouvelle FileListe()<noeudAncetre>
	cptNiveau : entier <-0

	trouveA : booleen <- FAUX
	trouveB : booleen <- FAUX

	niveauA , niveauB : entier <- 0

	na , noeudA , noeudB : noeudAncetre
	na.niveau = cptNiveau
	na.noeud = arbre.getRacine()

	ajouter(file,na)

	TANT QUE NON file.estVide()	FAIRE

		na <- file.remove() // traitement du noeud


		SI na.noeud.getID() = a ALORS
			trouveA = VRAI
			niveauA <- na.niveau
		FIN SI

		SI na.noeud.getID() = b ALORS
			trouveB = VRAI
			niveauB <- na.niveau
		FIN SI

		cptNiveau++

		POUR i de 1 à na.noeud.getNbFils()	FAIRE
			na.listeIdPère.add(na.noeud)
			na.noeud <- getFils(i)
			na.niveau <- cptNiveau

			ajouter(file,na)
		FIN POUR

	FIN TANT QUE

	SI (trouveA ET NON trouveB) OU (NON trouveA ET trouveB)	ALORS

		return -1

	FIN SI


	return niveauTotal(noeudA,noeudB)

fin module

module niveauTotal(nouedA,noeudB : noeudAncetre) -> entier

	SI (noeudA.niveau = noeudB.niveau)	ALORS
		return 0
	FIN SI

	i , j , nivAncetre : entier

	POUR i de 1 à n	FAIRE
		POUR j de 1 à n	FAIRE

			SI	noeudA.listeIdPère.get(i).getID() = noeudB.listeIdPère.get(j).getID	ALORS
				nivAncetre <- noeudA.listePère.get(i).niveau
			FIN SI

		FIN POUR
	FIN POUR

	return (noeudA.niveau-nivAncetre) + (noeudB.niveau-nivAncetre)

fin module