Dada una array ‘pre[]’ que representa el recorrido de Preorder de un árbol binario especial donde cada Node tiene 0 o 2 hijos. Se da una array más ‘preLN[]’ que tiene solo dos valores posibles ‘L’ y ‘N’. El valor ‘L’ en ‘preLN[]’ indica que el Node correspondiente en Binary Tree es un Node de hoja y el valor ‘N’ indica que el Node correspondiente no es un Node de hoja. Escribe una función para construir el árbol a partir de las dos arrays dadas.
Ejemplo:
Entrada : pre[] = {10, 30, 20, 5, 15}, preLN[] = {‘N’, ‘N’, ‘L’, ‘L’, ‘L’}
Salida: Raíz del siguiente árbol10
/ \
30 15
/ \
20 5
Enfoque: El primer elemento en pre[] siempre será root. Entonces podemos averiguar fácilmente la raíz. Si el subárbol izquierdo está vacío, el subárbol derecho también debe estar vacío y la entrada preLN[] para la raíz debe ser ‘L’. Simplemente podemos crear un Node y devolverlo. Si los subárboles izquierdo y derecho no están vacíos, llame recursivamente a los subárboles izquierdo y derecho y vincule los Nodes devueltos a la raíz.
A continuación se muestra la implementación del enfoque anterior:
C++
// A program to construct Binary Tree from preorder traversal
#include<bits/stdc++.h>
// A binary tree node structure
struct node
{
int data;
struct node *left;
struct node *right;
};
// 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;
}
/* A recursive function to create a Binary Tree from given pre[]
preLN[] arrays. The function returns root of tree. index_ptr is used
to update index values in recursive calls. index must be initially
passed as 0 */
struct node *constructTreeUtil(int pre[], char preLN[], int *index_ptr, int n)
{
int index = *index_ptr; // store the current value of index in pre[]
// Base Case: All nodes are constructed
if (index == n)
return NULL;
// Allocate memory for this node and increment index for
// subsequent recursive calls
struct node *temp = newNode ( pre[index] );
(*index_ptr)++;
// If this is an internal node, construct left and
// right subtrees and link the subtrees
if (preLN[index] == 'N')
{
temp->left = constructTreeUtil(pre, preLN, index_ptr, n);
temp->right = constructTreeUtil(pre, preLN, index_ptr, n);
}
return temp;
}
// A wrapper over constructTreeUtil()
struct node *constructTree(int pre[], char preLN[], int n)
{
/* Initialize index as 0. Value of index is
used in recursion to maintain the current
index in pre[] and preLN[] arrays. */
int index = 0;
return constructTreeUtil (pre, preLN, &index, n);
}
// This function is used only for testing
void printInorder (struct node* node)
{
if (node == NULL)
return;
// First recur on left child
printInorder (node->left);
// Print the data of node
printf("%d ", node->data);
// Now recur on right child
printInorder (node->right);
}
// Driver code
int main()
{
struct node *root = NULL;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
int pre[] = {10, 30, 20, 5, 15};
char preLN[] = {'N', 'N', 'L', 'L', 'L'};
int n = sizeof(pre)/sizeof(pre[0]);
// construct the above tree
root = constructTree (pre, preLN, n);
// Test the constructed tree
printf("Inorder Traversal of the Constructed Binary Tree: \n");
printInorder (root);
return 0;
}
Java
// Java program to construct a binary tree from preorder traversal
// A Binary Tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class Index
{
int index = 0;
}
class BinaryTree
{
Node root;
Index myindex = new Index();
/* A recursive function to create a Binary Tree from given pre[]
preLN[] arrays. The function returns root of tree. index_ptr is used
to update index values in recursive calls. index must be initially
passed as 0 */
Node constructTreeUtil(int pre[], char preLN[], Index index_ptr,
int n, Node temp)
{
// store the current value of index in pre[]
int index = index_ptr.index;
// Base Case: All nodes are constructed
if (index == n)
return null;
// Allocate memory for this node and increment index for
// subsequent recursive calls
temp = new Node(pre[index]);
(index_ptr.index)++;
// If this is an internal node, construct left and right subtrees
// and link the subtrees
if (preLN[index] == 'N')
{
temp.left = constructTreeUtil(pre, preLN, index_ptr, n,
temp.left);
temp.right = constructTreeUtil(pre, preLN, index_ptr, n,
temp.right);
}
return temp;
}
// A wrapper over constructTreeUtil()
Node constructTree(int pre[], char preLN[], int n, Node node)
{
// Initialize index as 0. Value of index is used in recursion to
// maintain the current index in pre[] and preLN[] arrays.
int index = 0;
return constructTreeUtil(pre, preLN, myindex, n, node);
}
/* This function is used only for testing */
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 the above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
int pre[] = new int[]{10, 30, 20, 5, 15};
char preLN[] = new char[]{'N', 'N', 'L', 'L', 'L'};
int n = pre.length;
// construct the above tree
Node mynode = tree.constructTree(pre, preLN, n, tree.root);
// Test the constructed tree
System.out.println("Following is Inorder Traversal of the"
+ "Constructed Binary Tree: ");
tree.printInorder(mynode);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# A program to construct Binary
# Tree from preorder traversal
# Utility function to create a
# new Binary Tree node
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A recursive function to create a
# Binary Tree from given pre[] preLN[]
# arrays. The function returns root of
# tree. index_ptr is used to update
# index values in recursive calls. index
# must be initially passed as 0
def constructTreeUtil(pre, preLN, index_ptr, n):
index = index_ptr[0] # store the current value
# of index in pre[]
# Base Case: All nodes are constructed
if index == n:
return None
# Allocate memory for this node and
# increment index for subsequent
# recursive calls
temp = newNode(pre[index])
index_ptr[0] += 1
# If this is an internal node, construct left
# and right subtrees and link the subtrees
if preLN[index] == 'N':
temp.left = constructTreeUtil(pre, preLN,
index_ptr, n)
temp.right = constructTreeUtil(pre, preLN,
index_ptr, n)
return temp
# A wrapper over constructTreeUtil()
def constructTree(pre, preLN, n):
# Initialize index as 0. Value of index is
# used in recursion to maintain the current
# index in pre[] and preLN[] arrays.
index = [0]
return constructTreeUtil(pre, preLN, index, n)
# This function is used only for testing
def printInorder (node):
if node == None:
return
# first recur on left child
printInorder (node.left)
# then print the data of node
print(node.data,end=" ")
# now recur on right child
printInorder (node.right)
# Driver Code
if __name__ == '__main__':
root = None
# Constructing tree given in
# the above figure
# 10
# / \
# 30 15
# / \
# 20 5
pre = [10, 30, 20, 5, 15]
preLN = ['N', 'N', 'L', 'L', 'L']
n = len(pre)
# construct the above tree
root = constructTree (pre, preLN, n)
# Test the constructed tree
print("Following is Inorder Traversal of",
"the Constructed Binary Tree:")
printInorder (root)
# This code is contributed by PranchalK
C#
// C# program to construct a binary
// tree from preorder traversal
using System;
// A Binary Tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class Index
{
public int index = 0;
}
class GFG
{
public Node root;
public Index myindex = new Index();
/* A recursive function to create a
Binary Tree from given pre[] preLN[] arrays.
The function returns root of tree. index_ptr
is used to update index values in recursive
calls. index must be initially passed as 0 */
public virtual Node constructTreeUtil(int[] pre, char[] preLN,
Index index_ptr, int n,
Node temp)
{
// store the current value of index in pre[]
int index = index_ptr.index;
// Base Case: All nodes are constructed
if (index == n)
{
return null;
}
// Allocate memory for this node
// and increment index for
// subsequent recursive calls
temp = new Node(pre[index]);
(index_ptr.index)++;
// If this is an internal node,
// construct left and right subtrees
// and link the subtrees
if (preLN[index] == 'N')
{
temp.left = constructTreeUtil(pre, preLN, index_ptr,
n, temp.left);
temp.right = constructTreeUtil(pre, preLN, index_ptr,
n, temp.right);
}
return temp;
}
// A wrapper over constructTreeUtil()
public virtual Node constructTree(int[] pre, char[] preLN,
int n, Node node)
{
// Initialize index as 0. Value of
// index is used in recursion to
// maintain the current index in
// pre[] and preLN[] arrays.
int index = 0;
return constructTreeUtil(pre, preLN,
myindex, n, node);
}
/* This function is used only for testing */
public virtual 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 Code
public static void Main(string[] args)
{
GFG tree = new GFG();
int[] pre = new int[]{10, 30, 20, 5, 15};
char[] preLN = new char[]{'N', 'N', 'L', 'L', 'L'};
int n = pre.Length;
// construct the above tree
Node mynode = tree.constructTree(pre, preLN,
n, tree.root);
// Test the constructed tree
Console.WriteLine("Following is Inorder Traversal of the" +
"Constructed Binary Tree: ");
tree.printInorder(mynode);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to construct a binary
// tree from preorder traversal
// A Binary Tree node
class Node
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
class Index
{
constructor()
{
this.index = 0;
}
}
var root = null;
var myindex = new Index();
/* A recursive function to create a
Binary Tree from given pre[] preLN[] arrays.
The function returns root of tree. index_ptr
is used to update index values in recursive
calls. index must be initially passed as 0 */
function constructTreeUtil(pre, preLN, index_ptr, n, temp)
{
// store the current value of index in pre[]
var index = index_ptr.index;
// Base Case: All nodes are constructed
if (index == n)
{
return null;
}
// Allocate memory for this node
// and increment index for
// subsequent recursive calls
temp = new Node(pre[index]);
(index_ptr.index)++;
// If this is an internal node,
// construct left and right subtrees
// and link the subtrees
if (preLN[index] == 'N')
{
temp.left = constructTreeUtil(pre, preLN, index_ptr,
n, temp.left);
temp.right = constructTreeUtil(pre, preLN, index_ptr,
n, temp.right);
}
return temp;
}
// A wrapper over constructTreeUtil()
function constructTree(pre, preLN, n, node)
{
// Initialize index as 0. Value of
// index is used in recursion to
// maintain the current index in
// pre[] and preLN[] arrays.
var index = 0;
return constructTreeUtil(pre, preLN,
myindex, n, node);
}
/* This function is used only for testing */
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);
}
// Driver Code
var pre = [10, 30, 20, 5, 15];
var preLN = ['N', 'N', 'L', 'L', 'L'];
var n = pre.length;
// construct the above tree
var mynode = constructTree(pre, preLN,
n, root);
// Test the constructed tree
document.write("Following is Inorder Traversal of the" +
"Constructed Binary Tree:<br>");
printInorder(mynode);
</script>
Producción
Inorder Traversal of the Constructed Binary Tree: 20 30 5 10 15
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 2: usar Stack sin recursividad
Acercarse:
- Como se proporciona el Pre-order Traversal, primero hacemos una raíz e insertamos el primer valor en ella.
- Atraviesa el recorrido de pedido previo dado.
- Compruebe la izquierda de la parte superior de la pila
- Si es NULL entonces agregamos el Node presente a la izquierda
- De lo contrario, agregue a la derecha si la derecha es NULL .
- Si tanto la izquierda como la derecha no son NULL, significa que el Node tiene tanto la izquierda como la derecha, por lo que sacamos los Nodes hasta que no obtengamos ningún Node cuya izquierda o derecha sea NULL.
- Si el Node actual no es un Node hoja, inserte el Node en la pila.
- Compruebe la izquierda de la parte superior de la pila
- Finalmente devuelva la raíz del árbol construido.
A continuación se muestra la implementación del enfoque anterior:
C++
// A program to construct Binary Tree from preorder
// traversal
#include <bits/stdc++.h>
using namespace std;
// A binary tree node structure
struct node {
int data;
struct node* left;
struct node* right;
node(int x)
{
data = x;
left = right = NULL;
}
};
struct node* constructTree(int pre[], char preLN[], int n)
{
// Taking an empty Stack
stack<node*> st;
// Setting up root node
node* root = new node(pre[0]);
// Checking if root is not leaf node
if (preLN[0] != 'L')
st.push(root);
// Iterating over the given node values
for (int i = 1; i < n; i++) {
node* temp = new node(pre[i]);
// Checking if the left position is NULL or not
if (!st.top()->left) {
st.top()->left = temp;
// Checking for leaf node
if (preLN[i] != 'L')
st.push(temp);
}
// Checking if the right position is NULL or not
else if (!st.top()->right) {
st.top()->right = temp;
if (preLN[i] != 'L')
// Checking for leaf node
st.push(temp);
}
// If left and right of top node is already filles
else {
while (st.top()->left && st.top()->right)
st.pop();
st.top()->right = temp;
// Checking for leaf node
if (preLN[i] != 'L')
st.push(temp);
}
}
// Returning the root of tree
return root;
}
// This function is used only for testing
void printInorder(struct node* node)
{
if (node == NULL)
return;
// First recur on left child
printInorder(node->left);
// Print the data of node
printf("%d ", node->data);
// Now recur on right child
printInorder(node->right);
}
// Driver code
int main()
{
struct node* root = NULL;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
int pre[] = { 10, 30, 20, 5, 15 };
char preLN[] = { 'N', 'N', 'L', 'L', 'L' };
int n = sizeof(pre) / sizeof(pre[0]);
// construct the above tree
root = constructTree(pre, preLN, n);
// Test the constructed tree
printf("Inorder Traversal of the Constructed Binary Tree: \n");
printInorder(root);
return 0;
}
// This code is contributed by shubhamrajput6156
Java
// Java program to construct Binary Tree from preorder
// traversal
// A Binary Tree node
import java.util.*;
class GFG
{
static class node {
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
public static node constructTree(int []pre, char []preLN, int n)
{
// Taking an empty Stack
Stack<node> st = new Stack<node>();
// Setting up root node
node root = new node(pre[0]);
// Checking if root is not leaf node
if (preLN[0] != 'L')
st.push(root);
// Iterating over the given node values
for (int i = 1; i < n; i++) {
node temp = new node(pre[i]);
// Checking if the left position is NULL or not
if (st.peek().left==null) {
st.peek().left = temp;
// Checking for leaf node
if (preLN[i] != 'L')
st.push(temp);
}
// Checking if the right position is NULL or not
else if (st.peek().right==null) {
st.peek().right = temp;
// Checking for leaf node
if (preLN[i] != 'L')
st.push(temp);
}
// If left and right of top node is already filles
else {
while (st.peek().left!=null && st.peek().right!=null)
st.pop();
st.peek().right = temp;
// Checking for leaf node
if (preLN[i] != 'L')
st.push(temp);
}
}
// Returning the root of tree
return root;
}
// This function is used only for testing
public static void printInorder( node temp)
{
if (temp == null)
return;
// First recur on left child
printInorder(temp.left);
// Print the data of node
System.out.println(temp.data);
// Now recur on right child
printInorder(temp.right);
}
// driver function to test the above functions
public static void main(String args[])
{
//node root = null;
/* Constructing tree given in the above figure
10
/ \
30 15
/ \
20 5 */
int []pre = { 10, 30, 20, 5, 15 };
char []preLN = { 'N', 'N', 'L', 'L', 'L' };
int n = pre.length;
// construct the above tree
node root = constructTree(pre, preLN, n);
// Test the constructed tree
System.out.println("Inorder Traversal of the Constructed Binary Tree: ");
printInorder(root);
}
}
// This code is contributed by jana_sayantan.
Producción
Inorder Traversal of the Constructed Binary Tree: 20 30 5 10 15
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Construya el árbol k-ario completo a partir de su recorrido previo al pedido
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