Requisito previo: recorrido del árbol en orden/preorden/posorden
Dado un árbol binario, realice un recorrido en orden posterior.
Hemos discutido a continuación los métodos para el recorrido posterior al pedido.
1) Recorrido Posorden Recursivo .
2) Recorrido posterior al pedido usando Stack.
2) Recorrido posterior al pedido usando dos pilas .
En este método se analiza una solución basada en DFS . Realizamos un seguimiento de los Nodes visitados en una tabla hash.
C++
// CPP program or postorder traversal
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
void postorder(struct Node* head)
{
struct Node* temp = head;
unordered_set<Node*> visited;
while (temp && visited.find(temp) == visited.end()) {
// Visited left subtree
if (temp->left &&
visited.find(temp->left) == visited.end())
temp = temp->left;
// Visited right subtree
else if (temp->right &&
visited.find(temp->right) == visited.end())
temp = temp->right;
// Print node
else {
printf("%d ", temp->data);
visited.insert(temp);
temp = head;
}
}
}
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
struct Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
postorder(root);
return 0;
}
Java
// JAVA program or postorder traversal
import java.util.*;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
int data;
Node left, right;
Node(int data)
{
this.data = data;
this.left = this.right = null;
}
};
class GFG
{
Node root;
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
void postorder(Node head)
{
Node temp = root;
HashSet<Node> visited = new HashSet<>();
while ((temp != null && !visited.contains(temp)))
{
// Visited left subtree
if (temp.left != null &&
!visited.contains(temp.left))
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
!visited.contains(temp.right))
temp = temp.right;
// Print node
else
{
System.out.printf("%d ", temp.data);
visited.add(temp);
temp = head;
}
}
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
GFG gfg = new GFG();
gfg.root = new Node(8);
gfg.root.left = new Node(3);
gfg.root.right = new Node(10);
gfg.root.left.left = new Node(1);
gfg.root.left.right = new Node(6);
gfg.root.left.right.left = new Node(4);
gfg.root.left.right.right = new Node(7);
gfg.root.right.right = new Node(14);
gfg.root.right.right.left = new Node(13);
gfg.postorder(gfg.root);
}
}
// This code is contributed by Rajput-Ji
Python
# Python program or postorder traversal ''' A binary tree node has data, pointer to left child and a pointer to right child ''' class newNode: # Constructor to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None ''' Helper function that allocates a new node with the given data and NULL left and right pointers. ''' def postorder(head): temp = head visited = set() while (temp and temp not in visited): # Visited left subtree if (temp.left and temp.left not in visited): temp = temp.left # Visited right subtree elif (temp.right and temp.right not in visited): temp = temp.right # Print node else: print(temp.data, end = " ") visited.add(temp) temp = head ''' Driver program to test above functions''' if __name__ == '__main__': root = newNode(8) root.left = newNode(3) root.right = newNode(10) root.left.left = newNode(1) root.left.right = newNode(6) root.left.right.left = newNode(4) root.left.right.right = newNode(7) root.right.right = newNode(14) root.right.right.left = newNode(13) postorder(root) # This code is contributed by # SHUBHAMSINGH10
C#
// C# program or postorder traversal
using System;
using System.Collections.Generic;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
public
class Node
{
public
int data;
public
Node left, right;
public
Node(int data)
{
this.data = data;
this.left = this.right = null;
}
};
class GFG
{
Node root;
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
void postorder(Node head)
{
Node temp = root;
HashSet<Node> visited = new HashSet<Node>();
while ((temp != null && !visited.Contains(temp)))
{
// Visited left subtree
if (temp.left != null &&
!visited.Contains(temp.left))
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
!visited.Contains(temp.right))
temp = temp.right;
// Print node
else
{
Console.Write(temp.data + " ");
visited.Add(temp);
temp = head;
}
}
}
/* Driver code*/
public static void Main(String[] args)
{
GFG gfg = new GFG();
gfg.root = new Node(8);
gfg.root.left = new Node(3);
gfg.root.right = new Node(10);
gfg.root.left.left = new Node(1);
gfg.root.left.right = new Node(6);
gfg.root.left.right.left = new Node(4);
gfg.root.left.right.right = new Node(7);
gfg.root.right.right = new Node(14);
gfg.root.right.right.left = new Node(13);
gfg.postorder(gfg.root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program or postorder traversal
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
var root = null;
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
function postorder(head)
{
var temp = root;
var visited = new Set();
while ((temp != null && !visited.has(temp)))
{
// Visited left subtree
if (temp.left != null &&
!visited.has(temp.left))
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
!visited.has(temp.right))
temp = temp.right;
// Print node
else
{
document.write(temp.data + " ");
visited.add(temp);
temp = head;
}
}
}
/* Driver code*/
root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
root.right.right = new Node(14);
root.right.right.left = new Node(13);
postorder(root);
</script>
Producción:
1 4 7 6 3 13 14 10 8
Solución alternativa:
podemos mantener el indicador visitado con cada Node en lugar de una tabla hash separada.
C++
// CPP program or postorder traversal
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
bool visited;
};
void postorder(struct Node* head)
{
struct Node* temp = head;
while (temp && temp->visited == false) {
// Visited left subtree
if (temp->left && temp->left->visited == false)
temp = temp->left;
// Visited right subtree
else if (temp->right && temp->right->visited == false)
temp = temp->right;
// Print node
else {
printf("%d ", temp->data);
temp->visited = true;
temp = head;
}
}
}
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = false;
return (node);
}
/* Driver program to test above functions*/
int main()
{
struct Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
postorder(root);
return 0;
}
Java
// Java program or postorder traversal
class GFG
{
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
static class Node
{
int data;
Node left, right;
boolean visited;
}
static void postorder( Node head)
{
Node temp = head;
while (temp != null &&
temp.visited == false)
{
// Visited left subtree
if (temp.left != null &&
temp.left.visited == false)
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
temp.right.visited == false)
temp = temp.right;
// Print node
else
{
System.out.printf("%d ", temp.data);
temp.visited = true;
temp = head;
}
}
}
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
node.visited = false;
return (node);
}
/* Driver code*/
public static void main(String []args)
{
Node root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
root.right.right = newNode(14);
root.right.right.left = newNode(13);
postorder(root);
}
}
// This code is contributed by Arnab Kundu
Python3
"""Python3 program or postorder traversal """ # A Binary Tree Node # Utility function to create a # new tree node class newNode: # Constructor to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None self.visited = False def postorder(head) : temp = head while (temp and temp.visited == False): # Visited left subtree if (temp.left and temp.left.visited == False): temp = temp.left # Visited right subtree elif (temp.right and temp.right.visited == False): temp = temp.right # Print node else: print(temp.data, end = " ") temp.visited = True temp = head # Driver Code if __name__ == '__main__': root = newNode(8) root.left = newNode(3) root.right = newNode(10) root.left.left = newNode(1) root.left.right = newNode(6) root.left.right.left = newNode(4) root.left.right.right = newNode(7) root.right.right = newNode(14) root.right.right.left = newNode(13) postorder(root) # This code is contributed by # SHUBHAMSINGH10
C#
// C# program or postorder traversal
using System;
class GFG
{
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
class Node
{
public int data;
public Node left, right;
public bool visited;
}
static void postorder( Node head)
{
Node temp = head;
while (temp != null &&
temp.visited == false)
{
// Visited left subtree
if (temp.left != null &&
temp.left.visited == false)
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
temp.right.visited == false)
temp = temp.right;
// Print node
else
{
Console.Write("{0} ", temp.data);
temp.visited = true;
temp = head;
}
}
}
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
node.visited = false;
return (node);
}
/* Driver code*/
public static void Main(String []args)
{
Node root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
root.right.right = newNode(14);
root.right.right.left = newNode(13);
postorder(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program or postorder traversal
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
class Node
{
constructor() {
this.data;
this.left;
this.right;
this.visited;
}
}
function postorder(head)
{
let temp = head;
while (temp != null &&
temp.visited == false)
{
// Visited left subtree
if (temp.left != null &&
temp.left.visited == false)
temp = temp.left;
// Visited right subtree
else if (temp.right != null &&
temp.right.visited == false)
temp = temp.right;
// Print node
else
{
document.write(temp.data + " ");
temp.visited = true;
temp = head;
}
}
}
function newNode(data)
{
let node = new Node();
node.data = data;
node.left = null;
node.right = null;
node.visited = false;
return (node);
}
let root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
root.right.right = newNode(14);
root.right.right.left = newNode(13);
postorder(root);
</script>
Producción:
1 4 7 6 3 13 14 10 8
Complejidad de tiempo: O(n 2 ) en el peor de los casos movemos el puntero de nuevo a la cabeza después de visitar cada Node.
Espacio auxiliar: O(1)
Solución alternativa usando unordered_map en el que no tenemos que mover el puntero de nuevo a la cabeza, por lo que la complejidad del tiempo es O(n).
C++
// CPP program or postorder traversal
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
bool visited;
};
void postorder(Node* root)
{
Node* n = root;
unordered_map<Node*, Node*> parentMap;
parentMap.insert(pair<Node*, Node*>(root, nullptr));
while (n) {
if (n->left && parentMap.find(n->left) == parentMap.end()) {
parentMap.insert(pair<Node*, Node*>(n->left, n));
n = n->left;
}
else if (n->right && parentMap.find(n->right) == parentMap.end()) {
parentMap.insert(pair<Node*, Node*>(n->right, n));
n = n->right;
}
else {
cout << n->data << " ";
n = (parentMap.find(n))->second;
}
}
}
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = false;
return (node);
}
/* Driver program to test above functions*/
int main()
{
struct Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
postorder(root);
return 0;
}
Producción:
1 4 7 6 3 13 14 10 8
Complejidad temporal : O(n) donde n no es ningún Node en un árbol binario
Espacio auxiliar: O(n) desde que se usa unordered_map
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA