Dados dos arreglos que representan recorridos en orden previo de un árbol binario completo y su árbol espejo, necesitamos escribir un programa para construir el árbol binario usando estos dos recorridos en orden previo.
Un árbol binario completo es un árbol binario donde cada Node tiene 0 o 2 hijos.
Nota : No es posible construir un árbol binario general utilizando estos dos recorridos. Pero podemos crear un árbol binario completo utilizando los recorridos anteriores sin ninguna ambigüedad. Para más detalles consulte este artículo.
Ejemplos:
Input : preOrder[] = {1,2,4,5,3,6,7}
preOrderMirror[] = {1,3,7,6,2,5,4}
Output : 1
/ \
2 3
/ \ / \
4 5 6 7
- Método 1 : Consideremos las dos arrays dadas como preOrder[] = {1, 2, 4, 5, 3, 6, 7} y preOrderMirror[] = {1 ,3 ,7 ,6 ,2 ,5 ,4} .
Tanto en preOrder[] como en preOrderMirror[], el elemento más a la izquierda es la raíz del árbol. Dado que el árbol está lleno y el tamaño de la array es mayor que 1, el valor junto a 1 en preOrder[] debe ser el hijo izquierdo de la raíz y el valor junto a 1 en preOrderMirror[] debe ser el hijo derecho de la raíz. Entonces sabemos que 1 es raíz, 2 es hijo izquierdo y 3 es hijo derecho. ¿Cómo encontrar todos los Nodes en el subárbol izquierdo? Sabemos que 2 es la raíz de todos los Nodes del subárbol izquierdo y 3 es la raíz de todos los Nodes del subárbol derecho. Todos los Nodes desde y 2 en preOrderMirror[] deben estar en el subárbol izquierdo del Node raíz 1 y todos los Nodes después del 3 y antes del 2 en preOrderMirror[] deben estar en el subárbol derecho del Node raíz 1. Ahora sabemos que 1 es raíz, elementos {2 , 5, 4} están en el subárbol izquierdo y los elementos {3, 7, 6} están en el subárbol derecho.
1
/ \
/ \
{2,5,4} {3,7,6}
- Seguiremos recursivamente el enfoque anterior y obtendremos el siguiente árbol:
1
/ \
2 3
/ \ / \
4 5 6 7
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
#include<bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to print inorder traversal
// of a Binary Tree
void printInorder(Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
// A recursive function to construct Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
Node* constructBinaryTreeUtil(int pre[], int preM[],
int &preIndex, int l,int h,int size)
{
// Base case
if (preIndex >= size || l > h)
return NULL;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
Node* root = newNode(pre[preIndex]);
++(preIndex);
// If the current subarray has only one element,
// no need to recur
if (l == h)
return root;
// Search the next element of pre[] in preM[]
int i;
for (i = l; i <= h; ++i)
if (pre[preIndex] == preM[i])
break;
// construct left and right subtrees recursively
if (i <= h)
{
root->left = constructBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root->right = constructBinaryTreeUtil (pre, preM,
preIndex, l+1, i-1, size);
}
// return root
return root;
}
// function to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
void constructBinaryTree(Node* root,int pre[],
int preMirror[], int size)
{
int preIndex = 0;
int preMIndex = 0;
root = constructBinaryTreeUtil(pre,preMirror,
preIndex,0,size-1,size);
printInorder(root);
}
// Driver program to test above functions
int main()
{
int preOrder[] = {1,2,4,5,3,6,7};
int preOrderMirror[] = {1,3,7,6,2,5,4};
int size = sizeof(preOrder)/sizeof(preOrder[0]);
Node* root = new Node;
constructBinaryTree(root,preOrder,preOrderMirror,size);
return 0;
}
Java
// Java program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
class GFG
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
static class INT
{
int a;
INT(int a){this.a=a;}
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// A utility function to print inorder traversal
// of a Binary Tree
static void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.printf("%d ", node.data);
printInorder(node.right);
}
// A recursive function to construct Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
static Node conBinaryTreeUtil(int pre[], int preM[],
INT preIndex, int l, int h, int size)
{
// Base case
if (preIndex.a >= size || l > h)
return null;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
Node root = newNode(pre[preIndex.a]);
++(preIndex.a);
// If the current subarray has only one element,
// no need to recur
if (l == h)
return root;
// Search the next element of pre[] in preM[]
int i;
for (i = l; i <= h; ++i)
if (pre[preIndex.a] == preM[i])
break;
// construct left and right subtrees recursively
if (i <= h)
{
root.left = conBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root.right = conBinaryTreeUtil (pre, preM,
preIndex, l + 1, i - 1, size);
}
// return root
return root;
}
// function to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
static void conBinaryTree(Node root,int pre[],
int preMirror[], int size)
{
INT preIndex = new INT(0);
int preMIndex = 0;
root = conBinaryTreeUtil(pre,preMirror,
preIndex, 0, size - 1, size);
printInorder(root);
}
// Driver code
public static void main(String args[])
{
int preOrder[] = {1,2,4,5,3,6,7};
int preOrderMirror[] = {1,3,7,6,2,5,4};
int size = preOrder.length;
Node root = new Node();
conBinaryTree(root,preOrder,preOrderMirror,size);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to construct full binary # tree using its preorder traversal and # preorder traversal of its mirror tree # Utility function to create a new tree node class newNode: def __init__(self,data): self.data = data self.left = self.right = None # A utility function to print inorder # traversal of a Binary Tree def printInorder(node): if (node == None) : return printInorder(node.left) print(node.data, end = " ") printInorder(node.right) # A recursive function to construct Full # binary tree from pre[] and preM[]. # preIndex is used to keep track of index # in pre[]. l is low index and h is high # index for the current subarray in preM[] def constructBinaryTreeUtil(pre, preM, preIndex, l, h, size): # Base case if (preIndex >= size or l > h) : return None , preIndex # The first node in preorder traversal # is root. So take the node at preIndex # from preorder and make it root, and # increment preIndex root = newNode(pre[preIndex]) preIndex += 1 # If the current subarray has only # one element, no need to recur if (l == h): return root, preIndex # Search the next element of # pre[] in preM[] i = 0 for i in range(l, h + 1): if (pre[preIndex] == preM[i]): break # construct left and right subtrees # recursively if (i <= h): root.left, preIndex = constructBinaryTreeUtil(pre, preM, preIndex, i, h, size) root.right, preIndex = constructBinaryTreeUtil(pre, preM, preIndex, l + 1, i - 1, size) # return root return root, preIndex # function to construct full binary tree # using its preorder traversal and preorder # traversal of its mirror tree def constructBinaryTree(root, pre, preMirror, size): preIndex = 0 preMIndex = 0 root, x = constructBinaryTreeUtil(pre, preMirror, preIndex, 0, size - 1, size) Print Inorder(root) # Driver code if __name__ =="__main__": preOrder = [1, 2, 4, 5, 3, 6, 7] preOrderMirror = [1, 3, 7, 6, 2, 5, 4] size = 7 root = newNode(0) constructBinaryTree(root, preOrder, preOrderMirror, size) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
using System;
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
};
public class INT
{
public int a;
public INT(int a){this.a=a;}
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// A utility function to print inorder traversal
// of a Binary Tree
static void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
Console.Write("{0} ", node.data);
printInorder(node.right);
}
// A recursive function to construct Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
static Node conBinaryTreeUtil(int []pre, int []preM,
INT preIndex, int l, int h, int size)
{
// Base case
if (preIndex.a >= size || l > h)
return null;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
Node root = newNode(pre[preIndex.a]);
++(preIndex.a);
// If the current subarray has only one element,
// no need to recur
if (l == h)
return root;
// Search the next element of pre[] in preM[]
int i;
for (i = l; i <= h; ++i)
if (pre[preIndex.a] == preM[i])
break;
// construct left and right subtrees recursively
if (i <= h)
{
root.left = conBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root.right = conBinaryTreeUtil (pre, preM,
preIndex, l + 1, i - 1, size);
}
// return root
return root;
}
// function to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
static void conBinaryTree(Node root,int []pre,
int []preMirror, int size)
{
INT preIndex = new INT(0);
int preMIndex = 0;
root = conBinaryTreeUtil(pre,preMirror,
preIndex, 0, size - 1, size);
printInorder(root);
}
// Driver code
public static void Main(String []args)
{
int []preOrder = {1,2,4,5,3,6,7};
int []preOrderMirror = {1,3,7,6,2,5,4};
int size = preOrder.Length;
Node root = new Node();
conBinaryTree(root,preOrder,preOrderMirror,size);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
// A Binary Tree Node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
class INT
{
constructor(a)
{
this.a = a;
}
}
// Utility function to create a new tree node
function newNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// 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);
}
// A recursive function to construct Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
function conBinaryTreeUtil(pre, preM, preIndex, l, h, size)
{
// Base case
if (preIndex.a >= size || l > h)
return null;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
var root = newNode(pre[preIndex.a]);
++(preIndex.a);
// If the current subarray has only one element,
// no need to recur
if (l == h)
return root;
// Search the next element of pre[] in preM[]
var i;
for (i = l; i <= h; ++i)
if (pre[preIndex.a] == preM[i])
break;
// construct left and right subtrees recursively
if (i <= h)
{
root.left = conBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root.right = conBinaryTreeUtil (pre, preM,
preIndex, l + 1, i - 1, size);
}
// return root
return root;
}
// function to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
function conBinaryTree(root,pre, preMirror, size)
{
var preIndex = new INT(0);
var preMIndex = 0;
root = conBinaryTreeUtil(pre,preMirror,
preIndex, 0, size - 1, size);
printInorder(root);
}
// Driver code
var preOrder = [1,2,4,5,3,6,7];
var preOrderMirror = [1,3,7,6,2,5,4];
var size = preOrder.length;
var root = new Node();
conBinaryTree(root,preOrder,preOrderMirror,size);
</script>
Producción
4 2 5 1 6 3 7
- Método 2 : Si observamos con cuidado, entonces el reverso del recorrido de Preorder del árbol espejo será el recorrido de Postorder del árbol original. Podemos construir el árbol a partir de recorridos Preorder y Postorder dados de una manera similar a la anterior. Puede consultar este artículo sobre cómo construir un árbol binario completo a partir de recorridos previos y posteriores dados.
Este artículo es una contribución de Harsh Agarwal . 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