Trouver le nombre de nœuds qui n'ont qu'un seul enfant
La construction d’un arbre binaire peut se faire de manière récursive. Supposons que l’arbre soit construit en se basant sur des données saisies par l’utilisateur. Si le nœud n’existe pas, l’utilisateur entre la valeur 0, et s’il existe, il utilise un nombre positif.
En partant de la racine, on lit la valeur indiquée par l’utilisateur et on poursuit la construction du sous-arbre si la valeur est positive ; si elle est égale à 0, on interrompt la récursion à cet endroit.
vals = map(int, input().split()) # Lit les valeurs de BST depuis l'entrée
idx = 0 # Index de la valeur courante
root = Node(vals[idx]) # Définit la valeur du nœud racine
def read(node: Node): # Lit récursivement toutes les données dans l'arbre
if node.value == 0: # Si la valeur courante est 0 => le nœud n'existe pas
return # Donc, on ne lit pas ses enfants gauche et droit
node.left = Node(vals[idx + 1]) # Définit la valeur du nœud gauche
node.right = Node(vals[idx + 2]) # Définit la valeur du nœud droit
idx += 2 # Met à jour l'index de la valeur courante
read(node.left) # Demande les données de la sous-arbre gauche à l'utilisateur
read(node.right) # Demande les données de la sous-arbre droit à l'utilisateurIci, on remarque que le nombre de nœuds n’est pas déterminé au départ. Le programme lit récursivement toutes les valeurs, en commençant par le sous-arbre gauche et en remontant ensuite vers le sous-arbre droit, jusqu’à ce que la valeur du nœud soit 0. Une fois qu’un nœud ne contient plus de valeur positive, on s’arrête pour cet embranchement et on passe aux autres. Ce processus se poursuit jusqu’à ce que tous les nœuds du bas soient à 0 et qu’il n’y ait plus de valeurs à lire. Ainsi, pour l’exemple d’arbre illustré ci-dessus, la saisie de l’utilisateur pourrait ressembler à ceci :
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left does not exist (no left child of 4)
0 # root.left.left.right does not exist (no right child of 4)
0 # root.left.right.left does not exist (no left child of 5)
0 # root.left.right.right does not exist (no right child of 5)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left does not exist (no left child of 6)
0 # root.right.left.right does not exist (no right child of 6)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left does not exist (no left child of 8)
0 # root.right.right.left.right does not exist (no right child of 8)
0 # root.right.right.right.left does not exist (no left child of 9)
0 # root.right.right.right.right does not exist (no right child of 9)On peut aussi représenter cette séquence de valeurs sous forme de tableau, par exemple :
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], qui correspond à la même structure d’arbre binaire. Au lieu de demander à l’utilisateur une nouvelle valeur à chaque étape, il est alors possible d’itérer sur ce tableau et de construire l’arbre de manière récursive comme décrit plus haut.Étant donné un arbre binaire valide, vous devez déterminer le nombre de nœuds qui ont un seul enfant.
Entrée
L’entrée contient des entiers séparés par des espaces, représentant les valeurs des nœuds de l’arbre binaire. L’ordre des valeurs suit la logique décrite ci-dessus. Une valeur de 0 signifie que le nœud n’existe pas.
Sortie
Le programme doit afficher le nombre de nœuds dans un arbre binaire qui n’ont qu’un seul enfant.
Exemples
Entrée | Sortie |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 0 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 |
Explication
- Dans le premier exemple, l’arbre binaire ne contient aucun nœud avec un seul enfant.
- Dans le second exemple, l’arbre binaire ne possède qu’un seul nœud ayant un enfant unique : le nœud dont la valeur est 3.
Pro tip 😎
Vous pouvez modifier le code ci-dessus pour créer les nœuds de manière conditionnelle : ne créer un nœud et l’assigner à
node.left ou node.right que si la valeur saisie est différente de 0.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB