数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的二叉搜索树中的第 k 小元素（二叉搜索树中的顺序统计）
假设我们有一个二叉搜索树和一个值 K 作为输入，我们必须找到树中的第 K 个最小元素。
因此，如果输入类似于
k = 3，则输出将为 15。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 find_kth_smallest()，它将使用 root、count、k 作为参数，
如果 root 为 NULL，则：
返回 NULL
left = find_kth_smallest(root 的左元素，count，k)
如果 left 不为 NULL，则：
返回 left
(将 count 递增 1)
如果 count 与 k 相同，则：
返回 root
返回 find_kth_smallest(root 的右元素，count，k)
从主方法中，执行以下操作 −
count := 0
res = find_kth_smallest(root，count，k)
如果 res 为 NULL，则：
显示未找到
否则
显示 res 的 val
示例 (C++)
我们来看一下以下实现以获得更好的理解 −
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) {
val = x;
left = right = NULL;
}
};
TreeNode* find_kth_smallest(TreeNode* root, int &count, int k) {
if (root == NULL)
return NULL;
TreeNode* left = find_kth_smallest(root->left, count, k);
if (left != NULL)
return left;
count++;
if (count == k)
return root;
return find_kth_smallest(root->right, count, k);
}
void kth_smallest(TreeNode* root, int k) {
int count = 0;
TreeNode* res = find_kth_smallest(root, count, k);
if (res == NULL)
cout << "Not found";
else
cout << res->val;
}
int main() {
TreeNode* root = new TreeNode(25);
root->left = new TreeNode(13);
root->right = new TreeNode(27);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(17);
root->left->right->left = new TreeNode(15);
root->left->right->right = new TreeNode(19);
int k = 3;
kth_smallest(root, k);
}输入
TreeNode* root = new TreeNode(25); root->left = new TreeNode(13); root->right = new TreeNode(27); root->left->left = new TreeNode(9); root->left->right = new TreeNode(17); root- >left->right->left = new TreeNode(15); root->left->right->right = new TreeNode(19); k = 3
输出
15
更新于：2020-08-25
487 次观看
广告