Conversión de árbol binario a árbol de búsqueda binario

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.

  1. Cree una array temporal arr[] que almacene el recorrido en orden del árbol. Este paso toma tiempo O(n).
  2. 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.
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *