Discussion :

[aboud abdi]

bonjour tout le monde :
j'ai une question je peut pas la répondre :
comment calculer nombres de sommet pendant d'un arbre binaire et le nombre de sommet interne
merci d’avance

[onilink_]

Salut,
voici des algos qui devraient fonctionner:

(exemple parcours pour comprendre la suite)

Code :

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

1
2
3
4
5
6
7
8
9
parcoursProfondeur(n:node)
debut
si n->sousArbreGauche != NUL alors
  parcoursProfondeur(n->sousArbreGauche);
finsi
si n->sousArbreDroit != NUL alors
  parcoursProfondeur(n->sousArbreDroit);
finsi
fin

sommetsPendants(n:node): entier

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
16
17
18
19
20
21
debut
resultat: entier;
estPendant: booleen;
resultat <- 0;
estPendant <- vrai;
 
si n->sousArbreGauche != NUL alors
  resultat <- resultat + parcoursProfondeur(n->sousArbreGauche);
  estPendant <- faux;
finsi
si n->sousArbreDroit != NUL alors
  resultat <- resultat + parcoursProfondeur(n->sousArbreDroit);
  estPendant <- faux;
finsi
 
si estPendant = vrai alors
  resultat <- 1;
finsi
 
revoyer resultat;
fin

sommetsInternes(n:node): entier

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
16
17
18
19
debut
resultat: entier;
estInterne: bool;
resultat <- 0;
estInterne <- faux;
si n->sousArbreGauche != NUL alors
  resultat <- resultat + parcoursProfondeur(n->sousArbreGauche);
  estInterne <- vrai;
finsi
si n->sousArbreDroit != NUL alors
  resultat <- resultat + parcoursProfondeur(n->sousArbreDroit);
  estInterne <- vrai;
finsi
 
si estInterne = vrai alors
  resultat <- resultat + 1;
finsi
renvoyer resultat;
fin

[aboud abdi]

merci bien mais j'ai par exemple cette formule:
nbr sommet pendant= n+1/2 (avec n l’ordre du l’arbre binaire avec n>=3)
comment on peut la montrer ?
merci pour m'aider