给予 二叉搜索树 这也是一个完整的二叉树。问题是将给定的BST转换为一个特殊的最大堆，条件是节点左子树中的所有值都应小于节点右子树中的所有值。此条件应用于so转换的最大堆中的所有节点。 例如：
null
Input : 4 / 2 6 / / 1 3 5 7 Output : 7 / 3 6 / / 1 2 4 5The given BST has been transformed into aMax Heap.All the nodes in the Max Heap satisfies the givencondition, that is, values in the left subtree ofa node should be less than the values in the rightsubtree of the node.
先决条件 : 二叉搜索树 | 堆 方法 1.创建一个数组 arr[] 大小为n，其中n是给定BST中的节点数。 2.执行BST的顺序遍历，并将节点值复制到 arr[] 分类 顺序 3.现在执行树的后序遍历。 4.在后序遍历期间遍历根时，逐个复制数组中的值 arr[] 到节点。
C++
// C++ implementation to convert a given // BST to Max Heap #include <bits/stdc++.h> using namespace std; struct Node { int data; Node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node* getNode( int data) { struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // Function prototype for postorder traversal // of the given tree void postorderTraversal(Node*); // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order void inorderTraversal(Node* root, vector< int >& arr) { if (root == NULL) return ; // first recur on left subtree inorderTraversal(root->left, arr); // then copy the data of the node arr.push_back(root->data); // now recur for right subtree inorderTraversal(root->right, arr); } void BSTToMaxHeap(Node* root, vector< int > &arr, int * i) { if (root == NULL) return ; // recur on left subtree BSTToMaxHeap(root->left, arr, i); // recur on right subtree BSTToMaxHeap(root->right, arr, i); // copy data at index 'i' of 'arr' to // the node root->data = arr[++*i]; } // Utility function to convert the given BST to // MAX HEAP void convertToMaxHeapUtil(Node* root) { // vector to store the data of all the // nodes of the BST vector< int > arr; int i = -1; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr, &i); } // Function to Print Postorder Traversal of the tree void postorderTraversal(Node* root) { if (!root) return ; // recur on left subtree postorderTraversal(root->left); // then recur on right subtree postorderTraversal(root->right); // print the root's data cout << root->data << " " ; } // Driver Code int main() { // BST formation 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); convertToMaxHeapUtil(root); cout << "Postorder Traversal of Tree:" << endl; postorderTraversal(root); return 0; } |
JAVA
// Java implementation to convert a given // BST to Max Heap import java.util.*; class GFG { static int i; static class Node { int data; Node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node getNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order static void inorderTraversal(Node root, Vector<Integer> arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.add(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } static void BSTToMaxHeap(Node root, Vector<Integer> arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr.get(i++); } // Utility function to convert the given BST to // MAX HEAP static void convertToMaxHeapUtil(Node root) { // vector to store the data of all the // nodes of the BST Vector<Integer> arr = new Vector<Integer>(); int i = - 1 ; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree static void postorderTraversal(Node root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data System.out.print(root.data + " " ); } // Driver Code public static void main(String[] args) { // BST formation 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 ); convertToMaxHeapUtil(root); System.out.print( "Postorder Traversal of Tree:" + "" ); postorderTraversal(root); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to convert a given # BST to Max Heap i = 0 class Node: def __init__( self ): self .data = 0 self .left = None self .right = None # Helper function that allocates a new node # with the given data and None left and right # pointers. def getNode(data): newNode = Node() newNode.data = data newNode.left = newNode.right = None return newNode arr = [] # Function for the inorder traversal of the tree # so as to store the node values in 'arr' in # sorted order def inorderTraversal( root): if (root = = None ): return arr # first recur on left subtree inorderTraversal(root.left) # then copy the data of the node arr.append(root.data) # now recur for right subtree inorderTraversal(root.right) def BSTToMaxHeap(root): global i if (root = = None ): return None # recur on left subtree root.left = BSTToMaxHeap(root.left) # recur on right subtree root.right = BSTToMaxHeap(root.right) # copy data at index 'i' of 'arr' to # the node root.data = arr[i] i = i + 1 return root # Utility function to convert the given BST to # MAX HEAP def convertToMaxHeapUtil( root): global i # vector to store the data of all the # nodes of the BST i = 0 # inorder traversal to populate 'arr' inorderTraversal(root) # BST to MAX HEAP conversion root = BSTToMaxHeap(root) return root # Function to Print Postorder Traversal of the tree def postorderTraversal(root): if (root = = None ): return # recur on left subtree postorderTraversal(root.left) # then recur on right subtree postorderTraversal(root.right) # print the root's data print (root.data ,end = " " ) # Driver Code # BST formation 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 ) root = convertToMaxHeapUtil(root) print ( "Postorder Traversal of Tree:" ) postorderTraversal(root) # This code is contributed by Arnab Kundu |
C#
// C# implementation to convert a given // BST to Max Heap using System; using System.Collections.Generic; public class GFG { static int i; public class Node { public int data; public Node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node getNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order static void inorderTraversal(Node root, List< int > arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.Add(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } static void BSTToMaxHeap(Node root, List< int > arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr[i++]; } // Utility function to convert the given BST to // MAX HEAP static void convertToMaxHeapUtil(Node root) { // vector to store the data of all the // nodes of the BST List< int > arr = new List< int >(); int i = -1; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree static void postorderTraversal(Node root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data Console.Write(root.data + " " ); } // Driver Code public static void Main(String[] args) { // BST formation 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); convertToMaxHeapUtil(root); Console.Write( "Postorder Traversal of Tree:" + "" ); postorderTraversal(root); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to convert a given // BST to Max Heap let i = 0; class Node { constructor() { this .data = 0; this .left = this .right = null ; } } /* Helper function that allocates a new node with the given data and null left and right pointers. */ function getNode(data) { let newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Function for the inorder traversal of the tree // so as to store the node values in 'arr' in // sorted order function inorderTraversal(root, arr) { if (root == null ) return ; // first recur on left subtree inorderTraversal(root.left, arr); // then copy the data of the node arr.push(root.data); // now recur for right subtree inorderTraversal(root.right, arr); } function BSTToMaxHeap(root,arr) { if (root == null ) return ; // recur on left subtree BSTToMaxHeap(root.left, arr); // recur on right subtree BSTToMaxHeap(root.right, arr); // copy data at index 'i' of 'arr' to // the node root.data = arr[i++]; } // Utility function to convert the given BST to // MAX HEAP function convertToMaxHeapUtil(root) { // vector to store the data of all the // nodes of the BST let arr = []; // inorder traversal to populate 'arr' inorderTraversal(root, arr); // BST to MAX HEAP conversion BSTToMaxHeap(root, arr); } // Function to Print Postorder Traversal of the tree function postorderTraversal(root) { if (root == null ) return ; // recur on left subtree postorderTraversal(root.left); // then recur on right subtree postorderTraversal(root.right); // print the root's data document.write(root.data + " " ); } // Driver Code // BST formation let 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); convertToMaxHeapUtil(root); document.write( "Postorder Traversal of Tree:" + "" ); postorderTraversal(root); // This code is contributed by rag2127 </script> |
输出：
Postorder Traversal of Tree:1 2 3 4 5 6 7
时间复杂性 ：O（n） 辅助空间 ：O（n） 其中，n是树中的节点数
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
