Dado el recorrido posterior al orden de un árbol de búsqueda binario, construya el BST.
Por ejemplo,
1. Si el recorrido dado es {1, 7, 5, 50, 40, 10}, entonces se debe construir el siguiente árbol y se debe devolver la raíz del árbol.
10 / \ 5 40 / \ \ 1 7 50
Entrada: 1 7 5 50 40 10
Salida:
Recorrido en orden del árbol construido:
1 5 7 10 40 50
Si el recorrido dado es {2, 6, 4, 9, 13, 11, 7}, entonces se debe construir el siguiente árbol y la raíz del árbol debe ser devuelta.
7 / \ 4 11 / \ / \ 2 6 9 13Entrada: 2 6 4 9 13 11 7
Salida:
Recorrido en orden del árbol construido:
2 4 6 7 9 11 13
Veamos primero el funcionamiento del recorrido posterior al pedido .
Left Right Root Hence last node of post order will be root of tree, create it and push to stack. If next element(i-1) is greater then it should be in right subtree. If next element(i-1) is less then it should be in left subtree.
Algoritmo:
- Empuje la raíz del BST a la pila, es decir, el último elemento de la array.
- Comience a recorrer la array en sentido inverso, si el siguiente elemento es> el elemento en la parte superior de la pila,
establezca este elemento como el elemento secundario derecho del elemento en la parte superior de la pila y también empújelo a la pila. - De lo contrario, si el siguiente elemento es < el elemento en la parte superior de la pila,
comience a extraer todos los elementos de la pila hasta que la pila esté vacía o el elemento actual se convierta en > el elemento en la parte superior de la pila. - Haga que este elemento sea hijo izquierdo del último Node extraído y repita los pasos anteriores hasta que la array se atraviese por completo.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ implementation of the algorithm
/* A binary tree node has data,
pointer to left child and a pointer
to right child */
#include<bits/stdc++.h>
using namespace std;
// Class Node has data and references
// to the left and the right child.
class Node
{
public:
int data;
Node* left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function that creates the tree
Node* constructTreeUtil(int post[], int n)
{
// Last node is root
Node* root = new Node(post[n - 1]);
stack<Node*> s;
s.push(root);
// Traverse from second last node
for (int i = n - 2; i >= 0; --i)
{
Node* x = new Node(post[i]);
// Keep popping nodes while top()
// of stack is greater.
Node* temp = NULL;
while (s.size() &&
post[i] < s.top()->data)
temp = s.top(), s.pop();
// Make x as left child of temp
if (temp != NULL)
temp->left = x;
// Else make x as right of top
else
s.top()->right = x;
s.push(x);
}
return root;
}
// Function that calls the method
// which constructs the tree
Node* constructTree(int post[], int size)
{
return constructTreeUtil(post, 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 post[] = { 1, 7, 5, 50, 40, 10 };
int size = sizeof(post)/sizeof(int);
Node* root = constructTree(post, size);
cout << "Inorder traversal of "
<< "the constructed tree:\n";
printInorder(root);
}
// This code is contributed by Arnab Kundu
Java
// Java implementation of the algorithm
/* A binary tree node has data, pointer to left child
and a pointer to right child */
import java.util.*;
// Class Node has data and references to the left
// and the right child.
class Node {
int data;
Node left, right;
Node(int data)
{
this.data = data;
left = right = null;
}
}
class BinaryTree {
// Function that creates the tree
Node constructTreeUtil(int post[], int n)
{
// Last node is root
Node root = new Node(post[n - 1]);
Stack<Node> s = new Stack<>();
s.push(root);
// Traverse from second last node
for (int i = n - 2; i >= 0; --i) {
Node x = new Node(post[i]);
// Keep popping nodes while top() of stack
// is greater.
Node temp = null;
while (!s.isEmpty() && post[i] < s.peek().data)
temp = s.pop();
// Make x as left child of temp
if (temp != null)
temp.left = x;
// Else make x as right of top
else
s.peek().right = x;
s.push(x);
}
return root;
}
// Function that calls the method which constructs the tree
Node constructTree(int post[], int size)
{
return constructTreeUtil(post, 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 program to test above functions
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
int post[] = new int[] { 1, 7, 5, 50, 40, 10 };
int size = post.length;
Node root = tree.constructTree(post, size);
System.out.println("Inorder traversal of the constructed tree:");
tree.printInorder(root);
}
}
Python3
# Python3 implementation of the algorithm # A binary tree node has data, # pointer to left child and a pointer # to right child # Class Node has data and references # to the left and the right child. class Node: def __init__(self, data = 0): self.data = data self.left = None self.right = None # Function that creates the tree def constructTreeUtil(post , n): # Last node is root root = Node(post[n - 1]) s = [] s.append(root) i = n - 2 # Traverse from second last node while ( i >= 0): x = Node(post[i]) # Keep popping nodes while top() # of stack is greater. temp = None while (len(s) > 0 and post[i] < s[-1].data) : temp = s[-1] s.pop() # Make x as left child of temp if (temp != None): temp.left = x # Else make x as right of top else: s[-1].right = x s.append(x) i = i - 1 return root # Function that calls the method # which constructs the tree def constructTree( post, size): return constructTreeUtil(post, size) # 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) # Driver Code post = [1, 7, 5, 50, 40, 10] size = len(post) root = constructTree(post, size) print( "Inorder traversal of the constructed tree:") printInorder(root) # This code is contributed by Arnab Kundu
C#
// C# implementation of the algorithm
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
using System;
using System.Collections.Generic;
// Class Node has data and references
// to the left and the right child.
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
public class BinaryTree
{
// Function that creates the tree
Node constructTreeUtil(int []post, int n)
{
// Last node is root
Node root = new Node(post[n - 1]);
Stack<Node> s = new Stack<Node>();
s.Push(root);
// Traverse from second last node
for (int i = n - 2; i >= 0; --i)
{
Node x = new Node(post[i]);
// Keep popping nodes while top() of stack
// is greater.
Node temp = null;
while (s.Count!=0 && post[i] < s.Peek().data)
temp = s.Pop();
// Make x as left child of temp
if (temp != null)
temp.left = x;
// Else make x as right of top
else
s.Peek().right = x;
s.Push(x);
}
return root;
}
// Function that calls the
// method which constructs the tree
Node constructTree(int []post, int size)
{
return constructTreeUtil(post, size);
}
// A utility function to print
// inorder traversal of a Binary Tree
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
Console.Write(node.data + " ");
printInorder(node.right);
}
// Driver code
public static void Main()
{
BinaryTree tree = new BinaryTree();
int []post = new int[] { 1, 7, 5, 50, 40, 10 };
int size = post.Length;
Node root = tree.constructTree(post, size);
Console.WriteLine("Inorder traversal of the constructed tree:");
tree.printInorder(root);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript implementation of the algorithm
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
// Class Node has data and references
// to the left and the right child.
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Function that creates the tree
function constructTreeUtil(post, n)
{
// Last node is root
var root = new Node(post[n - 1]);
var s = [];
s.push(root);
// Traverse from second last node
for (var i = n - 2; i >= 0; --i)
{
var x = new Node(post[i]);
// Keep popping nodes while top() of stack
// is greater.
var temp = null;
while (s.length!=0 && post[i] < s[s.length-1].data)
temp = s.pop();
// Make x as left child of temp
if (temp != null)
temp.left = x;
// Else make x as right of top
else
s[s.length-1].right = x;
s.push(x);
}
return root;
}
// Function that calls the
// method which constructs the tree
function constructTree(post, size)
{
return constructTreeUtil(post, 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 post = [1, 7, 5, 50, 40, 10];
var size = post.length;
var root = constructTree(post, size);
document.write("Inorder traversal of the constructed tree:<br>");
printInorder(root);
</script>
Producción:
Inorder traversal of the constructed tree: 1 5 7 10 40 50
Complejidad de tiempo: O (n ^ 2) donde n es el tamaño de la array de entrada