Dado un árbol binario, conviértalo en un árbol de búsqueda binario. La conversión debe hacerse de tal manera que se mantenga la estructura original de Binary Tree.
Ejemplos
Example 1
Input:
10
/ \
2 7
/ \
8 4
Output:
8
/ \
4 10
/ \
2 7
Example 2
Input:
10
/ \
30 15
/ \
20 5
Output:
15
/ \
10 20
/ \
5 30
Solución:
La siguiente es una solución de 3 pasos para convertir un árbol binario en un árbol de búsqueda binario.
- Cree una array temporal arr[] que almacene el recorrido en orden del árbol. Este paso toma tiempo O(n).
- Ordene la array temporal arr[]. La complejidad temporal de este paso depende del algoritmo de clasificación. En la siguiente implementación, se utiliza Quick Sort, que lleva (n^2) tiempo. Esto se puede hacer en tiempo O (nLogn) utilizando Heap Sort o Merge Sort.
- De nuevo, haga un recorrido en orden del árbol y copie los elementos de la array en los Nodes del árbol uno por uno. Este paso toma tiempo O(n).
A continuación se muestra la implementación del enfoque anterior. La función principal para convertir se resalta en el siguiente código.
Implementación:
C++
/* A program to convert Binary Tree to Binary Search Tree */
#include <iostream>
using namespace std;
/* A binary tree node structure */
struct node {
int data;
struct node* left;
struct node* right;
};
/* A helper function that stores inorder
traversal of a tree rooted with node */
void storeInorder(struct node* node, int inorder[], int* index_ptr)
{
// Base Case
if (node == NULL)
return;
/* first store the left subtree */
storeInorder(node->left, inorder, index_ptr);
/* Copy the root's data */
inorder[*index_ptr] = node->data;
(*index_ptr)++; // increase index for next entry
/* finally store the right subtree */
storeInorder(node->right, inorder, index_ptr);
}
/* A helper function to count nodes in a Binary Tree */
int countNodes(struct node* root)
{
if (root == NULL)
return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
// Following function is needed for library function qsort()
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
/* A helper function that copies contents of arr[]
to Binary Tree. This function basically does Inorder
traversal of Binary Tree and one by one copy arr[]
elements to Binary Tree nodes */
void arrayToBST(int* arr, struct node* root, int* index_ptr)
{
// Base Case
if (root == NULL)
return;
/* first update the left subtree */
arrayToBST(arr, root->left, index_ptr);
/* Now update root's data and increment index */
root->data = arr[*index_ptr];
(*index_ptr)++;
/* finally update the right subtree */
arrayToBST(arr, root->right, index_ptr);
}
// This function converts a given Binary Tree to BST
void binaryTreeToBST(struct node* root)
{
// base case: tree is empty
if (root == NULL)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
int n = countNodes(root);
// Create a temp array arr[] and store inorder
// traversal of tree in arr[]
int* arr = new int[n];
int i = 0;
storeInorder(root, arr, &i);
// Sort the array using library function for quick sort
qsort(arr, n, sizeof(arr[0]), compare);
// Copy array elements back to Binary Tree
i = 0;
arrayToBST(arr, root, &i);
// delete dynamically allocated memory to
// avoid memory leak
delete[] arr;
}
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node* temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Utility function to print inorder
traversal of Binary Tree */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout <<" "<< node->data;
/* now recur on right child */
printInorder(node->right);
}
/* Driver function to test above functions */
int main()
{
struct node* root = NULL;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
root = newNode(10);
root->left = newNode(30);
root->right = newNode(15);
root->left->left = newNode(20);
root->right->right = newNode(5);
// convert Binary Tree to BST
binaryTreeToBST(root);
cout <<"Following is Inorder Traversal of the converted BST:" << endl ;
printInorder(root);
return 0;
}
// This code is contributed by shivanisinghss2110
C
/* A program to convert Binary Tree to Binary Search Tree */
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node structure */
struct node {
int data;
struct node* left;
struct node* right;
};
/* A helper function that stores inorder traversal of a tree rooted
with node */
void storeInorder(struct node* node, int inorder[], int* index_ptr)
{
// Base Case
if (node == NULL)
return;
/* first store the left subtree */
storeInorder(node->left, inorder, index_ptr);
/* Copy the root's data */
inorder[*index_ptr] = node->data;
(*index_ptr)++; // increase index for next entry
/* finally store the right subtree */
storeInorder(node->right, inorder, index_ptr);
}
/* A helper function to count nodes in a Binary Tree */
int countNodes(struct node* root)
{
if (root == NULL)
return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
// Following function is needed for library function qsort()
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
/* A helper function that copies contents of arr[] to Binary Tree.
This function basically does Inorder traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
void arrayToBST(int* arr, struct node* root, int* index_ptr)
{
// Base Case
if (root == NULL)
return;
/* first update the left subtree */
arrayToBST(arr, root->left, index_ptr);
/* Now update root's data and increment index */
root->data = arr[*index_ptr];
(*index_ptr)++;
/* finally update the right subtree */
arrayToBST(arr, root->right, index_ptr);
}
// This function converts a given Binary Tree to BST
void binaryTreeToBST(struct node* root)
{
// base case: tree is empty
if (root == NULL)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
int n = countNodes(root);
// Create a temp array arr[] and store inorder traversal of tree in arr[]
int* arr = new int[n];
int i = 0;
storeInorder(root, arr, &i);
// Sort the array using library function for quick sort
qsort(arr, n, sizeof(arr[0]), compare);
// Copy array elements back to Binary Tree
i = 0;
arrayToBST(arr, root, &i);
// delete dynamically allocated memory to avoid memory leak
delete[] arr;
}
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node* temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Utility function to print inorder traversal of Binary Tree */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Driver function to test above functions */
int main()
{
struct node* root = NULL;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
root = newNode(10);
root->left = newNode(30);
root->right = newNode(15);
root->left->left = newNode(20);
root->right->right = newNode(5);
// convert Binary Tree to BST
binaryTreeToBST(root);
printf("Following is Inorder Traversal of the converted BST: \n");
printInorder(root);
return 0;
}
Java
/* A program to convert Binary Tree to Binary Search Tree */
import java.util.*;
public class GFG{
/* A binary tree node structure */
static class Node {
int data;
Node left;
Node right;
};
// index pointer to pointer to the array index
static int index;
/* A helper function that stores inorder traversal of a tree rooted
with node */
static void storeInorder(Node node, int inorder[])
{
// Base Case
if (node == null)
return;
/* first store the left subtree */
storeInorder(node.left, inorder);
/* Copy the root's data */
inorder[index] = node.data;
index++; // increase index for next entry
/* finally store the right subtree */
storeInorder(node.right, inorder);
}
/* A helper function to count nodes in a Binary Tree */
static int countNodes(Node root)
{
if (root == null)
return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
/* A helper function that copies contents of arr[] to Binary Tree.
This function basically does Inorder traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
static void arrayToBST(int[] arr, Node root)
{
// Base Case
if (root == null)
return;
/* first update the left subtree */
arrayToBST(arr, root.left);
/* Now update root's data and increment index */
root.data = arr[index];
index++;
/* finally update the right subtree */
arrayToBST(arr, root.right);
}
// This function converts a given Binary Tree to BST
static void binaryTreeToBST(Node root)
{
// base case: tree is empty
if (root == null)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
int n = countNodes(root);
// Create a temp array arr[] and store inorder traversal of tree in arr[]
int arr[] = new int[n];
storeInorder(root, arr);
// Sort the array using library function for quick sort
Arrays.sort(arr);
// Copy array elements back to Binary Tree
index = 0;
arrayToBST(arr, root);
}
/* Utility function to create a new Binary Tree node */
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
/* Utility function to print inorder traversal of Binary Tree */
static void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
System.out.print(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
/* Driver function to test above functions */
public static void main(String args[])
{
Node root = null;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
root = newNode(10);
root.left = newNode(30);
root.right = newNode(15);
root.left.left = newNode(20);
root.right.right = newNode(5);
// convert Binary Tree to BST
binaryTreeToBST(root);
System.out.println("Following is Inorder Traversal of the converted BST: ");
printInorder(root);
}
}
// This code is contributed by adityapande88.
Python3
# Program to convert binary tree to BST
# A binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Helper function to store the inorder traversal of a tree
def storeInorder(root, inorder):
# Base Case
if root is None:
return
# First store the left subtree
storeInorder(root.left, inorder)
# Copy the root's data
inorder.append(root.data)
# Finally store the right subtree
storeInorder(root.right, inorder)
# A helper function to count nodes in a binary tree
def countNodes(root):
if root is None:
return 0
return countNodes(root.left) + countNodes(root.right) + 1
# Helper function that copies contents of sorted array
# to Binary tree
def arrayToBST(arr, root):
# Base Case
if root is None:
return
# First update the left subtree
arrayToBST(arr, root.left)
# now update root's data delete the value from array
root.data = arr[0]
arr.pop(0)
# Finally update the right subtree
arrayToBST(arr, root.right)
# This function converts a given binary tree to BST
def binaryTreeToBST(root):
# Base Case: Tree is empty
if root is None:
return
# Count the number of nodes in Binary Tree so that
# we know the size of temporary array to be created
n = countNodes(root)
# Create the temp array and store the inorder traversal
# of tree
arr = []
storeInorder(root, arr)
# Sort the array
arr.sort()
# copy array elements back to binary tree
arrayToBST(arr, root)
# Print the inorder traversal of the tree
def printInorder(root):
if root is None:
return
printInorder(root.left)
print (root.data,end=" ")
printInorder(root.right)
# Driver program to test above function
root = Node(10)
root.left = Node(30)
root.right = Node(15)
root.left.left = Node(20)
root.right.right = Node(5)
# Convert binary tree to BST
binaryTreeToBST(root)
print ("Following is the inorder traversal of the converted BST")
printInorder(root)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
public class Node
{
public int data;
public Node left;
public Node right;
}
public class GFG{
// index pointer to pointer to the array index
static int index;
/* A helper function that stores inorder traversal of a tree rooted
with node */
static void storeInorder(Node node, int[] inorder)
{
// Base Case
if (node == null)
return;
/* first store the left subtree */
storeInorder(node.left, inorder);
/* Copy the root's data */
inorder[index] = node.data;
index++; // increase index for next entry
/* finally store the right subtree */
storeInorder(node.right, inorder);
}
/* A helper function to count nodes in a Binary Tree */
static int countNodes(Node root)
{
if (root == null)
return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
/* A helper function that copies contents of arr[] to Binary Tree.
This function basically does Inorder traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
static void arrayToBST(int[] arr, Node root)
{
// Base Case
if (root == null)
return;
/* first update the left subtree */
arrayToBST(arr, root.left);
/* Now update root's data and increment index */
root.data = arr[index];
index++;
/* finally update the right subtree */
arrayToBST(arr, root.right);
}
// This function converts a given Binary Tree to BST
static void binaryTreeToBST(Node root)
{
// base case: tree is empty
if (root == null)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
int n = countNodes(root);
// Create a temp array arr[] and store inorder traversal of tree in arr[]
int[] arr = new int[n];
storeInorder(root, arr);
// Sort the array using library function for quick sort
Array.Sort(arr);
// Copy array elements back to Binary Tree
index = 0;
arrayToBST(arr, root);
}
/* Utility function to create a new Binary Tree node */
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
/* Utility function to print inorder traversal of Binary Tree */
static void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
Console.Write(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
/* Driver function to test above functions */
static public void Main (){
Node root = null;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
root = newNode(10);
root.left = newNode(30);
root.right = newNode(15);
root.left.left = newNode(20);
root.right.right = newNode(5);
// convert Binary Tree to BST
binaryTreeToBST(root);
Console.WriteLine("Following is Inorder Traversal of the converted BST: ");
printInorder(root);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
/* A program to convert Binary Tree
to Binary Search Tree */
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// index pointer to pointer to the array index
let index = 0;
/* Utility function to create a new Binary Tree node */
function newNode(data)
{
let temp = new Node(data);
return temp;
}
/* Utility function to print inorder
traversal of Binary Tree */
function printInorder(node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
document.write(node.data + " ");
/* now recur on right child */
printInorder(node.right);
}
/* A helper function that copies
contents of arr[] to Binary Tree.
This function basically does Inorder
traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
function arrayToBST(arr, root)
{
// Base Case
if (root == null)
return;
/* first update the left subtree */
arrayToBST(arr, root.left);
/* Now update root's data and increment index */
root.data = arr[index];
index++;
/* finally update the right subtree */
arrayToBST(arr, root.right);
}
/* A helper function that stores inorder
traversal of a tree rooted with node */
function storeInorder(node, inorder)
{
// Base Case
if (node == null)
return inorder;
/* first store the left subtree */
storeInorder(node.left, inorder);
/* Copy the root's data */
inorder[index] = node.data;
index++; // increase index for next entry
/* finally store the right subtree */
storeInorder(node.right, inorder);
}
/* A helper function to count nodes in a Binary Tree */
function countNodes(root)
{
if (root == null)
return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
// This function converts a given Binary Tree to BST
function binaryTreeToBST(root)
{
// base case: tree is empty
if (root == null)
return;
/* Count the number of nodes in Binary Tree so that
we know the size of temporary array to be created */
let n = countNodes(root);
// Create a temp array arr[] and store
// inorder traversal of tree in arr[]
let arr = new Array(n);
arr.fill(0);
storeInorder(root, arr);
// Sort the array using library function for quick sort
arr.sort(function(a, b){return a - b});
// Copy array elements back to Binary Tree
index = 0;
arrayToBST(arr, root);
}
let root = null;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
root = newNode(10);
root.left = newNode(30);
root.right = newNode(15);
root.left.left = newNode(20);
root.right.right = newNode(5);
// convert Binary Tree to BST
binaryTreeToBST(root);
document.write(
"Following is Inorder Traversal of the converted BST: "+
"</br>");
printInorder(root);
</script>
Producción
Following is the inorder traversal of the converted BST 5 10 15 20 30
Análisis de Complejidad:
- Complejidad de tiempo: O (nlogn). Esta es la complejidad del algoritmo de clasificación que estamos usando después del primer recorrido en orden, el resto de las operaciones se realizan en tiempo lineal.
- Espacio Auxiliar: O(n). Uso de la estructura de datos ‘array’ para almacenar el recorrido en orden.
Cubriremos otro método para este problema que convierte el árbol usando O (altura del árbol) espacio adicional.
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