資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中將 BST 轉換為最大堆
在本教程中，我們將討論一個將二叉搜尋樹轉換為最大堆的程式。
為此，我們將提供一個二叉搜尋樹。我們的任務是將給定的二叉搜尋樹轉換為最大堆，以便在比較元素時遵循二叉搜尋樹的條件。
示例
#include <bits/stdc++.h>
using namespace std;
//node structure of BST
struct Node {
int data;
Node *left, *right;
};
//node creation
struct Node* getNode(int data) {
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
//performing post order traversal
void postorderTraversal(Node*);
//moving in a sorted manner using inorder traversal
void inorderTraversal(Node* root, vector<int>& arr) {
if (root == NULL)
return;
inorderTraversal(root->left, arr);
arr.push_back(root->data);
inorderTraversal(root->right, arr);
}
void convert_BSTHeap(Node* root, vector<int> arr, int* i){
if (root == NULL)
return;
convert_BSTHeap(root->left, arr, i);
convert_BSTHeap(root->right, arr, i);
//copying data from array to node
root->data = arr[++*i];
}
//converting to max heap
void convert_maxheap(Node* root) {
vector<int> arr;
int i = -1;
inorderTraversal(root, arr);
convert_BSTHeap(root, arr, &i);
}
//printing post order traversal
void postorderTraversal(Node* root) {
if (!root)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
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_maxheap(root);
cout << "Postorder Traversal:" << endl;
postorderTraversal(root);
return 0;
}輸出
Postorder Traversal: 1 2 3 4 5 6 7
更新於： 16-Jan-2020
442 次瀏覽
廣告