Dado un árbol binario, conviértalo en un árbol de búsqueda binario . La conversión debe hacerse de forma que se mantenga la estructura original del Árbol Binario.
Esta solución utilizará conjuntos de C++ STL en lugar de una solución basada en arrays.
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
- Copie los elementos del árbol binario en un conjunto mientras realiza un recorrido en orden. Esto toma tiempo O (n log n). Tenga en cuenta que el conjunto en C++ STL se implementa utilizando un árbol de búsqueda binario autoequilibrado como Red Black Tree , AVL Tree , etc.
- No es necesario ordenar el conjunto, ya que los conjuntos en C++ se implementan mediante árboles de búsqueda binarios autoequilibrados, por lo que cada operación, como la inserción, la búsqueda, la eliminación, etc., requiere tiempo O (log n).
- Ahora simplemente copie los elementos del conjunto uno por uno desde el principio hasta el árbol mientras realiza un recorrido en orden del árbol. Se debe tener cuidado ya que al copiar cada elemento del conjunto desde el principio, primero lo copiamos en el árbol mientras hacemos un recorrido en orden, luego lo eliminamos del conjunto también.
Ahora, la solución anterior es más simple y más fácil de implementar que la conversión basada en array de árbol binario a árbol de búsqueda binario que se explica aquí: Conversión de árbol binario a árbol de búsqueda binario (Conjunto-1) , donde tuvimos que hacer una función por separado para ordenar los elementos de la array después de copiar los elementos del árbol en él.
Programa para convertir un árbol binario en un árbol de búsqueda binario utilizando el conjunto.
C++
/* CPP program to convert a Binary tree to BST
using sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
// function to store the nodes in set while
// doing inorder traversal.
void storeinorderInSet(Node* root, set<int>& s)
{
if (!root)
return;
// visit the left subtree first
storeinorderInSet(root->left, s);
// insertion takes order of O(logn) for sets
s.insert(root->data);
// visit the right subtree
storeinorderInSet(root->right, s);
} // Time complexity = O(nlogn)
// function to copy items of set one by one
// to the tree while doing inorder traversal
void setToBST(set<int>& s, Node* root)
{
// base condition
if (!root)
return;
// first move to the left subtree and
// update items
setToBST(s, root->left);
// iterator initially pointing to the
// beginning of set
auto it = s.begin();
// copying the item at beginning of
// set(sorted) to the tree.
root->data = *it;
// now erasing the beginning item from set.
s.erase(it);
// now move to right subtree and update items
setToBST(s, root->right);
} // T(n) = O(nlogn) time
// Converts Binary tree to BST.
void binaryTreeToBST(Node* root)
{
set<int> s;
// populating the set with the tree's
// inorder traversal data
storeinorderInSet(root, s);
// now sets are by default sorted as
// they are implemented using self-
// balancing BST
// copying items from set to the tree
// while inorder traversal which makes a BST
setToBST(s, root);
} // Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function to create a node
Node* newNode(int data)
{
// dynamically allocating memory
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function to do inorder traversal
void inorder(Node* root)
{
if (!root)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main()
{
Node* root = newNode(5);
root->left = newNode(7);
root->right = newNode(9);
root->right->left = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->right->right = newNode(11);
/* Constructing tree given in the above figure
5
/ \
7 9
/\ / \
1 6 10 11 */
// converting the above Binary tree to BST
binaryTreeToBST(root);
cout << "Inorder traversal of BST is: " << endl;
inorder(root);
return 0;
}
Java
/* Java program to convert a Binary tree to BST
using sets as containers. */
import java.util.*;
class Solution
{
static class Node
{
int data;
Node left, right;
}
// set
static Set<Integer> s = new HashSet<Integer>();
// function to store the nodes in set while
// doing inorder traversal.
static void storeinorderInSet(Node root)
{
if (root == null)
return;
// visit the left subtree first
storeinorderInSet(root.left);
// insertion takes order of O(logn) for sets
s.add(root.data);
// visit the right subtree
storeinorderInSet(root.right);
} // Time complexity = O(nlogn)
// function to copy items of set one by one
// to the tree while doing inorder traversal
static void setToBST( Node root)
{
// base condition
if (root == null)
return;
// first move to the left subtree and
// update items
setToBST( root.left);
// iterator initially pointing to the
// beginning of set
// copying the item at beginning of
// set(sorted) to the tree.
root.data = s.iterator().next();
// now erasing the beginning item from set.
s.remove(root.data);
// now move to right subtree and update items
setToBST( root.right);
} // T(n) = O(nlogn) time
// Converts Binary tree to BST.
static void binaryTreeToBST(Node root)
{
s.clear();
// populating the set with the tree's
// inorder traversal data
storeinorderInSet(root);
// now sets are by default sorted as
// they are implemented using self-
// balancing BST
// copying items from set to the tree
// while inorder traversal which makes a BST
setToBST( root);
} // Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function to create a node
static Node newNode(int data)
{
// dynamically allocating memory
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// function to do inorder traversal
static void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Driver code
public static void main(String args[])
{
Node root = newNode(5);
root.left = newNode(7);
root.right = newNode(9);
root.right.left = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(11);
/* Constructing tree given in the above figure
5
/ \
7 9
/\ / \
1 6 10 11 */
// converting the above Binary tree to BST
binaryTreeToBST(root);
System.out.println( "Inorder traversal of BST is: " );
inorder(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to convert a Binary tree
# to BST using sets as containers.
# 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
# function to store the nodes in set
# while doing inorder traversal.
def storeinorderInSet(root, s):
if (not root) :
return
# visit the left subtree first
storeinorderInSet(root.left, s)
# insertion takes order of O(logn)
# for sets
s.add(root.data)
# visit the right subtree
storeinorderInSet(root.right, s)
# Time complexity = O(nlogn)
# function to copy items of set one by one
# to the tree while doing inorder traversal
def setToBST(s, root) :
# base condition
if (not root):
return
# first move to the left subtree and
# update items
setToBST(s, root.left)
# iterator initially pointing to
# the beginning of set
it = next(iter(s))
# copying the item at beginning of
# set(sorted) to the tree.
root.data = it
# now erasing the beginning item from set.
s.remove(it)
# now move to right subtree
# and update items
setToBST(s, root.right)
# T(n) = O(nlogn) time
# Converts Binary tree to BST.
def binaryTreeToBST(root):
s = set()
# populating the set with the tree's
# inorder traversal data
storeinorderInSet(root, s)
# now sets are by default sorted as
# they are implemented using self-
# balancing BST
# copying items from set to the tree
# while inorder traversal which makes a BST
setToBST(s, root)
# Time complexity = O(nlogn),
# Auxiliary Space = O(n) for set.
# function to do inorder traversal
def inorder(root) :
if (not root) :
return
inorder(root.left)
print(root.data, end = " ")
inorder(root.right)
# Driver Code
if __name__ == '__main__':
root = newNode(5)
root.left = newNode(7)
root.right = newNode(9)
root.right.left = newNode(10)
root.left.left = newNode(1)
root.left.right = newNode(6)
root.right.right = newNode(11)
""" Constructing tree given in
the above figure
5
/ \
7 9
/\ / \
1 6 10 11 """
# converting the above Binary tree to BST
binaryTreeToBST(root)
print("Inorder traversal of BST is: ")
inorder(root)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to convert
// a Binary tree to BST
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
class Solution{
class Node
{
public int data;
public Node left,
right;
}
// set
static SortedSet<int> s =
new SortedSet<int>();
// function to store the nodes
// in set while doing inorder
// traversal.
static void storeinorderInSet(Node root)
{
if (root == null)
return;
// visit the left subtree
// first
storeinorderInSet(root.left);
// insertion takes order of
// O(logn) for sets
s.Add(root.data);
// visit the right subtree
storeinorderInSet(root.right);
}
// Time complexity = O(nlogn)
// function to copy items of
// set one by one to the tree
// while doing inorder traversal
static void setToBST(Node root)
{
// base condition
if (root == null)
return;
// first move to the left
// subtree and update items
setToBST(root.left);
// iterator initially pointing
// to the beginning of set copying
// the item at beginning of set(sorted)
// to the tree.
root.data = s.First();
// now erasing the beginning item
// from set.
s.Remove(s.First());
// now move to right subtree and
// update items
setToBST( root.right);
}
// T(n) = O(nlogn) time
// Converts Binary tree to BST.
static void binaryTreeToBST(Node root)
{
s.Clear();
// populating the set with
// the tree's inorder traversal
// data
storeinorderInSet(root);
// now sets are by default sorted
// as they are implemented using
// self-balancing BST
// copying items from set to the
// tree while inorder traversal
// which makes a BST
setToBST( root);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function to create a node
static Node newNode(int data)
{
// dynamically allocating
// memory
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// function to do inorder traversal
static void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
Console.Write(root.data + " ");
inorder(root.right);
}
// Driver code
public static void Main(string []args)
{
Node root = newNode(5);
root.left = newNode(7);
root.right = newNode(9);
root.right.left = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(11);
/* Constructing tree given in
// the above figure
5
/ \
7 9
/\ / \
1 6 10 11 */
// converting the above Binary
// tree to BST
binaryTreeToBST(root);
Console.Write("Inorder traversal of " +
"BST is: \n" );
inorder(root);
}
}
// This code is contributed by Rutvik_56
Javascript
<script>
// JavaScript program to convert
// a Binary tree to BST
class Node
{
constructor()
{
this.data = 0;
this.right = null;
this.left = null;
}
}
// set
var s = new Set();
// function to store the nodes
// in set while doing inorder
// traversal.
function storeinorderInSet(root)
{
if (root == null)
return;
// visit the left subtree
// first
storeinorderInSet(root.left);
// insertion takes order of
// O(logn) for sets
s.add(root.data);
// visit the right subtree
storeinorderInSet(root.right);
}
// Time complexity = O(nlogn)
// function to copy items of
// set one by one to the tree
// while doing inorder traversal
function setToBST(root)
{
// base condition
if (root == null)
return;
// first move to the left
// subtree and update items
setToBST(root.left);
var tmp = [...s].sort((a,b)=> a-b);
// iterator initially pointing
// to the beginning of set copying
// the item at beginning of set(sorted)
// to the tree.
root.data = tmp[0];
// now erasing the beginning item
// from set.
s.delete(tmp[0]);
// now move to right subtree and
// update items
setToBST( root.right);
}
// T(n) = O(nlogn) time
// Converts Binary tree to BST.
function binaryTreeToBST(root)
{
s = new Set();
// populating the set with
// the tree's inorder traversal
// data
storeinorderInSet(root);
// now sets are by default sorted
// as they are implemented using
// self-balancing BST
// copying items from set to the
// tree while inorder traversal
// which makes a BST
setToBST( root);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function to create a node
function newNode(data)
{
// dynamically allocating
// memory
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// function to do inorder traversal
function inorder(root)
{
if (root == null)
return;
inorder(root.left);
document.write(root.data + " ");
inorder(root.right);
}
// Driver code
var root = newNode(5);
root.left = newNode(7);
root.right = newNode(9);
root.right.left = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(11);
/* Constructing tree given in
// the above figure
5
/ \
7 9
/\ / \
1 6 10 11 */
// converting the above Binary
// tree to BST
binaryTreeToBST(root);
document.write("Inorder traversal of " +
"BST is: <br>" );
inorder(root);
</script>
Producción:
Inorder traversal of BST is: 1 5 6 7 9 10 11
Complejidad Temporal: O(n Log n)
Espacio Auxiliar: (n)
Publicación traducida automáticamente
Artículo escrito por AnishSinghWalia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA