Section des rosiers
🏷️ On considère ici des arbres étiquetés et ordonnés. (Ce qui était toujours le cas jusqu'à présent.)
Rappel : Arbres ordonnés
On dit qu'un arbre est ordonné lorsque l'ordre de ses sous-arbres compte.
Par exemple, les deux arbres ordonnés suivants sont distincts. (Si on avait considérés ces arbres comme non ordonnés, ils auraient été identiques.)
flowchart TB
subgraph "A_droite"
direction TB
N0(5) --> N1(7)
N0 --> N2(9)
N0 --> N3(1)
N3 --> N4(4)
N3 --> N5(2)
end
subgraph "A_gauche"
direction TB
M0(5) --> M1(1)
M0 --> M2(9)
M0 --> M3(7)
M1 --> M4(2)
M1 --> M5(4)
endSécateur sur rosier
Un jardinier décide de couper des branches de son rosier assimilé à un arbre. Il décide de garder au maximum les q premières branches de chaque nœud et de couper les autres. Par exemple, avec q = 2
flowchart TB
subgraph "Après"
direction TB
N0(5) --> N1(1)
N0 --> N2(9)
N1 --> N4(2)
N1 --> N5(4)
N5 --> N6(5)
N5 --> N7(6)
end
subgraph "Avant"
direction TB
M0(5) --> M1(1)
M0 --> M2(9)
M0 --> M3(7)
M1 --> M4(2)
M1 --> M5(4)
M5 --> M6(5)
M5 --> M7(6)
M5 --> M8(3)
endExercice
Coder une fonction section qui prend un arbre ordonné et étiqueté et un entier q en paramètres et qui renvoie une copie de l'arbre, mais qui aura au maximum q sous-arbres par nœud, les derniers étant éventuellement sectionnés.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)