Discussion :

[Nirolac]

Bonjour à tous,
Je me tourne vers vous car j'ai un problème sur une fonction sur un type d'arbre, ces arbres sont des quadtrees c'est à dire soit une feuille d'une couleur Noir ou Blanche soit un noeud de quadtrees (4 fils). comme fonction je dois, dans le cadre de mon projet avoir un arbre dont la taille est la même sur tous les sous arbres, j'ai donc essayé de créer une fonction qui si la taille du plus grand sous arbre n'est pas la même que dans le sous arbre dans lequel je suis alors je remplace Feuille Blanc (ou feuille Noir) par Noeud(Feuille Blanc, FEuille Blanc, Feuille Blanc, Feuille Blanc), cependant cela ne marche pas et je ne comprends pas pourquoi si quelqu'un peut m'aider ce serait vraiment sympa car cela fait 15 jours que je suis dessus j'en peux vraiment
voici la fonction qui donne la taille du plus grand sous arbre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
type couleur = Blanc | Noir 
type quad = Feuille of couleur | Noeud of quad * quad * quad * quad
 
let max_four a b c d = 
	let max1 = max a b
	and max2 = max c d
	in max max1 max2;;
 
(max_four 5 12 65 27);;
 
let rec height = function arbre ->
	match arbre with 
	| Feuille _ -> 0
	| Noeud(e,f,g,h) -> 1 + (max_four (height e)(height f)(height g)(height h));;

et voici la fonction pour rendre l'arbre de la même taille que le plus grand sous arbre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
let dev arb =
	let rec aux arb n =
		match (aux,arb) with
		| (arb, n) when arb = Blanc -> aux (Noeud(Feuille Blanc,Feuille Blanc,Feuille Blanc,Feuille Blanc))  (n - 1)
		| (arb, n) when arb = Blanc -> aux (Noeud(Feuille Blanc,Feuille Blanc,Feuille Blanc,Feuille Blanc)) (n - 1)
		| (arb, 0) when arb = Noir -> (Noeud(Feuille Noir,Feuille Noir,Feuille Noir,Feuille Noir))
		| (arb, 0) when arb = Noir -> (Noeud(Feuille Noir,Feuille Noir,Feuille Noir,Feuille Noir))
		| (Noeud(a,b,c,d), n) when (height a) < n -> (aux a n)
		| (Noeud(a,b,c,d), n) when (height b) < n -> (aux b n)
		| (Noeud(a,b,c,d), n) when (height c) < n -> (aux c n)
		| (Noeud(a,b,c,d), n) when (height d) < n -> (aux d n)
		| _->(arb, 0)
		in aux arb (height arb);;

Bonne journée à tous et merci d'avance !