Для моего кода на C я не уверен, как работает двоичное дерево, потому что мой ожидаемый результат отличается от фактического результата?

Question

Я отслеживаю часть кода, данного профессором, но я не понимаю, как работает двоичное дерево. Вопрос в следующем: «Напишите функцию, чтобы найти наименьшего общего предка в бинарном дереве поиска и вернуть указатель. Наименьший общий предок между двумя узлами a и b в дереве T определяется как самый низкий узел в T, который имеет и a и b как потомки. Рассмотрим следующее дерево в качестве примера. самый низкий общий предок 4 и 8 - 6. самый низкий общий предок 4 и 14 - 10 ".

        10
     6     14
   4  8  12  16 

У меня вопрос, я не понимаю, как это зацикливается?

node *lca(node *ptr, int a, int b)
{
    if(ptr==NULL)
        return NULL;
    while (ptr != NULL)
    {   
        if (ptr->key >= a && ptr->key <= b)//What's key?
            return (ptr);
        else if (ptr->key > b)
            ptr = ptr->left;
        else if (ptr->key < a)
            ptr = ptr->right;
    }
    return (ptr);
}

Answer 1

Идея этого кода заключается в следующем:

Предполагая, что дерево отсортировано в двоичном виде, мы можем проверить, находятся ли элементы a и b на другой стороне текущего узла (еслимы нашли нашу lca).

В двоичном дереве для каждого узла больший элемент направлен вправо, а маленький - влево.Таким образом, если a меньше от текущего узла, а b больше, это означает, что они с другой стороны -> lca.

ptr->key обращается к данным в узле.

Когда первый оператор if завершается неудачно, это означает, что и a, и b находятся с одной и той же стороны -> следующие 2, если оператор выбирает, продолжать поиск вправо или влево (на b меньше, чем текущий узел как на левой стороне, так и еслибольше, чем ток на правой стороне)

Обратите внимание этот код предполагает, что a меньше, чем b.