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: [] }