二叉搜索树BST是一种二进制数据结构，包含具有一些属性的各种节点，包括：
- 左子树节点小于根节点。
- 右子树节点比根节点多。
- 树节点的每个节点的子节点形成二叉搜索树。
问题陈述
我们需要找到现有二叉搜索树中的第 K 大元素。这意味着我们首先将二叉搜索树的元素按降序排列；然后，我们将从二叉搜索树中搜索第 k 大的元素。
让我们借助示例来理解问题陈述。
输入：
k = 4
Binary Search Tree
Root Node
15
/ \
8 25
/ \
6 21
/ / \
13 14 18
|
输出：
14
我们有一棵二叉搜索树，需要搜索第 K 个最大的元素。我们的输入为 4，即 k 为 4。我们需要从二叉搜索树中搜索第 4 大元素。我们首先将二叉搜索树中的元素按降序排列，然后找出第 4 大元素。
在 BST 中查找第 K 大元素的方法
在 BST 中查找第 k 个元素有不同的方法。这包括：
1. 幼稚的方法
使用朴素的方法，我们可以存储中序遍历，然后我们将找到n - k + 1 个元素，其中 n 是元素的数量，k 是我们需要搜索的元素。这种方法的空间复杂度为O(N)，这意味着它将占用更多空间并且效率低下。
因此，我们将使用更有效的方法来查找二叉搜索树中的第 K 大元素。
2. 逆莫里斯遍历
该方法基于线程二叉树。线程二叉树只是一个带有额外线程的普通二叉树，这有助于轻松遍历树。它使用NULL指针，它存储了后继和前驱（前一个和下一个节点），用于使用这些NULL指针未使用的内存。
逆向莫里斯遍历只是逆向莫里斯遍历。与莫里斯遍历不同，在莫里斯遍历中，我们首先移动到左子树，然后移动到右子树，而不使用堆栈或递归，在反向莫里斯遍历中，我们将首先遍历右子树，然后再遍历左子树。它消耗了恒定的 O(1) 额外内存。这是在二叉搜索树中查找第 k 大元素的最佳且最有效的方法。
此问题陈述的逻辑是执行反向中序遍历，默认情况下按降序排序给出列表，并跟踪访问的节点数。当该计数等于我们要搜索的元素 (k) 时，我们将打印该元素。
寻找二叉搜索树中第k大元素的实现
class new_Node:
def __init__(self, ele):
self.ele = ele
self.right = self.left = None
def KthLargestElement(root, k):
current = root
Klargestele = None
cnt = 0 # count variable
while (current != None):
# checking if the right child is None
if (current.right == None):
# 增加计数，然后检查计数是否等于 k ；
cnt += 1
if (cnt == k):
# If it matches the current is the required element
Klargestele = current
# else move it to the left child
current = current.left
else:
# finding inorder successor
succ_node = current.right
while (succ_node.left != None and
succ_node.left != current):
succ_node = succ_node.left
if (succ_node.left == None):
succ_node.left = current
# moving current to its right
current = current.right
# removing thread links and getting the binary tree
else:
succ_node.left = None
cnt += 1
if (cnt == k):
Klargest = current
# moving current to its left child
current = current.left
return Klargestele
if __name__ == '__main__':
root = new_Node(8)
root.left = new_Node(1)
root.right = new_Node(9)
root.left.left = new_Node(3)
root.left.right = new_Node(2)
root.right.left = new_Node(11)
root.right.right = new_Node(15)
pos=input("Enter the kth element to be searched: ")
print("The K-th largest Node in Binary Search Tree is : ",
KthLargestElement(root, pos).ele)
|
输出：
Enter the kth element to be searched: 3
The K-th largest Node in Binary Search Tree is : 11
使用的二叉树是
我们首先将当前节点初始化为根节点。我们初始化了一个计数变量，以相反的顺序遍历二叉树，检查第 k 个元素是否与当前节点匹配，并计算节点数。我们发现第 11 个元素是第 k 个最大的元素（k = 3）。