在 C++ 中使用 BST 的预序遍历小于根的元素数
在本教程中,我们将编写一个程序,使用BST中的前序遍历来计算小于根的元素数量。
您将获得预序遍历的结果。您需要找到小于根的元素数。
前序遍历中的第一个元素是BST的根。
让我们看看解决问题的步骤。
在数组中初始化预排序结果。
将第一个元素,即BST的根存储在一个变量中。
编写一个循环,从预排序结果的第二个元素开始迭代。
将每个元素与根进行比较。
如果当前元素大于根,则增加计数。
返回计数。
示例
让我们看看代码。
#include输出结果using namespace std; int getElementsCount(int arr[], int n) { if (n < 0) { return 0; } int i, root = arr[0], count = 0; for(i = 1; i < n; i++) { if(arr[i] < root) { count += 1; } } return count; } int main() { int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9}; int n = 8; cout << getElementsCount(preorder, n) << endl; return 0; }
如果你运行上面的代码,那么你会得到下面的结果。
3
结论
如果您对本教程有任何疑问,请在评论部分提及。