Dado el recorrido en orden previo de un árbol de búsqueda binario, construya el BST.
Por ejemplo , si el recorrido dado es {10, 5, 1, 7, 40, 50}, entonces la salida debería ser la raíz del siguiente árbol.
10 / \ 5 40 / \ \ 1 7 50
Método 1 ( O(n 2 ) complejidad de tiempo ) :
El primer elemento del recorrido previo al pedido siempre es root. Primero construimos la raíz. Luego encontramos el índice del primer elemento que es mayor que la raíz. Sea el índice ‘i’. Los valores entre raíz e ‘i’ serán parte del subárbol izquierdo, y los valores entre ‘i’ (inclusive) y ‘n-1’ serán parte del subárbol derecho. Divida el pre[] dado en el índice «i» y recurra a los subárboles izquierdo y derecho.
Por ejemplo , en {10, 5, 1, 7, 40, 50}, 10 es el primer elemento, por lo que lo hacemos raíz. Ahora buscamos el primer elemento mayor que 10, encontramos 40. Entonces sabemos que la estructura de BST es la siguiente.
10
/ \
/ \
{5, 1, 7} {40, 50}
Seguimos recursivamente los pasos anteriores para los subarreglos {5, 1, 7} y {40, 50}, y obtenemos el árbol completo.
C++
/* A O(n^2) program for construction of BST from preorder
* traversal */
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
int data;
node* left;
node* right;
};
// A utility function to create a node
node* newNode(int data)
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
node* constructTreeUtil(int pre[], int* preIndex, int low,
int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;
// The first node in preorder traversal is root. So take
// the node at preIndex from pre[] and make it root, and
// increment preIndex
node* root = newNode(pre[*preIndex]);
*preIndex = *preIndex + 1;
// If the current subarray has only one element, no need
// to recur
if (low == high)
return root;
// Search for the first element greater than root
int i;
for (i = low; i <= high; ++i)
if (pre[i] > root->data)
break;
// Use the index of element found in preorder to divide
// preorder array in two parts. Left subtree and right
// subtree
root->left = constructTreeUtil(pre, preIndex, *preIndex,
i - 1, size);
root->right
= constructTreeUtil(pre, preIndex, i, high, size);
return root;
}
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
node* constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, &preIndex, 0, size - 1,
size);
}
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
// Driver code
int main()
{
int pre[] = { 10, 5, 1, 7, 40, 50 };
int size = sizeof(pre) / sizeof(pre[0]);
node* root = constructTree(pre, size);
cout << "Inorder traversal of the constructed tree: \n";
printInorder(root);
return 0;
}
// This code is contributed by rathbhupendra
C
/* A O(n^2) program for construction of BST from preorder
* traversal */
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
// A utility function to create a node
struct node* newNode(int data)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int* preIndex,
int low, int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;
// The first node in preorder traversal is root. So take
// the node at preIndex from pre[] and make it root, and
// increment preIndex
struct node* root = newNode(pre[*preIndex]);
*preIndex = *preIndex + 1;
// If the current subarray has only one element, no need
// to recur
if (low == high)
return root;
// Search for the first element greater than root
int i;
for (i = low; i <= high; ++i)
if (pre[i] > root->data)
break;
// Use the index of element found in preorder to divide
// preorder array in two parts. Left subtree and right
// subtree
root->left = constructTreeUtil(pre, preIndex, *preIndex,
i - 1, size);
root->right
= constructTreeUtil(pre, preIndex, i, high, size);
return root;
}
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, &preIndex, 0, size - 1,
size);
}
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
// Driver code
int main()
{
int pre[] = { 10, 5, 1, 7, 40, 50 };
int size = sizeof(pre) / sizeof(pre[0]);
struct node* root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
return 0;
}
Java
// Java program to construct BST from given preorder
// traversal
// A binary tree node
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class Index {
int index = 0;
}
class BinaryTree {
Index index = new Index();
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
Node constructTreeUtil(int pre[], Index preIndex,
int low, int high, int size)
{
// Base case
if (preIndex.index >= size || low > high) {
return null;
}
// The first node in preorder traversal is root. So
// take the node at preIndex from pre[] and make it
// root, and increment preIndex
Node root = new Node(pre[preIndex.index]);
preIndex.index = preIndex.index + 1;
// If the current subarray has only one element, no
// need to recur
if (low == high) {
return root;
}
// Search for the first element greater than root
int i;
for (i = low; i <= high; ++i) {
if (pre[i] > root.data) {
break;
}
}
// Use the index of element found in preorder to
// divide preorder array in two parts. Left subtree
// and right subtree
root.left = constructTreeUtil(
pre, preIndex, preIndex.index, i - 1, size);
root.right = constructTreeUtil(pre, preIndex, i,
high, size);
return root;
}
// The main function to construct BST from given
// preorder traversal. This function mainly uses
// constructTreeUtil()
Node constructTree(int pre[], int size)
{
return constructTreeUtil(pre, index, 0, size - 1,
size);
}
// A utility function to print inorder traversal of a
// Binary Tree
void printInorder(Node node)
{
if (node == null) {
return;
}
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
int pre[] = new int[] { 10, 5, 1, 7, 40, 50 };
int size = pre.length;
Node root = tree.constructTree(pre, size);
System.out.println(
"Inorder traversal of the constructed tree is ");
tree.printInorder(root);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# A O(n^2) Python3 program for
# construction of BST from preorder traversal
# A binary tree node
class Node():
# A constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# constructTreeUtil.preIndex is a static variable of
# function constructTreeUtil
# Function to get the value of static variable
# constructTreeUtil.preIndex
def getPreIndex():
return constructTreeUtil.preIndex
# Function to increment the value of static variable
# constructTreeUtil.preIndex
def incrementPreIndex():
constructTreeUtil.preIndex += 1
# A recurseive function to construct Full from pre[].
# preIndex is used to keep track of index in pre[[].
def constructTreeUtil(pre, low, high):
# Base Case
if(low > high):
return None
# The first node in preorder traversal is root. So take
# the node at preIndex from pre[] and make it root,
# and increment preIndex
root = Node(pre[getPreIndex()])
incrementPreIndex()
# If the current subarray has onlye one element,
# no need to recur
if low == high:
return root
r_root = -1
# Search for the first element greater than root
for i in range(low, high+1):
if (pre[i] > root.data):
r_root = i
break
# If no elements are greater than the current root,
# all elements are left children
# so assign root appropriately
if r_root == -1:
r_root = getPreIndex() + (high - low)
# Use the index of element found in preorder to divide
# preorder array in two parts. Left subtree and right
# subtree
root.left = constructTreeUtil(pre, getPreIndex(), r_root-1)
root.right = constructTreeUtil(pre, r_root, high)
return root
# The main function to construct BST from given preorder
# traversal. This function mailny uses constructTreeUtil()
def constructTree(pre):
size = len(pre)
constructTreeUtil.preIndex = 0
return constructTreeUtil(pre, 0, size-1)
def printInorder(root):
if root is None:
return
printInorder(root.left)
print (root.data,end=' ')
printInorder(root.right)
# Driver code
pre = [10, 5, 1, 7, 40, 50]
root = constructTree(pre)
print ("Inorder traversal of the constructed tree:")
printInorder(root)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007) and Rhys Compton
C#
using System;
// C# program to construct BST from given preorder traversal
// A binary tree node
public class Node {
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class Index {
public int index = 0;
}
public class BinaryTree {
public Index index = new Index();
// A recursive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[].
public virtual Node constructTreeUtil(int[] pre,
Index preIndex,
int low, int high,
int size)
{
// Base case
if (preIndex.index >= size || low > high) {
return null;
}
// The first node in preorder traversal is root. So
// take the node at preIndex from pre[] and make it
// root, and increment preIndex
Node root = new Node(pre[preIndex.index]);
preIndex.index = preIndex.index + 1;
// If the current subarray has only one element, no
// need to recur
if (low == high) {
return root;
}
// Search for the first element greater than root
int i;
for (i = low; i <= high; ++i) {
if (pre[i] > root.data) {
break;
}
}
// Use the index of element found in preorder to
// divide preorder array in two parts. Left subtree
// and right subtree
root.left = constructTreeUtil(
pre, preIndex, preIndex.index, i - 1, size);
root.right = constructTreeUtil(pre, preIndex, i,
high, size);
return root;
}
// The main function to construct BST from given
// preorder traversal. This function mainly uses
// constructTreeUtil()
public virtual Node constructTree(int[] pre, int size)
{
return constructTreeUtil(pre, index, 0, size - 1,
size);
}
// A utility function to print inorder traversal of a
// Binary Tree
public virtual void printInorder(Node node)
{
if (node == null) {
return;
}
printInorder(node.left);
Console.Write(node.data + " ");
printInorder(node.right);
}
// Driver code
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
int[] pre = new int[] { 10, 5, 1, 7, 40, 50 };
int size = pre.Length;
Node root = tree.constructTree(pre, size);
Console.WriteLine(
"Inorder traversal of the constructed tree is ");
tree.printInorder(root);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// A O(n^2) Python3 program for
// construction of BST from preorder traversal
// A binary tree node
class Node{
// A constructor to create a new node
constructor(data){
this.data = data
this.left = null
this.right = null
}
}
// constructTreeUtil.preIndex is a static variable of
// function constructTreeUtil
// Function to get the value of static variable
// constructTreeUtil.preIndex
function getPreIndex(){
return constructTreeUtil.preIndex
}
// Function to increment the value of static variable
// constructTreeUtil.preIndex
function incrementPreIndex(){
constructTreeUtil.preIndex += 1
}
// A recurseive function to construct Full from pre[].
// preIndex is used to keep track of index in pre[[].
function constructTreeUtil(pre, low, high){
// Base Case
if(low > high)
return null
// The first node in preorder traversal is root. So take
// the node at preIndex from pre[] and make it root,
// and increment preIndex
let root = new Node(pre[getPreIndex()])
incrementPreIndex()
// If the current subarray has onlye one element,
// no need to recur
if(low == high)
return root
let r_root = -1
// Search for the first element greater than root
for(let i=low;i<high+1;i++){
if (pre[i] > root.data){
r_root = i
break
}
}
// If no elements are greater than the current root,
// all elements are left children
// so assign root appropriately
if(r_root == -1)
r_root = getPreIndex() + (high - low)
// Use the index of element found in preorder to divide
// preorder array in two parts. Left subtree and right
// subtree
root.left = constructTreeUtil(pre, getPreIndex(), r_root-1)
root.right = constructTreeUtil(pre, r_root, high)
return root
}
// The main function to construct BST from given preorder
// traversal. This function mailny uses constructTreeUtil()
function constructTree(pre){
let size = pre.length
constructTreeUtil.preIndex = 0
return constructTreeUtil(pre, 0, size-1)
}
function printInorder(root){
if(root == null)
return
printInorder(root.left)
document.write(root.data,' ')
printInorder(root.right)
}
// Driver code
let pre = [10, 5, 1, 7, 40, 50]
let root = constructTree(pre)
document.write("Inorder traversal of the constructed tree:","</br>")
printInorder(root)
// This code is contributed by shinjanpatra
</script>
Producción
Inorder traversal of the constructed tree: 1 5 7 10 40 50
Complejidad temporal: O(n 2 )
Método 2 (complejidad de tiempo O(n)):
La idea utilizada aquí está inspirada en el método 3 de esta publicación. El truco es establecer un rango {min .. max} para cada Node. Inicialice el rango como {INT_MIN .. INT_MAX}. El primer Node definitivamente estará dentro del rango, así que cree un Node raíz. Para construir el subárbol izquierdo, establezca el rango como {INT_MIN…raíz->datos}. Si un valor está en el rango {INT_MIN .. root->data}, los valores son parte del subárbol izquierdo. Para construir el subárbol derecho, establezca el rango como {root->data..max .. INT_MAX}.
A continuación se muestra la implementación de la idea anterior:
C++
/* A O(n) program for construction
of BST from preorder traversal */
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
int data;
node* left;
node* right;
};
// A utility function to create a node
node* newNode(int data)
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct
// BST from pre[]. preIndex is used
// to keep track of index in pre[].
node* constructTreeUtil(int pre[], int* preIndex, int key,
int min, int max, int size)
{
// Base case
if (*preIndex >= size)
return NULL;
node* root = NULL;
// If current element of pre[] is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this
// subtree and increment *preIndex
root = newNode(key);
*preIndex = *preIndex + 1;
if (*preIndex < size) {
// Construct the subtree under root
// All nodes which are in range
// {min .. key} will go in left
// subtree, and first such node
// will be root of left subtree.
root->left = constructTreeUtil(pre, preIndex,
pre[*preIndex],
min, key, size);
}
if (*preIndex < size) {
// All nodes which are in range
// {key..max} will go in right
// subtree, and first such node
// will be root of right subtree.
root->right = constructTreeUtil(pre, preIndex,
pre[*preIndex],
key, max, size);
}
}
return root;
}
// The main function to construct BST
// from given preorder traversal.
// This function mainly uses constructTreeUtil()
node* constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, &preIndex, pre[0],
INT_MIN, INT_MAX, size);
}
// A utility function to print inorder
// traversal of a Binary Tree
void printInorder(node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
// Driver code
int main()
{
int pre[] = { 10, 5, 1, 7, 40, 50 };
int size = sizeof(pre) / sizeof(pre[0]);
// Function call
node* root = constructTree(pre, size);
cout << "Inorder traversal of the constructed tree: \n";
printInorder(root);
return 0;
}
// This is code is contributed by rathbhupendra
C
/* A O(n) program for construction of BST from preorder
* traversal */
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
// A utility function to create a node
struct node* newNode(int data)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct BST from pre[].
// preIndex is used to keep track of index in pre[].
struct node* constructTreeUtil(int pre[], int* preIndex,
int key, int min, int max,
int size)
{
// Base case
if (*preIndex >= size)
return NULL;
struct node* root = NULL;
// If current element of pre[] is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this subtree and
// increment *preIndex
root = newNode(key);
*preIndex = *preIndex + 1;
if (*preIndex < size) {
// Construct the subtree under root
// All nodes which are in range {min .. key}
// will go in left subtree, and first such node
// will be root of left subtree.
root->left = constructTreeUtil(pre, preIndex,
pre[*preIndex],
min, key, size);
}
if (*preIndex < size) {
// All nodes which are in range {key..max} will
// go in right subtree, and first such node will
// be root of right subtree.
root->right = constructTreeUtil(pre, preIndex,
pre[*preIndex],
key, max, size);
}
}
return root;
}
// The main function to construct BST from given preorder
// traversal. This function mainly uses constructTreeUtil()
struct node* constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, &preIndex, pre[0],
INT_MIN, INT_MAX, size);
}
// A utility function to print inorder traversal of a Binary
// Tree
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
// Driver code
int main()
{
int pre[] = { 10, 5, 1, 7, 40, 50 };
int size = sizeof(pre) / sizeof(pre[0]);
// function call
struct node* root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
return 0;
}
Java
// Java program to construct BST from given preorder
// traversal
// A binary tree node
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
class Index {
int index = 0;
}
class BinaryTree {
Index index = new Index();
// A recursive function to construct BST from pre[].
// preIndex is used to keep track of index in pre[].
Node constructTreeUtil(int pre[], Index preIndex,
int key, int min, int max,
int size)
{
// Base case
if (preIndex.index >= size) {
return null;
}
Node root = null;
// If current element of pre[] is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this
// subtree and increment *preIndex
root = new Node(key);
preIndex.index = preIndex.index + 1;
if (preIndex.index < size) {
// Construct the subtree under root
// All nodes which are in range {min .. key}
// will go in left subtree, and first such
// node will be root of left subtree.
root.left = constructTreeUtil(
pre, preIndex, pre[preIndex.index], min,
key, size);
}
if (preIndex.index < size) {
// All nodes which are in range {key..max}
// will go in right subtree, and first such
// node will be root of right subtree.
root.right = constructTreeUtil(
pre, preIndex, pre[preIndex.index], key,
max, size);
}
}
return root;
}
// The main function to construct BST from given
// preorder traversal. This function mainly uses
// constructTreeUtil()
Node constructTree(int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil(pre, index, pre[0],
Integer.MIN_VALUE,
Integer.MAX_VALUE, size);
}
// A utility function to print inorder traversal of a
// Binary Tree
void printInorder(Node node)
{
if (node == null) {
return;
}
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
int pre[] = new int[] { 10, 5, 1, 7, 40, 50 };
int size = pre.length;
// Function call
Node root = tree.constructTree(pre, size);
System.out.println(
"Inorder traversal of the constructed tree is ");
tree.printInorder(root);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# A O(n) program for construction of BST from preorder traversal
INT_MIN = -float("inf")
INT_MAX = float("inf")
# A Binary tree node
class Node:
# Constructor to created a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Methods to get and set the value of static variable
# constructTreeUtil.preIndex for function construcTreeUtil()
def getPreIndex():
return constructTreeUtil.preIndex
def incrementPreIndex():
constructTreeUtil.preIndex += 1
# A recursive function to construct BST from pre[].
# preIndex is used to keep track of index in pre[]
def constructTreeUtil(pre, key, mini, maxi, size):
# Base Case
if(getPreIndex() >= size):
return None
root = None
# If current element of pre[] is in range, then
# only it is part of current subtree
if(key > mini and key < maxi):
# Allocate memory for root of this subtree
# and increment constructTreeUtil.preIndex
root = Node(key)
incrementPreIndex()
if(getPreIndex() < size):
# Construct the subtree under root
# All nodes which are in range {min.. key} will
# go in left subtree, and first such node will
# be root of left subtree
root.left = constructTreeUtil(pre,
pre[getPreIndex()],
mini, key, size)
if(getPreIndex() < size):
# All nodes which are in range{key..max} will
# go to right subtree, and first such node will
# be root of right subtree
root.right = constructTreeUtil(pre,
pre[getPreIndex()],
key, maxi, size)
return root
# This is the main function to construct BST from given
# preorder traversal. This function mainly uses
# constructTreeUtil()
def constructTree(pre):
constructTreeUtil.preIndex = 0
size = len(pre)
return constructTreeUtil(pre, pre[0], INT_MIN, INT_MAX, size)
# A utility function to print inorder traversal of Binary Tree
def printInorder(node):
if node is None:
return
printInorder(node.left)
print (node.data,end=" ")
printInorder(node.right)
# Driver code
pre = [10, 5, 1, 7, 40, 50]
# Function call
root = constructTree(pre)
print ("Inorder traversal of the constructed tree: ")
printInorder(root)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to construct BST from given preorder traversal
using System;
// A binary tree node
public class Node {
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class Index {
public int index = 0;
}
public class BinaryTree {
public Index index = new Index();
// A recursive function to construct BST from pre[].
// preIndex is used to keep track of index in pre[].
public virtual Node constructTreeUtil(int[] pre,
Index preIndex,
int key, int min,
int max, int size)
{
// Base case
if (preIndex.index >= size) {
return null;
}
Node root = null;
// If current element of pre[] is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this subtree
// and increment *preIndex
root = new Node(key);
preIndex.index = preIndex.index + 1;
if (preIndex.index < size) {
// Construct the subtree under root
// All nodes which are in range
// {min .. key} will go in left
// subtree, and first such node will
// be root of left subtree.
root.left = constructTreeUtil(
pre, preIndex, pre[preIndex.index], min,
key, size);
}
if (preIndex.index < size) {
// All nodes which are in range
// {key..max} will go in right
// subtree, and first such node
// will be root of right subtree.
root.right = constructTreeUtil(
pre, preIndex, pre[preIndex.index], key,
max, size);
}
}
return root;
}
// The main function to construct BST from given
// preorder traversal. This function mainly uses
// constructTreeUtil()
public virtual Node constructTree(int[] pre, int size)
{
return constructTreeUtil(pre, index, pre[0],
int.MinValue, int.MaxValue,
size);
}
// A utility function to print inorder traversal of a
// Binary Tree
public virtual void printInorder(Node node)
{
if (node == null) {
return;
}
printInorder(node.left);
Console.Write(node.data + " ");
printInorder(node.right);
}
// Driver code
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
int[] pre = new int[] { 10, 5, 1, 7, 40, 50 };
int size = pre.Length;
// Function call
Node root = tree.constructTree(pre, size);
Console.WriteLine(
"Inorder traversal of the constructed tree is ");
tree.printInorder(root);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to construct BST from given preorder
// traversal
// A binary tree node
class Node {
constructor(d) {
this.data = d;
this.left = this.right = null;
}
}
class Index {
constructor(){
this.index = 0;
}
}
index = new Index();
// A recursive function to construct BST from pre.
// preIndex is used to keep track of index in pre.
function constructTreeUtil(pre, preIndex , key , min , max , size) {
// Base case
if (preIndex.index >= size) {
return null;
}
var root = null;
// If current element of pre is in range, then
// only it is part of current subtree
if (key > min && key < max) {
// Allocate memory for root of this
// subtree and increment *preIndex
root = new Node(key);
preIndex.index = preIndex.index + 1;
if (preIndex.index < size) {
// Construct the subtree under root
// All nodes which are in range {min .. key}
// will go in left subtree, and first such
// node will be root of left subtree.
root.left = constructTreeUtil(pre, preIndex,
pre[preIndex.index], min, key, size);
}
if (preIndex.index < size)
{
// All nodes which are in range {key..max}
// will go in right subtree, and first such
// node will be root of right subtree.
root.right = constructTreeUtil(pre, preIndex,
pre[preIndex.index], key, max, size);
}
}
return root;
}
// The main function to construct BST from given
// preorder traversal. This function mainly uses
// constructTreeUtil()
function constructTree(pre , size) {
var preIndex = 0;
return constructTreeUtil(pre, index, pre[0],
Number.MIN_VALUE, Number.MAX_VALUE, size);
}
// A utility function to print inorder traversal of a
// Binary Tree
function printInorder(node) {
if (node == null) {
return;
}
printInorder(node.left);
document.write(node.data + " ");
printInorder(node.right);
}
// Driver code
var pre =[ 10, 5, 1, 7, 40, 50 ];
var size = pre.length;
// Function call
var root = constructTree(pre, size);
document.write("Inorder traversal of the constructed tree is <br/>");
printInorder(root);
// This code is contributed by Rajput-Ji
</script>
Producción
Inorder traversal of the constructed tree: 1 5 7 10 40 50
Complejidad de tiempo: O(n)
Pronto publicaremos una solución iterativa O(n) como una publicación separada.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 3 (O(n 2 ) complejidad temporal):
Simplemente hazlo usando el concepto de recursión e iterando a través de la array de los elementos dados como se muestra a continuación.
C++
// C++ Program for the same approach
#include <bits/stdc++.h>
using namespace std;
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
10
/ \
5 40
/ \ \
1 7 50 */
class Node {
public:
int data;
Node* left;
Node* right;
Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
static Node* node;
// This will create the BST
Node* createNode(Node* node, int data)
{
if (node == NULL)
node = new Node(data);
if (node->data > data)
node->left = createNode(node->left, data);
if (node->data < data)
node->right = createNode(node->right, data);
return node;
}
// A wrapper function of createNode
void create(int data)
{
node = createNode(node, data);
}
// A function to print BST in inorder
void inorderRec(Node* root)
{
if (root != NULL) {
inorderRec(root->left);
cout<<root->data<<endl;
inorderRec(root->right);
}
}
// Driver code
int main()
{
vector<int> nodeData = { 10, 5, 1, 7, 40, 50 };
for (int i = 0; i < nodeData.size(); i++) {
create(nodeData[i]);
}
inorderRec(node);
}
// This code is contributed by shinjanpatra
Java
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
10
/ \
5 40
/ \ \
1 7 50 */
class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
this.left = this.right = null;
}
}
class CreateBSTFromPreorder {
private static Node node;
// This will create the BST
public static Node createNode(Node node, int data)
{
if (node == null)
node = new Node(data);
if (node.data > data)
node.left = createNode(node.left, data);
if (node.data < data)
node.right = createNode(node.right, data);
return node;
}
// A wrapper function of createNode
public static void create(int data)
{
node = createNode(node, data);
}
// A function to print BST in inorder
public static void inorderRec(Node root)
{
if (root != null) {
inorderRec(root.left);
System.out.println(root.data);
inorderRec(root.right);
}
}
// Driver Code
public static void main(String[] args)
{
int[] nodeData = { 10, 5, 1, 7, 40, 50 };
for (int i = 0; i < nodeData.length; i++) {
create(nodeData[i]);
}
inorderRec(node);
}
}
Python3
# Construct a BST from given pre-order traversal
# for example if the given traversal is {10, 5, 1, 7, 40, 50},
# then the output should be the root of the following tree.
# 10
# / \
# 5 40
# / \ \
# 1 7 50
class Node:
data = 0
left = None
right = None
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class CreateBSTFromPreorder:
node = None
# This will create the BST
@staticmethod
def createNode(node, data):
if (node == None):
node = Node(data)
if (node.data > data):
node.left = CreateBSTFromPreorder.createNode(node.left, data)
if (node.data < data):
node.right = CreateBSTFromPreorder.createNode(node.right, data)
return node
# A wrapper function of createNode
@staticmethod
def create(data):
CreateBSTFromPreorder.node = CreateBSTFromPreorder.createNode(
CreateBSTFromPreorder.node, data)
# A function to print BST in inorder
@staticmethod
def inorderRec(root):
if (root != None):
CreateBSTFromPreorder.inorderRec(root.left)
print(root.data)
CreateBSTFromPreorder.inorderRec(root.right)
# Driver Code
@staticmethod
def main(args):
nodeData = [10, 5, 1, 7, 40, 50]
i = 0
while (i < len(nodeData)):
CreateBSTFromPreorder.create(nodeData[i])
i += 1
CreateBSTFromPreorder.inorderRec(CreateBSTFromPreorder.node)
if __name__ == "__main__":
CreateBSTFromPreorder.main([])
# This code is contributed by mukulsomukesh
C#
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50},
then the output should be the root of the following tree.
10
/ \
5 40
/ \ \
1 7 50 */
using System;
public class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
this.left = this.right = null;
}
}
public class CreateBSTFromPreorder {
private static Node node;
// This will create the BST
public static Node createNode(Node node, int data)
{
if (node == null)
node = new Node(data);
if (node.data > data)
node.left = createNode(node.left, data);
if (node.data < data)
node.right = createNode(node.right, data);
return node;
}
// A wrapper function of createNode
public static void create(int data)
{
node = createNode(node, data);
}
// A function to print BST in inorder
public static void inorderRec(Node root)
{
if (root != null) {
inorderRec(root.left);
Console.WriteLine(root.data);
inorderRec(root.right);
}
}
// Driver Code
public static void Main(String[] args)
{
int[] nodeData = { 10, 5, 1, 7, 40, 50 };
for (int i = 0; i < nodeData.Length; i++) {
create(nodeData[i]);
}
inorderRec(node);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/*Construct a BST from given pre-order traversal
for example if the given traversal is {10, 5, 1, 7, 40, 50],
then the output should be the root of the following tree.
10
/ \
5 40
/ \ \
1 7 50 */
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
var node;
// This will create the BST
function createNode(node , data) {
if (node == null)
node = new Node(data);
if (node.data > data)
node.left = createNode(node.left, data);
if (node.data < data)
node.right = createNode(node.right, data);
return node;
}
// A wrapper function of createNode
function create(data) {
node = createNode(node, data);
}
// A function to print BST in inorder
function inorderRec(root) {
if (root != null) {
inorderRec(root.left);
document.write(root.data+"<br/>");
inorderRec(root.right);
}
}
// Driver Code
var nodeData = [ 10, 5, 1, 7, 40, 50 ];
for (i = 0; i < nodeData.length; i++)
{
create(nodeData[i]);
}
inorderRec(node);
// This code is contributed by Rajput-Ji
</script>
Producción
1 5 7 10 40 50
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