Discussion :

[Acidmaster]

Bonjour,

Dans le cadre d'un développement php, je dois trouver la hauteur d'un arbre non binaire.

J'arrive à le parcourir et à trouver la hauteur de chaque noeuds et feuilles mais je ne sais pas où placer le return pour obtenir la hauteur de l'arbre total.

Voici mon algo :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
public function getTreeHeight($catId, $height) {
		$arrayChild = $this->getChildArray($catId); //tableau contenu les enfants du noeud catId
		echo 'noeud : '.$catId.'<br/>';
		echo 'height : '.$height.'<br/><br/>';
 
		if (count($arrayChild) != 0) {
			foreach ($arrayChild as $c) {
				$this->getTreeHeight($c->getId(), $height + 1);
			}
		}
	}

ce code me donne le résultat suivant par l'arbre ci-dessous (donc résultat correct) :

arbre :



résultat

noeud : -1
height : 0

noeud : 3
height : 1

noeud : 1
height : 2

noeud : 4
height : 3

noeud : 5
height : 4

noeud : 2
height : 3

noeud : 6
height : 4

noeud : 7
height : 4

noeud : 8
height : 5

noeud : 9
height : 3

noeud : 11
height : 4

noeud : 10
height : 3

si vous avez une idée, je suis preneur.

merci.

[pseudocode]

Bon alors je ne maitrise pas du tout le PHP, donc la syntaxe est sans doute fausse, mais voila en gros l'idée:

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
public function getTreeHeight($catId, $height) {
	$arrayChild = $this->getChildArray($catId); //tableau contenu les enfants du noeud catId
	echo 'noeud : '.$catId.'<br/>';
	echo 'height : '.$height.'<br/><br/>';
	$max = $height;	
	if (count($arrayChild) != 0) {
		foreach ($arrayChild as $c) {
			$h = $this->getTreeHeight($c->getId(), $height + 1);
			if ($h>$max) $max = $h;
		}
	}
	return $max;
}

[Acidmaster]

Merci, c'était bien ca !!!

le seul truc qui me manquait (après plusieurs essais) était $max = $height;, je faisant $max = 0...

problème résolu