Construya el BST (árbol de búsqueda binaria) a partir de su recorrido de orden de nivel dado.
Ejemplos:
Input : arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}
Output : BST:
7
/ \
4 12
/ \ /
3 6 8
/ / \
1 5 10
La idea es usar la recursividad: –
Sabemos que el primer elemento siempre será la raíz del árbol y el segundo elemento será el hijo izquierdo y el tercer elemento será el hijo derecho (si cae en el rango), y así sucesivamente para todos los elementos restantes.
- Primero elija el primer elemento de la array y conviértalo en raíz.
- Elija el segundo elemento, si su valor es más pequeño que el valor del Node raíz, hágalo hijo izquierdo,
- De lo contrario, hazlo bien, niño
- Ahora llame recursivamente al paso (2) y al paso (3) para hacer un BST desde su nivel Order Traversal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to construct a BST
// from its level order traversal
#include <bits/stdc++.h>
using namespace std;
// node of a BST
struct Node
{
int data;
Node *left, *right;
};
// function to get a new node
Node* getNode(int data)
{
// Allocate memory
Node *newNode =
(Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// function to construct a BST from
// its level order traversal
Node *LevelOrder(Node *root , int data)
{
if(root==NULL){
root = getNode(data);
return root;
}
if(data <= root->data)
root->left = LevelOrder(root->left, data);
else
root->right = LevelOrder(root->right, data);
return root;
}
Node* constructBst(int arr[], int n)
{
if(n==0)return NULL;
Node *root =NULL;
for(int i=0;i<n;i++)
root = LevelOrder(root , arr[i]);
return root;
}
// function to print the inorder traversal
void inorderTraversal(Node* root)
{
if (!root)
return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
// Driver program to test above
int main()
{
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = sizeof(arr) / sizeof(arr[0]);
Node *root = constructBst(arr, n);
cout << "Inorder Traversal: ";
inorderTraversal(root);
return 0;
}
Java
// Java implementation to construct a BST
// from its level order traversal
class GFG
{
// node of a BST
static class Node
{
int data;
Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// Allocate memory
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// function to construct a BST from
// its level order traversal
static Node LevelOrder(Node root , int data)
{
if(root == null)
{
root = getNode(data);
return root;
}
if(data <= root.data)
root.left = LevelOrder(root.left, data);
else
root.right = LevelOrder(root.right, data);
return root;
}
static Node constructBst(int arr[], int n)
{
if(n == 0)return null;
Node root = null;
for(int i = 0; i < n; i++)
root = LevelOrder(root , arr[i]);
return root;
}
// function to print the inorder traversal
static void inorderTraversal(Node root)
{
if (root == null)
return;
inorderTraversal(root.left);
System.out.print( root.data + " ");
inorderTraversal(root.right);
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10};
int n = arr.length;
Node root = constructBst(arr, n);
System.out.print( "Inorder Traversal: ");
inorderTraversal(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python implementation to construct a BST
# from its level order traversal
import math
# node of a BST
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
# function to get a new node
def getNode( data):
# Allocate memory
newNode = Node(data)
# put in the data
newNode.data = data
newNode.left =None
newNode.right = None
return newNode
# function to construct a BST from
# its level order traversal
def LevelOrder(root , data):
if(root == None):
root = getNode(data)
return root
if(data <= root.data):
root.left = LevelOrder(root.left, data)
else:
root.right = LevelOrder(root.right, data)
return root
def constructBst(arr, n):
if(n == 0):
return None
root = None
for i in range(0, n):
root = LevelOrder(root , arr[i])
return root
# function to print the inorder traversal
def inorderTraversal( root):
if (root == None):
return None
inorderTraversal(root.left)
print(root.data,end = " ")
inorderTraversal(root.right)
# Driver program
if __name__=='__main__':
arr = [7, 4, 12, 3, 6, 8, 1, 5, 10]
n = len(arr)
root = constructBst(arr, n)
print("Inorder Traversal: ", end = "")
root = inorderTraversal(root)
# This code is contributed by Srathore
C#
// C# implementation to construct a BST
// from its level order traversal
using System;
class GFG
{
// node of a BST
public class Node
{
public int data;
public Node left, right;
};
// function to get a new node
static Node getNode(int data)
{
// Allocate memory
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// function to construct a BST from
// its level order traversal
static Node LevelOrder(Node root,
int data)
{
if(root == null)
{
root = getNode(data);
return root;
}
if(data <= root.data)
root.left = LevelOrder(root.left, data);
else
root.right = LevelOrder(root.right, data);
return root;
}
static Node constructBst(int []arr, int n)
{
if(n == 0) return null;
Node root = null;
for(int i = 0; i < n; i++)
root = LevelOrder(root, arr[i]);
return root;
}
// function to print the inorder traversal
static void inorderTraversal(Node root)
{
if (root == null)
return;
inorderTraversal(root.left);
Console.Write( root.data + " ");
inorderTraversal(root.right);
}
// Driver code
public static void Main(String []args)
{
int []arr = {7, 4, 12, 3,
6, 8, 1, 5, 10};
int n = arr.Length;
Node root = constructBst(arr, n);
Console.Write("Inorder Traversal: ");
inorderTraversal(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to construct a BST
// from its level order traversal
// node of a BST
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
// function to get a new node
function getNode(data) {
// Allocate memory
var newNode = new Node();
// put in the data
newNode.data = data;
newNode.left = newNode.right = null;
return newNode;
}
// function to construct a BST from
// its level order traversal
function LevelOrder(root, data) {
if (root == null) {
root = getNode(data);
return root;
}
if (data <= root.data)
root.left = LevelOrder(root.left, data);
else
root.right = LevelOrder(root.right, data);
return root;
}
function constructBst(arr, n) {
if (n == 0) return null;
var root = null;
for (var i = 0; i < n; i++)
root = LevelOrder(root, arr[i]);
return root;
}
// function to print the inorder traversal
function inorderTraversal(root) {
if (root == null) return;
inorderTraversal(root.left);
document.write(root.data + " ");
inorderTraversal(root.right);
}
// Driver code
var arr = [7, 4, 12, 3, 6, 8, 1, 5, 10];
var n = arr.length;
var root = constructBst(arr, n);
document.write("Inorder Traversal: ");
inorderTraversal(root);
</script>
Producción
Inorder Traversal: 1 3 4 5 6 7 8 10 12
Complejidad de tiempo: O(n 2 )
Complejidad de espacio: O(n)
Esto se debe a que el programa anterior es como si estuviéramos insertando n Nodes en un bst que toma tiempo O (n 2 ) en el peor de los casos.
Este artículo es una contribución de Nishant Balayan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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