使用 O(1)额外空间的 BST 中的第 K 个最小元素
原文:https://www . geesforgeks . org/kth-最小元素 in-BST-using-O1-extra-space/
给定一个二叉查找树和一个正整数 k，求二叉查找树中第 k 个最小的元素。 比如下面的 BST，如果 k = 3，那么输出应该是 10，如果 k = 5，那么输出应该是 14。
我们在这个岗位讨论了两种方法，这个岗位讨论了一种方法。前面所有的方法都需要额外的空间。如何在没有多余空间的情况下找到 k 的最大元素？
想法是使用莫里斯遍历。在这个遍历中，我们首先创建到 Inorder 后继的链接，并使用这些链接打印数据，最后恢复更改以恢复原始树。详见本。 下面是这个想法的实现。
C++
// C++ program to find k'th largest element in BST
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct Node
{
int key;
Node *left, *right;
};
// A function to find
int KSmallestUsingMorris(Node *root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = INT_MIN; // store the Kth smallest
Node *curr = root; // to store the current node
while (curr != NULL)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr->left == NULL)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr->key;
// go to current's right child
curr = curr->right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
// building links
if (pre->right==NULL)
{
//link made to Inorder Successor
pre->right = curr;
curr = curr->left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre->right = NULL;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr->key;
curr = curr->right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
for (int k=1; k<=7; k++)
cout << KSmallestUsingMorris(root, k) << " ";
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to find k'th largest element in BST
import java.util.*;
class GfG {
// A BST node
static class Node
{
int key;
Node left, right;
}
// A function to find
static int KSmallestUsingMorris(Node root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = Integer.MIN_VALUE; // store the Kth smallest
Node curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right== null)
{
//link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
return temp;
}
/* A utility function to insert a new node with given key in BST */
static Node insert(Node node, int key)
{
/* If the tree is empty, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
public static void main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
for (int k=1; k<=7; k++)
System.out.print(KSmallestUsingMorris(root, k) + " ");
}
}
Python 3
# Python 3 program to find k'th
# largest element in BST
# A BST node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.key = data
self.left = None
self.right = None
# A function to find
def KSmallestUsingMorris(root, k):
# Count to iterate over elements
# till we get the kth smallest number
count = 0
ksmall = -9999999999 # store the Kth smallest
curr = root # to store the current node
while curr != None:
# Like Morris traversal if current does
# not have left child rather than
# printing as we did in inorder, we
# will just increment the count as the
# number will be in an increasing order
if curr.left == None:
count += 1
# if count is equal to K then we
# found the kth smallest, so store
# it in ksmall
if count == k:
ksmall = curr.key
# go to current's right child
curr = curr.right
else:
# we create links to Inorder Successor
# and count using these links
pre = curr.left
while (pre.right != None and
pre.right != curr):
pre = pre.right
# building links
if pre.right == None:
# link made to Inorder Successor
pre.right = curr
curr = curr.left
# While breaking the links in so made
# temporary threaded tree we will check
# for the K smallest condition
else:
# Revert the changes made in if part
# (break link from the Inorder Successor)
pre.right = None
count += 1
# If count is equal to K then we
# found the kth smallest and so
# store it in ksmall
if count == k:
ksmall = curr.key
curr = curr.right
return ksmall # return the found value
# A utility function to insert a new
# node with given key in BST
def insert(node, key):
# If the tree is empty,
# return a new node
if node == None:
return Node(key)
# Otherwise, recur down the tree
if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
# return the (unchanged) node pointer
return node
# Driver Code
if __name__ == '__main__':
# Let us create following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)
for k in range(1,8):
print(KSmallestUsingMorris(root, k),
end = " ")
# This code is contributed by PranchalK
C
// C# program to find k'th largest element in BST
using System;
class GfG
{
// A BST node
public class Node
{
public int key;
public Node left, right;
}
// A function to find
static int KSmallestUsingMorris(Node root, int k)
{
// Count to iterate over elements till we
// get the kth smallest number
int count = 0;
int ksmall = int.MinValue; // store the Kth smallest
Node curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
Node pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right == null)
{
// link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count == k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
return temp;
}
/* A utility function to insert a new node with given key in BST */
static Node insert(Node node, int key)
{
/* If the tree is empty, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
public static void Main(String[] args)
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
for (int k = 1; k <= 7; k++)
Console.Write(KSmallestUsingMorris(root, k) + " ");
}
}
// This code has been contributed by 29AjayKumar
java 描述语言
<script>
// javascript program to find k'th largest element in BST
// A BST node
class Node {
constructor() {
this.key = 0;
this.left = null;
this.right = null;
}
}
// A function to find
function KSmallestUsingMorris(root , k)
{
// Count to iterate over elements till we
// get the kth smallest number
var count = 0;
var ksmall = Number.MIN_VALUE; // store the Kth smallest
var curr = root; // to store the current node
while (curr != null)
{
// Like Morris traversal if current does
// not have left child rather than printing
// as we did in inorder, we will just
// increment the count as the number will
// be in an increasing order
if (curr.left == null)
{
count++;
// if count is equal to K then we found the
// kth smallest, so store it in ksmall
if (count==k)
ksmall = curr.key;
// go to current's right child
curr = curr.right;
}
else
{
// we create links to Inorder Successor and
// count using these links
var pre = curr.left;
while (pre.right != null && pre.right != curr)
pre = pre.right;
// building links
if (pre.right== null)
{
//link made to Inorder Successor
pre.right = curr;
curr = curr.left;
}
// While breaking the links in so made temporary
// threaded tree we will check for the K smallest
// condition
else
{
// Revert the changes made in if part (break link
// from the Inorder Successor)
pre.right = null;
count++;
// If count is equal to K then we found
// the kth smallest and so store it in ksmall
if (count==k)
ksmall = curr.key;
curr = curr.right;
}
}
}
return ksmall; //return the found value
}
// A utility function to create a new BST node
function newNode(item)
{
var temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
return temp;
}
/* A utility function to insert a new node with given key in BST */
function insert(node , key)
{
/* If the tree is empty, return a new node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
var root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
for (k=1; k<=7; k++)
document.write(KSmallestUsingMorris(root, k) + " ");
// This code contributed by Rajput-Ji
</script>
输出:
20 30 40 50 60 70 80
本文由 Abhishek Somani 供稿。如果发现有不正确的地方，请写评论，或者想分享更多关于以上讨论话题的信息
版权属于：月萌API www.moonapi.com，转载请注明出处
