trouver tous les nombres inférieurs à x dans un BST

Question

comment pourrais-je faire cela? Je ne suis pas sûr quand j'arrêterais la recherche de bst.

Answer 1

Si chaque nœud de votre arbre a un champ numLeft qui vous indique le nombre de nœuds, il y a dans son sous-arbre gauche (lui-même compter aussi), alors vous pouvez le faire dans O(log N)

Il suffit de continuer à ajouter numLeft à un monde variable de résultat pour chaque nœud dont la valeur est inférieure à x:

countLessThan(int x, node T) 
    if T = null 
     return 
    if T.value >= x 
     countLessThan(x, T.left) // T.left contains only numbers < T.value and T.right only numbers > T.value 
    else 
     globalResult += T.numLeft 
     countLessThan(x, T.right) 

Cela ne comptera que les chiffres. Si vous voulez les imprimer, vous devez écrire une première traversée en profondeur qui imprimera une sous-arborescence donnée en paramètre. Vous pouvez trouver beaucoup de ceux en ligne, donc je ne vais pas poster cela.

Answer 2

Vous ne savez pas si c'est exactement ce que vous recherchez ou non, mais les algorithmes d'arborescence de recherche binaire sont classiques et Internet en regorge. http://www.algolist.net/Data_structures/Binary_search_tree/Lookup - devrait au moins vous mettre dans la bonne direction (vous voudriez modifier la condition 'found' et retourner une 'collection' au lieu d'une bool).

Answer 3

Si vous avez besoin d'une liste de numéros, vous devrez quand même traverser l'arborescence. Pour BST, vous pouvez faire le déplacement du plus bas au plus haut.
Mais si vous avez besoin sous-arbre qui représente chiffres les plus bas:

def splitLowerTree(x, node): 
    if node is None: return None 
    elif node.value == x: return node.left 
    elif node.value < x: 
     if node.right is None: return node 
     else: return Node(node.value, left = node.left, right = splitLowerTree(x, node.right)) 
    else: return splitLowerTree(x, node.left)