gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-28 01:20:47 24 4
gpt4 key购买 nike

我需要一些帮助,了解如何在二叉搜索树中找到给定值的(排序的)位置,比我已经做的更好(如果可能的话)。

我有另一种方法可以搜索树的第 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;
}

最佳答案

这与您定位第 i:th 节点的方式非常相似,但“相反”。

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

关于c++ - 我可以更好地找到给定值在二叉搜索树中的位置吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56396816/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com