数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找 BST 的中位数，时间复杂度为 O(n)，空间复杂度为 O(1)
概念
对于给定的二叉搜索树 (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、7、8、9
因此，这里的中位数将是 (5+7)/2 = 6。
方法
为了确定中位数，我们需要确定 BST 的中序遍历，因为它的中序遍历将按排序顺序排列，然后确定中位数。在这里，这个概念基于使用 O(1) 额外空间的 BST 中第 K 个最小元素。现在，如果允许我们实现额外的空间，那么任务非常简单，但中序遍历实现递归和栈都使用空间，这里不允许。
因此，解决方案是执行 Morris 中序遍历，因为它不需要任何额外空间。
Morris 中序遍历的解释如下 -
- 我们将 current 初始化为根节点
- 当 current 不为 NULL 时
如果 current 没有左子节点
- 打印 current 的数据
- 移到右侧，即 current = current->right
否则
- 将 current 构造为 current 的左子树中最右侧节点的右子节点
- 移到这个左子节点，即 current = current->left
最终实现以以下方式讨论 -
我们使用 Morris 中序遍历计算给定 BST 中的节点数。
之后，再次执行 Morris 中序遍历，同时计算节点数并验证计数是否等于中位数点。
为了考虑偶数个节点，实现了一个额外的指针指向前一个节点。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
示例
/* 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
更新于： 2020-07-25
777 次查看
广告