Как сделать нижнюю границу в бинарном дереве поиска? - PullRequest
Новая
       3

Как сделать нижнюю границу в бинарном дереве поиска?

0 голосов
/ 29 ноября 2011

Я сделал ближайшую нижнюю границу, когда дал какое-то целое число в дереве бинарного поиска 

  def lowerBound(x : Int) : Int = {
    var t = root
    var result : Int = 0
    while(t.key != x) {
        if(x == t.key) {
            result = t.left.key
        }
        else{
          if(x < t.key) {
            t = t.left
            if(t == null) {
                throw new NoSuchElementException     
            }
            else {
                result = t.key
            }
          }
          else {
            t = t.right
          }
        }
  }
  result
}

Я сделал так.но это не печатает никакого результата.T T .... есть какой-нибудь встречный пример в моем алгоритме?

, если {2, 3, 5, 7, 8, 10, 99} lowerBound (6) равно 5.

1 Ответ

2 голосов
/ 29 ноября 2011

Домашнее задание

Всего несколько указателей:

  • Вы можете успешно выйти из цикла только с t.key == x, поэтому вы не можете вернуться успешно, если x не находится в дереве. Звучит неправильно.
  • Если в какой-то момент вы решите пойти направо, то вы знаете, что в дереве есть хотя бы одно значение меньше x. Таким образом, после того, как вы по крайней мере один раз попали прямо, есть решение, и вы не должны терпеть неудачу. Это не появляется в вашем коде.
  • Когда вы решите идти по правильному пути, возможно, что там не будет никаких данных, вы должны проверить это.
  • Нарисуйте маленький BST и проверьте свои идеи на чертеже, это должно очень помочь.

Также

  • будь уверен в том, что ты вычисляешь. Наибольший элемент меньше или равен x или строго меньше x?
  • возможно, вы можете попробовать рекурсивную реализацию.
...