資料結構
網路
關係資料庫管理系統
作業系統
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 次觀看
廣告