在C ++中找到O(n)时间和O(1)空间中BST的中位数
概念
对于给定的二叉搜索树(BST)，我们的任务是确定其中值。
甚至没有。节点数，中位数=（（n/2个节点+（n+1）/2个节点）/2）对于奇数个节点，中位数=（n+1）/2个节点。
对于给定的BST（节点数为奇数）为-
7
/ \
4 9
/ \ / \
2 5 8 10给定BST的顺序为：2、4、5、7、8、9、10因此，这里的中位数为7。
对于给定的BST（甚至偶数个节点）是-
7
/ \
4 9
/ \ /
2 5 8给定的BST的顺序为-2，4，5，5，7，8，9
因此，此处的中位数为（5+7）/2=6。
方法
为了确定中位数，我们需要确定BST的顺序，因为BST的顺序将按照排序顺序，然后确定中位数。在这里，该概念基于使用O(1)额外空间的BST中第K个最小元素。现在，如果允许我们实现额外的空间，则任务非常简单，但是实现递归和堆栈的顺序遍历都使用此处不允许的空间。
结果，解决方案是执行Morris有序遍历，因为它不需要任何额外的空间。
莫里斯有序遍历的解释如下-
我们将电流初始化为根
虽然当前不为NULL
如果当前还没有孩子
打印当前数据
向右移动，即current=current->right
其他
将current构造为current的左子树中最右边节点的right子代
移至该左孩子，即current=current->left
最终实现以以下方式讨论-
我们算数。给定BST中实现Morris有序遍历的节点的数量。
之后，通过对节点进行计数并验证计数是否等于中点，再执行一次莫里斯有序遍历。
对于考虑甚至没有。对于节点，实现了指向先前节点的额外指针。
示例
/* C++ program to find the median of BST in O(n) time and O(1)
space*/
#include<bits/stdc++.h>
using namespace std;
/* Implements a binary search tree Node1 which has data, pointer
to left child and a pointer to right child */
struct Node1{
int data1;
struct Node1* left1, *right1;
};
//Shows a utility function to create a new BST node
struct Node1 *newNode(int item1){
struct Node1 *temp1 = new Node1;
temp1->data1 = item1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
/* Shows a utility function to insert a new node with
given key in BST */
struct Node1* insert(struct Node1* node1, int key1){
/* It has been seen that if the tree is empty, return a new node
*/
if (node1 == NULL) return newNode(key1);
/* Else, recur down the tree */
if (key1 < node1->data1)
node1->left1 = insert(node1->left1, key1);
else if (key1 > node1->data1)
node1->right1 = insert(node1->right1, key1);
/* return the (unchanged) node pointer */
return node1;
}
/* Shows function to count nodes in a binary search tree
using Morris Inorder traversal*/
int counNodes(struct Node1 *root1){
struct Node1 *current1, *pre1;
// Used to initialise count of nodes as 0
int count1 = 0;
if (root1 == NULL)
return count1;
current1 = root1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count node if its left is NULL
count1++;
// Go to its right
current1 = current1->right1;
} else {
/* Determine the inorder predecessor of current */
pre1 = current1->left1;
while (pre1->right1 != NULL &&
pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder predecessor */
if(pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* we have to revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
// Now increment count if the current
// node is to be visited
count1++;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
return count1;
}
/* Shows function to find median in O(n) time and O(1) space
using Morris Inorder traversal*/
int findMedian(struct Node1 *root1){
if (root1 == NULL)
return 0;
int count1 = counNodes(root1);
int currCount1 = 0;
struct Node1 *current1 = root1, *pre1, *prev1;
while (current1 != NULL){
if (current1->left1 == NULL){
// Now count current node
currCount1++;
// Verify if current node is the median
// Odd case
if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
return prev1->data1;
// Even case
else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
return (prev1->data1 + current1->data1)/2;
// Now update prev1 for even no. of nodes
prev1 = current1;
//Go to the right
current1 = current1->right1;
} else {
/* determine the inorder predecessor of current1 */
pre1 = current1->left1;
while (pre1->right1 != NULL && pre1->right1 != current1)
pre1 = pre1->right1;
/* Construct current1 as right child of its inorder
predecessor */
if (pre1->right1 == NULL){
pre1->right1 = current1;
current1 = current1->left1;
}
/* We have to revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else {
pre1->right1 = NULL;
prev1 = pre1;
// Now count current node
currCount1++;
// Verify if the current node is the median
if (count1 % 2 != 0 && currCount1 == (count1+1)/2 )
return current1->data1;
else if (count1%2==0 && currCount1 == (count1/2)+1)
return (prev1->data1+current1->data1)/2;
// Now update prev1 node for the case of even
// no. of nodes
prev1 = current1;
current1 = current1->right1;
} /* End of if condition pre1->right1 == NULL */
} /* End of if condition current1->left1 == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main(){
/* Let us create following BST
7
/ \
4 9
/ \ / \
2 5 8 10 */
struct Node1 *root1 = NULL;
root1 = insert(root1, 7);
insert(root1, 4);
insert(root1, 2);
insert(root1, 5);
insert(root1, 9);
insert(root1, 8);
insert(root1, 10);
cout << "\nMedian of BST is(for odd no. of nodes) "<< findMedian(root1) <<endl;
/* Let us create following BST
7
/ \
4 9
/ \ /
2 5 8
*/
struct Node1 *root2 = NULL;
root2 = insert(root2, 7);
insert(root2, 4);
insert(root2, 2);
insert(root2, 5);
insert(root2, 9);
insert(root2, 8);
cout << "\nMedian of BST is(for even no. of nodes) "
<< findMedian(root2);
return 0;
}输出结果
Median of BST is(for odd no. of nodes) 7 Median of BST is(for even no. of nodes) 6