# 在BST中查找第k個最小元素（BST中的訂單統計信息）

## 問題陳述

“找到第k個最小的元素 BST （“ BST中的訂單統計信息”）問題指出，您獲得了一個二進制搜索樹，需要在BST中找到第k個最小的數字。 這意味著如果我們做一個 為了 遍歷二叉搜索樹並將結果存儲在vector / an數組中。 如果考慮基於1的索引，則索引（k-0）處的元素將是第k個最小元素。

k = 4

`6`

## 途徑

### 增強樹數據結構

#### 推薦碼

##### C ++代碼在BST中找到第k個最小的元素
```#include <bits/stdc++.h>
using namespace std;

struct node{
int data;
int leftCnt;
node *left;
node *right;
} ;

node* create(int data){
node * tmp = new node();
tmp->data = data;
tmp->leftCnt = 0;
tmp->left = tmp->right = NULL;
return tmp;
}

node* insert(node* root, int x)
{
if (root == NULL)
return create(x);
// we do the same as done to insert an element in the BST
// but if we insert an element in the left sub-tree
// we increment the count of nodes in left sub-tree as well
if(x<root->data){
root->left = insert(root->left, x);
root->leftCnt++;
}
else if(x>root->data)
root->right = insert(root->right, x);
return root;
}

node* findKthSmallest(node *root, int k)
{
if (!root)
return NULL;

int cnt = root->leftCnt+1;

// current node is the k-th smallest element
if(cnt == k)
return root;
else if(k > cnt)
return findKthSmallest(root->right, k-cnt);
else
return findKthSmallest(root->left, k);
}

int main()
{
node *root = NULL;
int n;cin>>n;
for(int i=0;i<n;i++){
int element;cin>>element;
root = insert(root, element);
}
int k;cin>>k;
node* res = findKthSmallest(root, k);
if(res == NULL)
cout<<"No kth smallest found";
else
cout<<"Kth smallest element is "<<res->data;
}```
```6
5 4 2 8 6 9
4```
`6`
##### Java代碼在BST中找到第k個最小的元素
```import java.util.*;
import java.lang.*;
import java.io.*;

class node{
int data;
int leftCnt;
node left;
node right;
}

class Tree{
static node root;

static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.leftCnt = 0;
tmp.left = null;
tmp.right = null;
return tmp;
}

static node insert(node root, int x)
{
if (root == null)
return create(x);
// we do the same as done to insert an element in the BST
// but if we insert an element in the left sub-tree
// we increment the count of nodes in left sub-tree as well
if(x<root.data){
root.left = insert(root.left, x);
root.leftCnt++;
}
else if(x>root.data)
root.right = insert(root.right, x);
return root;
}

static node findKthSmallest(node root, int k)
{
if (root == null)
return null;

int cnt = root.leftCnt+1;

// current node is the k-th smallest element
if(cnt == k)
return root;
else if(k > cnt)
return findKthSmallest(root.right, k-cnt);
else
return findKthSmallest(root.left, k);
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=0;i<n;i++){
int element = sc.nextInt();
root = insert(root, element);
}
int k = sc.nextInt();
node res = findKthSmallest(root, k);
if(res == null)
System.out.println("No kth smallest found");
else
System.out.println("Kth smallest element is "+res.data);
}
}```
```6
5 4 2 8 6 9
4```
`Kth smallest element is 6`

### 有序遍歷

#### 推薦碼

##### C ++代碼在BST中找到第k個最小的元素
```#include <bits/stdc++.h>
using namespace std;

struct node{
int data;
node *left;
node *right;
} ;

node* create(int data){
node * tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
return tmp;
}

// normally insert the node in BST
node* insert(node* root, int x)
{
if (root == NULL)
return create(x);
if(x<root->data)
root->left = insert(root->left, x);
else if(x>root->data)
root->right = insert(root->right, x);
return root;
}

node* findKthSmallest(node* root, int& k)
{
// base case
if(!root)
return NULL;
node *left = findKthSmallest(root->left, k);
if(left)
return left;
// if current element is kth smallest
if(k==1)
return root;
// if the kth smallest is not found in the left subtree
// search in right subtree
k--;
return findKthSmallest(root->right, k);
}

int main()
{
node *root = NULL;
int n;cin>>n;
for(int i=0;i<n;i++){
int element;cin>>element;
root = insert(root, element);
}
int k;cin>>k;
node* res = findKthSmallest(root, k);
if(res == NULL)
cout<<"No kth smallest found";
else
cout<<"Kth smallest element is "<<res->data;
}
```
```6
5 4 2 8 6 9
4```
`Kth smallest element is 6`
##### Java代碼在BST中找到第k個最小的元素
```import java.util.*;
import java.lang.*;
import java.io.*;

class node{
int data;
node left;
node right;
}

class Tree{
static node root;
static int count;
static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = null;
tmp.right = null;
return tmp;
}

static node insert(node root, int x)
{
if (root == null)
return create(x);
if(x<root.data)
root.left = insert(root.left, x);
else if(x>root.data)
root.right = insert(root.right, x);
return root;
}

static node findKthSmallest(node root, int k)
{
// base case
if(root == null)
return null;
node left = findKthSmallest(root.left, k);
if(left != null)
return left;
count++;
// if current element is kth smallest
if(k==count)
return root;
// if the kth smallest is not found in the left subtree
// search in right subtree
return findKthSmallest(root.right, k);
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=0;i<n;i++){
int element = sc.nextInt();
root = insert(root, element);
}
int k = sc.nextInt();
count = 0;
node res = findKthSmallest(root, k);
if(res == null)
System.out.println("No kth smallest found");
else
System.out.println("Kth smallest element is "+res.data);
}
}```
```6
5 4 2 8 6 9
4```
`Kth smallest element is 6`