Arbres (2) Construction
Construction d'un arbre⚓︎
On dispose de deux arbres, (une forêt), et on souhaite construire un nouvel arbre avec un nœud racine et les deux arbres donnés comme sous-arbres de la racine.
Exemple avec deux arbres et le nouvel arbre obtenu:
graph TB
r2(( )) --- n21(( ))
r2 --- n22(( ))
r2 --- n23(( ))
r1(( )) --- n11(( ))
r1 --- n12(( ))
n12 --- n13(( ))
n12 --- n14(( ))
r3(( )) --- n32(( ))
r3 --- n31(( ))
n32 --- n331(( ))
n32 --- n332(( ))
n32 --- n333(( ))
n31 --- n311(( ))
n31 --- n312(( ))
n312 --- n313(( ))
n312 --- n314(( ))Les \(n\) nœuds d'un arbre sont numérotés de \(0\) à \(n-1\) dans n'importe quel ordre.
Les nœuds sont numérotés:
graph TB
r2((3)) --- n21((0))
r2 --- n22((1))
r2 --- n23((2))
r1((1)) --- n11((0))
r1 --- n12((2))
n12 --- n13((3))
n12 --- n14((4))
r3((9)) --- n32((3))
r3 --- n31((5))
n32 --- n331((0))
n32 --- n332((1))
n32 --- n333((2))
n31 --- n311((4))
n31 --- n312((6))
n312 --- n313((7))
n312 --- n314((8))Implémentation⚓︎
Un arbre est représenté par un tableau, dans lequel les indices représentent les numéros des nœuds. La valeur à l'indice \(i\) représente le numéro (et l'indice) du parent du nœud \(i\). Si un élément à l'indice \(i\) vaut \(i\), cela signifie que le nœud numéro \(i\) n'a pas de parent: c'est donc la racine. La racine est donc l’unique nœud ayant une valeur égale à son indice.
Les trois arbres représentés ci-dessus sont implémentés par les tableaux: [3, 3, 3, 3], [1, 1, 1, 2, 2], [3, 3, 3, 9, 5, 9, 5, 6, 6, 9].
Pour construire un nouvel arbre à partir de deux arbres, si on suppose les nœuds du premier arbre numérotés de \(0\) à \(n-1\) et les nœuds du deuxième arbre numérotés de \(0\) à \(m-1\):
- On crée un tableau de longueur \(n+m+1\), par exemple
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; - On conserve les numéros des nœuds du premier arbre (de \(0\) à \(n-1\)), soit
[3, 3, 3, 3, 0, 0, 0, 0, 0, 0]; - Le nœud racine du premier arbre a pour racine le nœud numéro \(n+m\), soit
[3, 3, 3, 9, 0, 0, 0, 0, 0, 0]; - On décale les numéros des nœuds du deuxième arbre (de \(n\) à \(n+m-1\)), soit
[3, 3, 3, 9, 5, 5, 5, 6, 6, 0]; - Le nœud racine du deuxième arbre a pour racine le nœud numéro \(n+m\), soit
[3, 3, 3, 9, 5, 9, 5, 6, 6, 0]; - La racine du nouvel arbre reçoit le numéro \(n+m\), soit
[3, 3, 3, 9, 5, 9, 5, 6, 6, 9].
On demande d'écrire une fonction construction qui prend en paramètres deux arbres, et renvoie l'arbre construit en suivant le procédé décrit ci-dessus.
Exemples
>>> construction([3, 3, 3, 3], [1, 1, 1, 2, 2])
[3, 3, 3, 9, 5, 9, 5, 6, 6, 9]
>>> construction([2, 2, 2], [2, 2, 3, 3, 3])
[2, 2, 8, 5, 5, 6, 8, 6, 8]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)