给定二叉搜索树的根和K作为输入，在BST中找到第K个最小元素。 例如，在下面的BST中，如果k=3，则输出应为10，如果k=5，则输出应为14。
null
![图片[1]-按顺序查找第k个元素（BST统计）-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/BST.gif)
方法1：使用顺序遍历（O（n）时间和O（h）辅助空间） 这个 有序遍历 一个 英国夏令时 以递增的顺序遍历节点。所以我们的想法是按顺序遍历树。在遍历时，跟踪访问的节点数。如果计数变为k，则打印节点。
C++
// A simple inorder traversal based C++ program // to find k-th smallest element in a BST. #include <iostream> using namespace std; // A BST node struct Node { int data; Node *left, *right; Node( int x) { data = x; left = right = NULL; } }; // Recursive function to insert an key into BST Node* insert(Node* root, int x) { if (root == NULL) return new Node(x); if (x < root->data) root->left = insert(root->left, x); else if (x > root->data) root->right = insert(root->right, x); return root; } // Function to find k'th smallest element in BST // Here count denotes the number of nodes processed so far Node* kthSmallest(Node* root, int & k) { // base case if (root == NULL) return NULL; // search in left subtree Node* left = kthSmallest(root->left, k); // if k'th smallest is found in left subtree, return it if (left != NULL) return left; // if current element is k'th smallest, return it k--; if (k == 0) return root; // else search in right subtree return kthSmallest(root->right, k); } // Function to print k'th smallest element in BST void printKthSmallest(Node* root, int k) { // maintain index to count number of nodes processed so far int count = 0; Node* res = kthSmallest(root, k); if (res == NULL) cout << "There are less than k nodes in the BST" ; else cout << "K-th Smallest Element is " << res->data; } // main function int main() { Node* root = NULL; int keys[] = { 20, 8, 22, 4, 12, 10, 14 }; for ( int x : keys) root = insert(root, x); int k = 3; printKthSmallest(root, k); return 0; } |
JAVA
// A simple inorder traversal based Java program // to find k-th smallest element in a BST. import java.io.*; // A BST node class Node { int data; Node left, right; Node( int x) { data = x; left = right = null ; } } class GFG { static int count = 0 ; // Recursive function to insert an key into BST public static Node insert(Node root, int x) { if (root == null ) return new Node(x); if (x < root.data) root.left = insert(root.left, x); else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest element in BST // Here count denotes the number // of nodes processed so far public static Node kthSmallest(Node root, int k) { // base case if (root == null ) return null ; // search in left subtree Node left = kthSmallest(root.left, k); // if k'th smallest is found in left subtree, return it if (left != null ) return left; // if current element is k'th smallest, return it count++; if (count == k) return root; // else search in right subtree return kthSmallest(root.right, k); } // Function to find k'th largest element in BST public static void printKthSmallest(Node root, int k) { // maintain an index to count number of // nodes processed so far count = 0 ; Node res = kthSmallest(root, k); if (res == null ) System.out.println( "There are less " + "than k nodes in the BST" ); else System.out.println( "K-th Smallest" + " Element is " + res.data); } public static void main (String[] args) { Node root = null ; int keys[] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 }; for ( int x : keys) root = insert(root, x); int k = 3 ; printKthSmallest(root, k); } } |
Python3
# A simple inorder traversal based Python3 # program to find k-th smallest element # in a BST. # A BST node class Node: def __init__( self , key): self .data = key self .left = None self .right = None # Recursive function to insert an key into BST def insert(root, x): if (root = = None ): return Node(x) if (x < root.data): root.left = insert(root.left, x) elif (x > root.data): root.right = insert(root.right, x) return root # Function to find k'th largest element # in BST. Here count denotes the number # of nodes processed so far def kthSmallest(root): global k # Base case if (root = = None ): return None # Search in left subtree left = kthSmallest(root.left) # If k'th smallest is found in # left subtree, return it if (left ! = None ): return left # If current element is k'th # smallest, return it k - = 1 if (k = = 0 ): return root # Else search in right subtree return kthSmallest(root.right) # Function to find k'th largest element in BST def printKthSmallest(root): # Maintain index to count number # of nodes processed so far count = 0 res = kthSmallest(root) if (res = = None ): print ( "There are less than k nodes in the BST" ) else : print ( "K-th Smallest Element is " , res.data) # Driver code if __name__ = = '__main__' : root = None keys = [ 20 , 8 , 22 , 4 , 12 , 10 , 14 ] for x in keys: root = insert(root, x) k = 3 printKthSmallest(root) # This code is contributed by mohit kumar 29 |
C#
// A simple inorder traversal // based C# program to find // k-th smallest element in a BST. using System; // A BST node class Node{ public int data; public Node left, right; public Node( int x) { data = x; left = right = null ; } } class GFG{ static int count = 0; // Recursive function to // insert an key into BST public static Node insert(Node root, int x) { if (root == null ) return new Node(x); if (x < root.data) root.left = insert(root.left, x); else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest // element in BST. Here count // denotes the number of nodes // processed so far public static Node kthSmallest(Node root, int k) { // base case if (root == null ) return null ; // search in left subtree Node left = kthSmallest(root.left, k); // if k'th smallest is found // in left subtree, return it if (left != null ) return left; // if current element is // k'th smallest, return it count++; if (count == k) return root; // else search in right subtree return kthSmallest(root.right, k); } // Function to find k'th largest // element in BST public static void printKthSmallest(Node root, int k) { // Maintain an index to // count number of nodes // processed so far count = 0; Node res = kthSmallest(root, k); if (res == null ) Console.WriteLine( "There are less " + "than k nodes in the BST" ); else Console.WriteLine( "K-th Smallest" + " Element is " + res.data); } // Driver code public static void Main(String[] args) { Node root = null ; int []keys = {20, 8, 22, 4, 12, 10, 14}; foreach ( int x in keys) root = insert(root, x); int k = 3; printKthSmallest(root, k); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // A simple inorder traversal based Javascript program // to find k-th smallest element in a BST. // A BST node class Node { constructor(x) { this .data = x; this .left = null ; this .right = null ; } } let count = 0; // Recursive function to insert an key into BST function insert(root,x) { if (root == null ) return new Node(x); if (x < root.data) root.left = insert(root.left, x); else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest element in BST // Here count denotes the number // of nodes processed so far function kthSmallest(root,k) { // base case if (root == null ) return null ; // search in left subtree let left = kthSmallest(root.left, k); // if k'th smallest is found in left subtree, return it if (left != null ) return left; // if current element is k'th smallest, return it count++; if (count == k) return root; // else search in right subtree return kthSmallest(root.right, k); } // Function to find k'th largest element in BST function printKthSmallest(root,k) { // maintain an index to count number of // nodes processed so far count = 0; let res = kthSmallest(root, k); if (res == null ) document.write( "There are less " + "than k nodes in the BST" ); else document.write( "K-th Smallest" + " Element is " + res.data); } let root= null ; let key=[20, 8, 22, 4, 12, 10, 14 ]; for (let i=0;i<key.length;i++) { root = insert(root, key[i]); } let k = 3; printKthSmallest(root, k); // This code is contributed by unknown2108 </script> |
输出：
K-th Smallest Element is 10
我们可以利用 莫里斯穿越 .请参考 BST中使用O（1）额外空间的第K个最小元素 详细信息。
方法2：增广树数据结构（O（h）时间复杂度和O（h）辅助空间） 其思想是保持每个节点的排名。在构建树时，我们可以跟踪每个节点的左子树中的元素。因为我们需要第K个最小元素，所以我们可以在每个节点中保持左子树的元素数。 假设根在其左子树中有’lCount’节点。如果K=lCount+1，则root是第K个节点。如果K
C++
// A simple inorder traversal based C++ program // to find k-th smallest element in a BST. #include <iostream> using namespace std; // A BST node struct Node { int data; Node *left, *right; int lCount; Node( int x) { data = x; left = right = NULL; lCount = 0; } }; // Recursive function to insert an key into BST Node* insert(Node* root, int x) { if (root == NULL) return new Node(x); // If a node is inserted in left subtree, then // lCount of this node is increased. For simplicity, // we are assuming that all keys (tried to be // inserted) are distinct. if (x < root->data) { root->left = insert(root->left, x); root->lCount++; } else if (x > root->data) root->right = insert(root->right, x); return root; } // Function to find k'th smallest element in BST // Here count denotes the number of nodes processed so far Node* kthSmallest(Node* root, int k) { // base case if (root == NULL) return NULL; int count = root->lCount + 1; if (count == k) return root; if (count > k) return kthSmallest(root->left, k); // else search in right subtree return kthSmallest(root->right, k - count); } // main function int main() { Node* root = NULL; int keys[] = { 20, 8, 22, 4, 12, 10, 14 }; for ( int x : keys) root = insert(root, x); int k = 4; Node* res = kthSmallest(root, k); if (res == NULL) cout << "There are less than k nodes in the BST" ; else cout << "K-th Smallest Element is " << res->data; return 0; } |
JAVA
// A simple inorder traversal based Java program // to find k-th smallest element in a BST. import java.io.*; import java.util.*; // A BST node class Node { int data; Node left, right; int lCount; Node( int x) { data = x; left = right = null ; lCount = 0 ; } } class Gfg { // Recursive function to insert an key into BST public static Node insert(Node root, int x) { if (root == null ) return new Node(x); // If a node is inserted in left subtree, then // lCount of this node is increased. For simplicity, // we are assuming that all keys (tried to be // inserted) are distinct. if (x < root.data) { root.left = insert(root.left, x); root.lCount++; } else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest element in BST // Here count denotes the number of // nodes processed so far public static Node kthSmallest(Node root, int k) { // base case if (root == null ) return null ; int count = root.lCount + 1 ; if (count == k) return root; if (count > k) return kthSmallest(root.left, k); // else search in right subtree return kthSmallest(root.right, k - count); } // main function public static void main(String args[]) { Node root = null ; int keys[] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 }; for ( int x : keys) root = insert(root, x); int k = 4 ; Node res = kthSmallest(root, k); if (res == null ) System.out.println( "There are less " + "than k nodes in the BST" ); else System.out.println( "K-th Smallest" + " Element is " + res.data); } } |
Python3
# A simple inorder traversal based Python3 # program to find k-th smallest element in a BST. # A BST node class newNode: def __init__( self , x): self .data = x self .left = None self .right = None self .lCount = 0 # Recursive function to insert # an key into BST def insert(root, x): if (root = = None ): return newNode(x) # If a node is inserted in left subtree, # then lCount of this node is increased. # For simplicity, we are assuming that # all keys (tried to be inserted) are # distinct. if (x < root.data): root.left = insert(root.left, x) root.lCount + = 1 elif (x > root.data): root.right = insert(root.right, x); return root # Function to find k'th largest element # in BST. Here count denotes the number # of nodes processed so far def kthSmallest(root, k): # Base case if (root = = None ): return None count = root.lCount + 1 if (count = = k): return root if (count > k): return kthSmallest(root.left, k) # Else search in right subtree return kthSmallest(root.right, k - count) # Driver code if __name__ = = '__main__' : root = None keys = [ 20 , 8 , 22 , 4 , 12 , 10 , 14 ] for x in keys: root = insert(root, x) k = 4 res = kthSmallest(root, k) if (res = = None ): print ( "There are less than k nodes in the BST" ) else : print ( "K-th Smallest Element is" , res.data) # This code is contributed by bgangwar59 |
C#
// A simple inorder traversal based C# program // to find k-th smallest element in a BST. using System; // A BST node public class Node { public int data; public Node left, right; public int lCount; public Node( int x) { data = x; left = right = null ; lCount = 0; } } class GFG{ // Recursive function to insert an key into BST public static Node insert(Node root, int x) { if (root == null ) return new Node(x); // If a node is inserted in left subtree, // then lCount of this node is increased. // For simplicity, we are assuming that // all keys (tried to be inserted) are // distinct. if (x < root.data) { root.left = insert(root.left, x); root.lCount++; } else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest element // in BST. Here count denotes the number // of nodes processed so far public static Node kthSmallest(Node root, int k) { // Base case if (root == null ) return null ; int count = root.lCount + 1; if (count == k) return root; if (count > k) return kthSmallest(root.left, k); // Else search in right subtree return kthSmallest(root.right, k - count); } // Driver Code public static void Main(String[] args) { Node root = null ; int [] keys = { 20, 8, 22, 4, 12, 10, 14 }; foreach ( int x in keys) root = insert(root, x); int k = 4; Node res = kthSmallest(root, k); if (res == null ) Console.WriteLine( "There are less " + "than k nodes in the BST" ); else Console.WriteLine( "K-th Smallest" + " Element is " + res.data); } } // This code is contributed by aashish1995 |
Javascript
<script> // A simple inorder traversal based // Javascript program to find k-th // smallest element in a BST. // A BST node class Node { constructor(x) { this .data = x; this .left = null ; this .right = null ; this .lCount = 0; } } // Recursive function to insert an key into BST function insert(root, x) { if (root == null ) return new Node(x); // If a node is inserted in left subtree, // then lCount of this node is increased. // For simplicity, we are assuming that // all keys (tried to be inserted) are // distinct. if (x < root.data) { root.left = insert(root.left, x); root.lCount++; } else if (x > root.data) root.right = insert(root.right, x); return root; } // Function to find k'th largest element // in BST. Here count denotes the number // of nodes processed so far function kthSmallest(root, k) { // Base case if (root == null ) return null ; let count = root.lCount + 1; if (count == k) return root; if (count > k) return kthSmallest(root.left, k); // Else search in right subtree return kthSmallest(root.right, k - count); } // Driver code let root = null ; let keys = [ 20, 8, 22, 4, 12, 10, 14 ]; for (let x = 0; x < keys.length; x++) root = insert(root, keys[x]); let k = 4; let res = kthSmallest(root, k); if (res == null ) document.write( "There are less than k " + "nodes in the BST" + "</br>" ); else document.write( "K-th Smallest" + " Element is " + res.data); // This code is contributed by divyeshrabadiya07 </script> |
输出：
K-th Smallest Element is 12
时间复杂性： O（h），其中h是树的高度。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
