найти все числа меньше, чем х в BST

Question

как бы я это сделал?Я не уверен, когда остановлю поиск bst.

Answer 1

Если у каждого узла вашего дерева есть поле numLeft, которое сообщает вам, сколько узлов есть в его левом поддереве (считая себя тоже), то вы можете сделать это в O(log N)

Просто добавляйте numLeft к глобальной переменной результата для каждого узла, значение которого меньше 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)

Это будет считать только числа. Если вы хотите распечатать их, вам нужно написать первый обход глубины, который будет печатать поддерево, заданное в качестве параметра. Вы можете найти много таких в Интернете, поэтому я не буду это публиковать.

Answer 2

Если вам нужен список чисел, вы все равно должны пройти по дереву. Для BST вы можете перемещаться от низшего к высшему.
Но если вам нужно поддерево, которое представляет наименьшее число:

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)

Answer 3

Не уверен, что это именно то, что вы ищете или нет, но алгоритмы бинарного дерева поиска классические, и в интернете их полно.http://www.algolist.net/Data_structures/Binary_search_tree/Lookup - должен, по крайней мере, заставить вас двигаться в правильном направлении (вы бы хотели изменить условие 'found' и вернуть вместо 'bool' коллекцию).