Dado un árbol de búsqueda binario, conviértalo en un montón mínimo que contenga los mismos elementos en tiempo O(n). Haz esto en el lugar.
Input: Binary Search Tree
8
/ \
4 12
/ \ / \
2 6 10 14
Output - Min Heap
2
/ \
4 6
/ \ / \
8 10 12 14
[Or any other tree that follows Min Heap
properties and has same keys]
Si se nos permite usar espacio adicional, podemos realizar un recorrido en orden del árbol y almacenar las claves en una array auxiliar. Como estamos haciendo un recorrido en orden en un BST, la array se ordenará. Finalmente, construimos un árbol binario completo a partir de la array ordenada. Construimos el árbol binario nivel por nivel y de izquierda a derecha tomando el siguiente elemento mínimo de la array ordenada. El árbol binario construido será un montón mínimo. Esta solución funciona en tiempo O(n), pero no está en el lugar.
¿Cómo hacerlo en el lugar?
La idea es convertir primero el árbol de búsqueda binaria en una lista ordenada ordenada. Podemos hacer esto atravesando el BST en orden. Agregamos Nodes al comienzo de la lista enlazada actual y actualizamos el encabezado de la lista usando puntero a puntero de encabezado. Dado que insertamos al principio, para mantener el orden ordenado, primero recorremos el subárbol derecho antes que el subárbol izquierdo. es decir, hacer un recorrido en orden inverso.
Finalmente, convertimos la lista ordenada ordenada en un montón mínimo configurando los punteros izquierdo y derecho de manera adecuada. Podemos hacer esto haciendo un recorrido de orden de nivel del árbol de montón mínimo parcialmente construido usando la cola y recorriendo la lista vinculada al mismo tiempo. En cada paso, tomamos el Node principal de la cola, hacemos los siguientes dos Nodes de la lista enlazada como hijos del Node principal y ponemos en cola los siguientes dos Nodes. A medida que se ordena la lista vinculada, se mantiene la propiedad min-heap.
A continuación se muestra la implementación de la idea anterior:
C++
//C++ Program to convert a BST into a Min-Heap
// in O(n) time and in-place
#include <bits/stdc++.h>
using namespace std;
// Node for BST/Min-Heap
struct Node
{
int data;
Node *left, *right;
};
// Utility function for allocating node for BST
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// Utility function to print Min-heap level by level
void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL) return;
// Create an empty queue for level order traversal
queue<Node *> q;
q.push(root);
while (!q.empty())
{
int nodeCount = q.size();
while (nodeCount > 0)
{
Node *node = q.front();
cout << node->data << " ";
q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
nodeCount--;
}
cout << endl;
}
}
// A simple recursive function to convert a given
// Binary Search tree to Sorted Linked List
// root --> Root of Binary Search Tree
// head_ref --> Pointer to head node of created
// linked list
void BSTToSortedLL(Node* root, Node** head_ref)
{
// Base cases
if(root == NULL)
return;
// Recursively convert right subtree
BSTToSortedLL(root->right, head_ref);
// insert root into linked list
root->right = *head_ref;
// Change left pointer of previous head
// to point to NULL
if (*head_ref != NULL)
(*head_ref)->left = NULL;
// Change head of linked list
*head_ref = root;
// Recursively convert left subtree
BSTToSortedLL(root->left, head_ref);
}
// Function to convert a sorted Linked
// List to Min-Heap.
// root --> Root of Min-Heap
// head --> Pointer to head node of sorted
// linked list
void SortedLLToMinHeap(Node* &root, Node* head)
{
// Base Case
if (head == NULL)
return;
// queue to store the parent nodes
queue<Node *> q;
// The first node is always the root node
root = head;
// advance the pointer to the next node
head = head->right;
// set right child to NULL
root->right = NULL;
// add first node to the queue
q.push(root);
// run until the end of linked list is reached
while (head)
{
// Take the parent node from the q and remove it from q
Node* parent = q.front();
q.pop();
// Take next two nodes from the linked list and
// Add them as children of the current parent node
// Also in push them into the queue so that
// they will be parents to the future nodes
Node *leftChild = head;
head = head->right; // advance linked list to next node
leftChild->right = NULL; // set its right child to NULL
q.push(leftChild);
// Assign the left child of parent
parent->left = leftChild;
if (head)
{
Node *rightChild = head;
head = head->right; // advance linked list to next node
rightChild->right = NULL; // set its right child to NULL
q.push(rightChild);
// Assign the right child of parent
parent->right = rightChild;
}
}
}
// Function to convert BST into a Min-Heap
// without using any extra space
Node* BSTToMinHeap(Node* &root)
{
// head of Linked List
Node *head = NULL;
// Convert a given BST to Sorted Linked List
BSTToSortedLL(root, &head);
// set root as NULL
root = NULL;
// Convert Sorted Linked List to Min-Heap
SortedLLToMinHeap(root, head);
}
// Driver code
int main()
{
/* Constructing below tree
8
/ \
4 12
/ \ / \
2 6 10 14
*/
Node* root = newNode(8);
root->left = newNode(4);
root->right = newNode(12);
root->right->left = newNode(10);
root->right->right = newNode(14);
root->left->left = newNode(2);
root->left->right = newNode(6);
BSTToMinHeap(root);
/* Output - Min Heap
2
/ \
4 6
/ \ / \
8 10 12 14
*/
printLevelOrder(root);
return 0;
}
Java
// Java Program to convert a BST into a Min-Heap
// in O(n) time and in-place
import java.util.*;
class GFG
{
// Node for BST/Min-Heap
static class Node
{
int data;
Node left, right;
};
// Utility function for allocating node for BST
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// Utility function to print Min-heap level by level
static void printLevelOrder(Node root)
{
// Base Case
if (root == null) return;
// Create an empty queue for level order traversal
Queue<Node> q = new LinkedList<>();
q.add(root);
while (q.size() > 0)
{
int nodeCount = q.size();
while (nodeCount > 0)
{
Node node = q.peek();
System.out.print( node.data + " ");
q.remove();
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
nodeCount--;
}
System.out.println();
}
}
// A simple recursive function to convert a given
// Binary Search tree to Sorted Linked List
// root -. Root of Binary Search Tree
// head_ref -. Pointer to head node of created
// linked list
static Node BSTToSortedLL(Node root, Node head_ref)
{
// Base cases
if(root == null)
return head_ref;
// Recursively convert right subtree
head_ref = BSTToSortedLL(root.right, head_ref);
// insert root into linked list
root.right = head_ref;
// Change left pointer of previous head
// to point to null
if (head_ref != null)
(head_ref).left = null;
// Change head of linked list
head_ref = root;
// Recursively convert left subtree
head_ref = BSTToSortedLL(root.left, head_ref);
return head_ref;
}
// Function to convert a sorted Linked
// List to Min-Heap.
// root -. Root of Min-Heap
// head -. Pointer to head node of sorted
// linked list
static Node SortedLLToMinHeap(Node root, Node head)
{
// Base Case
if (head == null)
return null;
// queue to store the parent nodes
Queue<Node > q = new LinkedList<>();
// The first node is always the root node
root = head;
// advance the pointer to the next node
head = head.right;
// set right child to null
root.right = null;
// add first node to the queue
q.add(root);
// run until the end of linked list is reached
while (head != null)
{
// Take the parent node from the q and remove it from q
Node parent = q.peek();
q.remove();
// Take next two nodes from the linked list and
// Add them as children of the current parent node
// Also in add them into the queue so that
// they will be parents to the future nodes
Node leftChild = head;
head = head.right; // advance linked list to next node
leftChild.right = null; // set its right child to null
q.add(leftChild);
// Assign the left child of parent
parent.left = leftChild;
if (head != null)
{
Node rightChild = head;
head = head.right; // advance linked list to next node
rightChild.right = null; // set its right child to null
q.add(rightChild);
// Assign the right child of parent
parent.right = rightChild;
}
}
return root;
}
// Function to convert BST into a Min-Heap
// without using any extra space
static Node BSTToMinHeap(Node root)
{
// head of Linked List
Node head = null;
// Convert a given BST to Sorted Linked List
head = BSTToSortedLL(root, head);
// set root as null
root = null;
// Convert Sorted Linked List to Min-Heap
root = SortedLLToMinHeap(root, head);
return root;
}
// Driver code
public static void main(String args[])
{
/* Constructing below tree
8
/ \
4 12
/ \ / \
2 6 10 14
*/
Node root = newNode(8);
root.left = newNode(4);
root.right = newNode(12);
root.right.left = newNode(10);
root.right.right = newNode(14);
root.left.left = newNode(2);
root.left.right = newNode(6);
root = BSTToMinHeap(root);
/* Output - Min Heap
2
/ \
4 6
/ \ / \
8 10 12 14
*/
printLevelOrder(root);
}
}
// This code is contributed by andrew1234
Python3
# Python3 program to construct all unique # BSTs for keys from 1 to n # Binary Tree Node """ A utility function to create a new BST node """ class newNode: # Construct to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None # Utility function to print Min-heap # level by level def printLevelOrder(root): # Base Case if (root == None): return # Create an empty queue for level # order traversal q = [] q.append(root) while (len(q)): nodeCount = len(q) while (nodeCount > 0) : node = q[0] print(node.data, end = " " ) q.pop(0) if (node.left) : q.append(node.left) if (node.right) : q.append(node.right) nodeCount -= 1 print() # A simple recursive function to convert a # given Binary Search tree to Sorted Linked # List root -. Root of Binary Search Tree def BSTToSortedLL(root, head_ref): # Base cases if(root == None) : return # Recursively convert right subtree BSTToSortedLL(root.right, head_ref) # insert root into linked list root.right = head_ref[0] # Change left pointer of previous # head to point to None if (head_ref[0] != None): (head_ref[0]).left = None # Change head of linked list head_ref[0] = root # Recursively convert left subtree BSTToSortedLL(root.left, head_ref) # Function to convert a sorted Linked # List to Min-Heap. # root -. root[0] of Min-Heap # head -. Pointer to head node of # sorted linked list def SortedLLToMinHeap( root, head) : # Base Case if (head == None) : return # queue to store the parent nodes q = [] # The first node is always the # root node root[0] = head[0] # advance the pointer to the next node head[0] = head[0].right # set right child to None root[0].right = None # add first node to the queue q.append(root[0]) # run until the end of linked list # is reached while (head[0] != None) : # Take the parent node from the q # and remove it from q parent = q[0] q.pop(0) # Take next two nodes from the linked # list and Add them as children of the # current parent node. Also in push them # into the queue so that they will be # parents to the future nodes leftChild = head[0] head[0] = head[0].right # advance linked list to next node leftChild.right = None # set its right child to None q.append(leftChild) # Assign the left child of parent parent.left = leftChild if (head) : rightChild = head[0] head[0] = head[0].right # advance linked list to next node rightChild.right = None # set its right child to None q.append(rightChild) # Assign the right child of parent parent.right = rightChild # Function to convert BST into a Min-Heap # without using any extra space def BSTToMinHeap(root): # head of Linked List head = [None] # Convert a given BST to Sorted Linked List BSTToSortedLL(root, head) # set root as None root = [None] # Convert Sorted Linked List to Min-Heap SortedLLToMinHeap(root, head) return root # Driver Code if __name__ == '__main__': """ Constructing below tree 8 / \ 4 12 / \ / \ 2 6 10 14 """ root = newNode(8) root.left = newNode(4) root.right = newNode(12) root.right.left = newNode(10) root.right.right = newNode(14) root.left.left = newNode(2) root.left.right = newNode(6) root = BSTToMinHeap(root) """ Output - Min Heap 2 / \ 4 6 / \ / \ 8 10 12 14 """ printLevelOrder(*root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# Program to convert a BST into a Min-Heap
// in O(n) time and in-place
using System;
using System.Collections.Generic;
public class GFG
{
// Node for BST/Min-Heap
public
class Node
{
public
int data;
public
Node left, right;
};
// Utility function for allocating node for BST
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// Utility function to print Min-heap level by level
static void printLevelOrder(Node root)
{
// Base Case
if (root == null) return;
// Create an empty queue for level order traversal
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0)
{
int nodeCount = q.Count;
while (nodeCount > 0)
{
Node node = q.Peek();
Console.Write( node.data + " ");
q.Dequeue();
if (node.left != null)
q.Enqueue(node.left);
if (node.right != null)
q.Enqueue(node.right);
nodeCount--;
}
Console.WriteLine();
}
}
// A simple recursive function to convert a given
// Binary Search tree to Sorted Linked List
// root -. Root of Binary Search Tree
// head_ref -. Pointer to head node of created
// linked list
static Node BSTToSortedLL(Node root, Node head_ref)
{
// Base cases
if(root == null)
return head_ref;
// Recursively convert right subtree
head_ref = BSTToSortedLL(root.right, head_ref);
// insert root into linked list
root.right = head_ref;
// Change left pointer of previous head
// to point to null
if (head_ref != null)
(head_ref).left = null;
// Change head of linked list
head_ref = root;
// Recursively convert left subtree
head_ref = BSTToSortedLL(root.left, head_ref);
return head_ref;
}
// Function to convert a sorted Linked
// List to Min-Heap.
// root -. Root of Min-Heap
// head -. Pointer to head node of sorted
// linked list
static Node SortedLLToMinHeap(Node root, Node head)
{
// Base Case
if (head == null)
return null;
// queue to store the parent nodes
Queue<Node > q = new Queue<Node>();
// The first node is always the root node
root = head;
// advance the pointer to the next node
head = head.right;
// set right child to null
root.right = null;
// add first node to the queue
q.Enqueue(root);
// run until the end of linked list is reached
while (head != null)
{
// Take the parent node from the q and remove it from q
Node parent = q.Peek();
q.Dequeue();
// Take next two nodes from the linked list and
// Add them as children of the current parent node
// Also in add them into the queue so that
// they will be parents to the future nodes
Node leftChild = head;
head = head.right; // advance linked list to next node
leftChild.right = null; // set its right child to null
q.Enqueue(leftChild);
// Assign the left child of parent
parent.left = leftChild;
if (head != null)
{
Node rightChild = head;
head = head.right; // advance linked list to next node
rightChild.right = null; // set its right child to null
q.Enqueue(rightChild);
// Assign the right child of parent
parent.right = rightChild;
}
}
return root;
}
// Function to convert BST into a Min-Heap
// without using any extra space
static Node BSTToMinHeap(Node root)
{
// head of Linked List
Node head = null;
// Convert a given BST to Sorted Linked List
head = BSTToSortedLL(root, head);
// set root as null
root = null;
// Convert Sorted Linked List to Min-Heap
root = SortedLLToMinHeap(root, head);
return root;
}
// Driver code
public static void Main(String []args)
{
/* Constructing below tree
8
/ \
4 12
/ \ / \
2 6 10 14
*/
Node root = newNode(8);
root.left = newNode(4);
root.right = newNode(12);
root.right.left = newNode(10);
root.right.right = newNode(14);
root.left.left = newNode(2);
root.left.right = newNode(6);
root = BSTToMinHeap(root);
/* Output - Min Heap
2
/ \
4 6
/ \ / \
8 10 12 14
*/
printLevelOrder(root);
}
}
// This code is contributed by aashish1995
Javascript
<script>
// Javascript Program to convert a BST into a Min-Heap
// in O(n) time and in-place
// Node for BST/Min-Heap
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Utility function for allocating node for BST
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// Utility function to print Min-heap level by level
function printLevelOrder(root)
{
// Base Case
if (root == null) return;
// Create an empty queue for level order traversal
var q = [];
q.push(root);
while (q.length > 0)
{
var nodeCount = q.length;
while (nodeCount > 0)
{
var node = q[0];
document.write( node.data + " ");
q.shift();
if (node.left != null)
q.push(node.left);
if (node.right != null)
q.push(node.right);
nodeCount--;
}
document.write("<br>");
}
}
// A simple recursive function to convert a given
// Binary Search tree to Sorted Linked List
// root -. Root of Binary Search Tree
// head_ref -. Pointer to head node of created
// linked list
function BSTToSortedLL(root, head_ref)
{
// Base cases
if(root == null)
return head_ref;
// Recursively convert right subtree
head_ref = BSTToSortedLL(root.right, head_ref);
// insert root into linked list
root.right = head_ref;
// Change left pointer of previous head
// to point to null
if (head_ref != null)
(head_ref).left = null;
// Change head of linked list
head_ref = root;
// Recursively convert left subtree
head_ref = BSTToSortedLL(root.left, head_ref);
return head_ref;
}
// Function to convert a sorted Linked
// List to Min-Heap.
// root -. Root of Min-Heap
// head -. Pointer to head node of sorted
// linked list
function SortedLLToMinHeap( root, head)
{
// Base Case
if (head == null)
return null;
// queue to store the parent nodes
var q = [];
// The first node is always the root node
root = head;
// advance the pointer to the next node
head = head.right;
// set right child to null
root.right = null;
// add first node to the queue
q.push(root);
// run until the end of linked list is reached
while (head != null)
{
// Take the parent node from the q and remove it from q
var parent = q[0];
q.shift();
// Take next two nodes from the linked list and
// Add them as children of the current parent node
// Also in add them into the queue so that
// they will be parents to the future nodes
var leftChild = head;
head = head.right; // advance linked list to next node
leftChild.right = null; // set its right child to null
q.push(leftChild);
// Assign the left child of parent
parent.left = leftChild;
if (head != null)
{
var rightChild = head;
head = head.right; // advance linked list to next node
rightChild.right = null; // set its right child to null
q.push(rightChild);
// Assign the right child of parent
parent.right = rightChild;
}
}
return root;
}
// Function to convert BST into a Min-Heap
// without using any extra space
function BSTToMinHeap(root)
{
// head of Linked List
var head = null;
// Convert a given BST to Sorted Linked List
head = BSTToSortedLL(root, head);
// set root as null
root = null;
// Convert Sorted Linked List to Min-Heap
root = SortedLLToMinHeap(root, head);
return root;
}
// Driver code
/* Constructing below tree
8
/ \
4 12
/ \ / \
2 6 10 14
*/
var root = newNode(8);
root.left = newNode(4);
root.right = newNode(12);
root.right.left = newNode(10);
root.right.right = newNode(14);
root.left.left = newNode(2);
root.left.right = newNode(6);
root = BSTToMinHeap(root);
/* Output - Min Heap
2
/ \
4 6
/ \ / \
8 10 12 14
*/
printLevelOrder(root);
</script>
Producción
2 4 6 8 10 12 14
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA