Ubuntu-fr

bassouma

compter les fils d'une arbre n-aire

bonjour
j'ai une arbre n-aire , je veux compter le nombre  de fils de chaque noeud parent d'une arbre
comment le faire ? et merci d’avance
coordialement  Bassouma

tiramiseb

Re : compter les fils d'une arbre n-aire

salut,

tu nous demandes de faire tes devoirs ?

---

Sébastien Maccagnoni - https://www.maccagnoni.eu - https://www.domotego.com

pingouinux

Re : compter les fils d'une arbre n-aire

Bonjour,
Sous quel forme est stocké ton arbre ?
Quel langage de programmation utilises-tu ?

cqfd93

Re : compter les fils d'une arbre n-aire

Bonjour,

T'as posé la question sur faismesdevoirs.com ?

---

− cqfd93 −

claudius01

Re : compter les fils d'une arbre n-aire

Laisse moi te trouver ça...

---

micros informations
- Enregistreur de traces GPS sur Clé USB
- Boussole GPS à Guidage Vocal
- Coprocesseur flottant uM-FPU et PIC16

bassouma

Re : compter les fils d'une arbre n-aire

mon arbre est sous la forme hiérarchie par exemple
                 a
               / | \
              b  c d
              /\  / \
             e f g h
je veux un algorithme pour trouver le nombre de fils de chaque parent et merci pingouinux

bassouma

Re : compter les fils d'une arbre n-aire

salut,

tu nous demandes de faire tes devoirs ?

non j'ai essai mais j'ai trouvé des fautes c'est  pour quoi j'ai demande un aide et merci beaucoup pour ta reponse

joko

Re : compter les fils d'une arbre n-aire

bonjour bassouma et les autres...
ton problème n'est pas très difficile mais bien sur je ne te filerai pas le code (l'ayant perdu)...
en revanche je t'indique une piste (parmi d'autres) : la programmation récursive
j'ai écrit un prog équivalent en ruby qui devait faire 20/30 lignes max

tout dépend de comment tu structures ton arbre
pour ma part j'avais séparé en deux fichiers, celui des données et celui du prog
dans le fichier de données je faisais comme suit :
a-> a,b,c,d
b->e,f
c->g,h

note : avec mon prog, l'ordre de déclaration des branches n'avait aucune importance

le programme lisait ce fichier, remettait tout dans un tableau et roule ma poule
(il trouvait les enfants d'un parent mais aussi pouvait remonter la chaîne arrière-petit-enfant jusqu'au parent initial)

bon courage et regarde du côté de la prog. récursive (souvent présenté comme la crème de la programmation, cela n'est que partiellement vrai)
avec cette méthode il est par exemple possible de créer des databases sans plus jamais de problème de jointure (on associe aux noeuds des valeurs numériques et les requêtes se font sur ces valeurs)
c'est en tout cas un très bon exercice pour les neurones...

---

Je suis un homme, quoi de plus naturel en somme ?
linux on the rocks

joko

Re : compter les fils d'une arbre n-aire

cela ressemble à du déterrage de post mais voici une soluce en ruby, le prog est facile à lire

#!/bin/ruby
t_parent=Array.new
t_enfants=Array.new
g_parent=Array.new
#--------------------------------------------------------------------------------
#la fonction tabul permet l'affichage décalé des enfants et petits-enfants etc...
def tabul( n )
z=""
	n.times do
	z+=" "
	end
return z
end
#--------------------------------------------------------------------------------
#un exemple
#dcl = tableau des déclarations
#le tableau dcl se comprend ainsi 
#a parent de a...x, de fait (a...x) sont une fratrie
#b parent de b1...b4 etc...
dcl=Array.new
dcl=[["a","b","c","d","f","x"],["b","b1","b2","b3","b4"],["c","c1","c2","c3"],["d","d1","d2"],["e","e1","e2"]]
dcl<<["b3-k","b3-k-f","b3-k-z"]
dcl<<["b3","b3-k","b3-z"]
dcl<<["k","k1","k2","k3","k5","k6","k7"]
dcl<<["x","e"]
dcl<<["b1","b1-a","b1-b","b1-c"]
dcl<<["b4","b4-z"]
dcl<<["b1-a","b1-2a-a","b1-3-a","b1-4c-a"]
dcl<<["x","k"]
#--------------------------------------------------------------------------------
#serialisation des declaration sous forme t_parent(i]=parent et t_enfants=enfant 
#liste le tableau
#--------------------------on lit chaque déclaration-----------------------------
lig=0
dcl.each do |i|
	lig_dcl=i #est lui-mm un tableau
	#le parent
	parent=dcl[lig][0]
	#on supprime le 1er élém. du tableau qui est le parent du tableau lig_dcl pour ne garder que les enfants
	lig_dcl.delete_at(0)
	enfants=lig_dcl
	enfants.each do |j| 
		#on push parent + enfant	
		t_parent<<[parent]
		t_enfants<<[j]
	end
#on passe à la déclaration suivante
lig+= 1 
end
#-------------------test sur ggénéalogie ascendante on remonte de l'enfant au "parent zéro"----------------------
#tant que parent non vide faire
enf="k7" # un exemple
z=t_enfants.include?([enf])
if z==false #cas du parent zéro évite une erreur ruby
	puts "c'est le parent zero "
	exit
end
idx_p=t_enfants.index {|obj| obj == [enf]}#on repere l'index de l'enfant = à index parent
puts "parent de " + enf.to_s + " : " + t_parent[idx_p].join.to_s
#tant que le tableau des enfant contient un parent, le parent devient un enfant etc...
while t_enfants.include?t_parent[idx_p] do
	enf=t_parent[idx_p]
	idx_p=t_enfants.index {|obj| obj == enf}#attention enfant est sous la forme [...]
	puts "parent de " + enf.join.to_s+ " : " + t_parent[idx_p].join.to_s
end
#----------------------------------------fin recherche paretn et arrière-p etc...-------------------------------


#--------------------------------------bloc de descendance-------------------------------
puts "parent : > "
parent = gets
parent=parent.chomp
#-----------------------------test-----------------------------
puts "------------------------------bloc desc."
parent=[parent]
g_parent<<parent
#init
niveau=1
puts parent.join.to_s
while niveau !=0 do #recherche (parent dont on veut la généalogie (tant que enfant de enfant faire)
	lig+=1
	k=parent.join
	parent=k
	flag=t_parent.include?([parent])#on vérifie si parent existe= est dans tableau t-parent
	if flag==true 
		idx_p=t_parent.index {|obj| obj == [parent]}# idx_p = index parent=index enfant
		enfant=t_enfants[idx_p]
		puts  tabul(niveau)+ enfant.join.to_s
		g_parent<<parent
		parent=enfant
		niveau+=1
		#delete pour ne pas retomber sur le même couple parent enfant
		t_parent.delete_at(idx_p)
		t_enfants.delete_at(idx_p)
	else
		parent=[g_parent.last]	
		g_parent.pop#retire le dernier élément du tableau
		niveau-=1
	end
end

j'espère que ça en intéressera plus d'un :-)
p.s. le prog est facilement portable et modifiable au niveau des noeuds

Dernière modification par joko (Le 19/07/2015, à 09:09)

---

Je suis un homme, quoi de plus naturel en somme ?
linux on the rocks