Dado un vector arr no ordenado , la tarea es crear un árbol de búsqueda binario balanceado usando los elementos del arreglo.
Nota: Puede haber más de un BST balanceado. Formar cualquiera es aceptable
Ejemplos:
Entrada: arr[] = { 2, 1, 3}
Salida: 2 1 3
Explicación: El árbol formado se muestra a continuación. El recorrido previo al pedido es 2 1 3
2
/ \
1 3Entrada: arr[] = {4, 3, 1, 2}
Salida: 2 1 3 4
Explicación: El árbol formado es
2
/ \
1 3
\
4
Otra posible opción que puede proporcionar un recorrido de preorden es 3 2 1 4
Enfoque: Para resolver este problema, siga los pasos a continuación:
- En primer lugar, ordenaremos el vector usando la función de ordenación .
- Ahora, obtenga el medio del vector y conviértalo en raíz.
- Recursivamente haga lo mismo para la mitad izquierda y la mitad derecha.
- Obtenga el medio de la mitad izquierda y conviértalo en el hijo izquierdo de la raíz creada en el paso 2.
- Obtenga el medio de la mitad derecha y conviértalo en el hijo derecho de la raíz creada en el paso 2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print BST in given range
#include <bits/stdc++.h>
using namespace std;
// Node of Binary Search Tree
class Node {
public:
Node* left;
int data;
Node* right;
Node(int d)
{
data = d;
left = right = NULL;
}
};
// A function that constructs Balanced
// Binary Search Tree from a vector
Node* createBST(vector<int> v, int start,
int end)
{
sort(v.begin(), v.end());
// Base Case
if (start > end)
return NULL;
// Get the middle element and make it root
int mid = (start + end) / 2;
Node* root = new Node(v[mid]);
// Recursively construct the left subtree
// and make it left child of root
root->left = createBST(v, start, mid - 1);
// Recursively construct the right subtree
// and make it right child of root
root->right = createBST(v, mid + 1, end);
return root;
}
vector<int> preNode, vec;
// A utility function to print
// preorder traversal of BST
vector<int> preOrder(Node* node)
{
// Root Left Right
if (node == NULL) {
return vec;
}
preNode.push_back(node->data);
preOrder(node->left);
preOrder(node->right);
return preNode;
}
// Driver Code
int main()
{
vector<int> v = { 4, 3, 1, 2 };
Node* root = createBST(v, 0, v.size() - 1);
vector<int> ans = preOrder(root);
for (auto i : ans) {
cout << i << " ";
}
return 0;
}
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7
Complejidad de Tiempo: O(N * logN)
Espacio Auxiliar: O(N) para crear el árbol
Publicación traducida automáticamente
Artículo escrito por akshitsaxenaa09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA