Terminale NSI

Plus proche ancêtre communs

1. Compléter le tableau ci-dessous, en mettant en dessous de chaque noeud de l'arbre, son père.

noeud 0 1 2 3 4 5 6 7 8 9
père None 0 1 1 0 4 4 4 7 7

2. En déduire le tableau suivant, donnant, pour chaque noeud de l'arbre, la liste de ses ancêtres:

noeud ancêtres
0 0
1 0, 1
2 0,1,2
3 0, 1, 3
4 0, 4
5 0, 4, 5
6 0, 4, 6
7 0, 4, 7
8 0, 4, 7, 8
9 0, 4, 7, 9

3. Compléter le tableau suivant, dans lequel on placera à l'intersection de la ligne i et de la colonne j, le plus proche ancêtre commun à i et j dans l'arbre précédent:

0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 0 0 0 0 0 0
2 0 1 2 1 0 0 0 0 0 0
3 0 1 1 3 0 0 0 0 0 0
4 0 0 0 0 4 4 4 4 4 4
5 0 0 0 0 4 5 4 4 4 4
6 0 0 0 0 4 4 6 4 4 4
7 0 0 0 0 4 4 6 7 7 7
8 0 0 0 0 4 4 4 7 8 7
9 0 0 0 0 4 4 4 7 7 9

4. Compléter le script Python ci-dessous, pour que la variable a ait pour valeur l'arbre de la page précédente:

a = {    0: [1, 4], 
1: [2, 3],
2: [],
3: [],
4: [5,6,7],
5: [],
6: [],
7:[8,9],
8: [],
9: [] }