c++ - 我可以更好地找到给定值在二叉搜索树中的位置吗？

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 节点的方式非常相似，但“相反”。

• 如果元素在根中，它的位置就是左子树的大小。
• 如果元素在左边，则它的位置与它在该子树中的位置相同。
• 如果元素在右边，则它的位置是它在该子树中的位置加上根的左子树的大小再加一。