Могу ли я найти позицию заданного значения в бинарном дереве поиска лучше?

Question

Мне нужна помощь, чтобы найти (отсортированную) позицию заданного значения в бинарном дереве поиска лучше, чем я это уже сделал (если это возможно).

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

Наш учитель дал нам алгоритм, как найти i-Этот элемент, зная, сколько элементов есть в этом поддереве.Вот почему я задаюсь вопросом, можно ли решить мою проблему за меньшее количество шагов?

Заранее спасибо!

Это не очень оптимальное решение:

template <class T>
int BST<T>::Rang(const T& x) {

int meret = root->size;     //meret = size of the whole 
                            //tree
Node<T>* temp = i_th_Node_rec(1, root);
int i = 1;
while (temp && i <= meret && x != temp->data && x < temp->data) {
    ++i;
    temp = i_th_Node_rec(i, root);
}

return (i < meret) ? i : -1;
}

Answer 1

Это очень похоже на то, как вы находите i: th узел, но «наоборот».

• Если элемент находится в корне, его позиция равна размеру левого поддерева.
• Если элемент находится слева, его позиция совпадает с его позицией в этом поддереве.
• Если элемент находится справа, его позиция - это его позиция в этом поддереве плюсразмер левого поддерева корня плюс один.