在C ++中将BST转换为Min Heap
在本教程中，我们将讨论将二进制搜索树转换为最小堆的程序。
为此，我们将提供一个二进制搜索树。我们的任务是将给定的二进制搜索树转换为最小堆，以便在元素与自身进行比较时遵循二进制搜索树的条件。
示例
#include <bits/stdc++.h>
using namespace std;
//BST的节点结构
struct Node {
int data;
Node *left, *right;
};
//节点创建
struct Node* getNode(int data) {
struct Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
//执行预遍历
void preorderTraversal(Node*);
//以排序方式存储值
//有序遍历
void inorderTraversal(Node *root, vector<int>& arr) {
if (root == NULL)
return;
inorderTraversal(root->left, arr);
arr.push_back(root->data);
inorderTraversal(root->right, arr);
}
//将BST转换为最小堆
void convert_BSPheap(Node *root, vector<int> arr, int *i) {
if (root == NULL)
return;
root->data = arr[++*i];
convert_BSPheap(root->left, arr, i);
convert_BSPheap(root->right, arr, i);
}
//转换为最小堆
void convert_minheap(Node *root) {
//存储节点值的向量
vector<int> arr;
int i = -1;
//通过顺序遍历移动
inorderTraversal(root, arr);
convert_BSPheap(root, arr, &i);
}
//执行预遍历
void preorderTraversal(Node *root) {
if (!root)
return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
struct Node *root = getNode(4);
root->left = getNode(2);
root->right = getNode(6);
root->left->left = getNode(1);
root->left->right = getNode(3);
root->right->left = getNode(5);
root->right->right = getNode(7);
convert_minheap(root);
cout << "预购遍历：" << endl;
preorderTraversal(root);
return 0;
}输出
预购遍历： 1 2 3 4 5 6 7
热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短