Hemos visto diferentes formas de realizar el recorrido posterior al pedido en árboles binarios.
- Transversal de Post Orden .
- Recorrido iterativo en posorden utilizando dos pilas .
- Recorrido iterativo posterior al pedido utilizando One Stack .
Aquí hay otra forma de realizar el recorrido posorden en un árbol binario iterativamente usando una sola pila.
Considere las siguientes terminologías:
0 - Left element 1 - Right element 2 - Node element
El siguiente es el algoritmo detallado:
Take a Stack and perform the below operations: 1) Insert a pair of the root node as (node, 0). 2) Pop the top element to get the pair (Let a = node and b be the variable) If b is equal to 0: Push another pair as (node, 1) and Push the left child as (node->left, 0) Repeat Step 2 Else If b is equal to 1: Push another pair as (node, 2) and Push right child of node as (node->right, 0) Repeat Step 2 Else If b is equal to 2: Print(node->data) 3) Repeat the above steps while stack is not empty
Considere el siguiente árbol binario con solo 3 Nodes:
Ilustración:
1) Push(a, 0) Stack - (a, 0) 2) top = (a, 0) Push(a, 1) Push(b, 0) Stack - (b, 0) (a, 1) 3) top = (b, 0) Push(b, 1) Stack - (b, 1) (a, 1) 4) top = (b, 1) Push(b, 2) Stack - (b, 2) (a, 1) 5) top = (b, 2) print(b) Stack -(a, 1) 6) top = (a, 1) push(a, 2) push(c, 0) Stack - (c, 0) (a, 2) 7) top = (c, 0) push(c, 1) Stack - (c, 1) (a, 2) 8) top = (c, 1) push(c, 2) Stack - (c, 2) (a, 2) 9) top = (c, 2) print(c) Stack - (a, 2) 10) top = (a, 2) print(a) Stack - empty()
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print postorder traversal // iteratively #include <bits/stdc++.h> using namespace std; // Binary Tree Node struct Node { int data; struct Node* left; struct Node* right; }; // Helper function to create a // new Binary Tree node struct Node* newNode(int data) { struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return (node); } // Function to perform postorder // traversal iteratively void iterativePostorder(Node* root) { stack<pair<Node*, int> > st; st.push(make_pair(root, 0)); while (!st.empty()) { struct Node* temp = st.top().first; int b = st.top().second; st.pop(); if (temp == NULL) continue; if (b == 0) { st.push(make_pair(temp, 1)); if (temp->left != NULL) st.push(make_pair(temp->left, 0)); } else if (b == 1) { st.push(make_pair(temp, 2)); if (temp->right != NULL) st.push(make_pair(temp->right, 0)); } else cout << temp->data << " "; } } // Driver Code int main() { // Construct the below Binary Tree // 1 // / \ // 2 3 // / \ // 4 5 Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); iterativePostorder(root); return 0; }
Java
// Java program to print postorder traversal // iteratively import java.util.*; class GFG { //pair class static class Pair { Node first; int second; Pair(Node a,int b) { first = a; second = b; } } // Binary Tree Node static class Node { int data; Node left; Node right; }; // Helper function to create a // new Binary Tree node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return (node); } // Function to perform postorder // traversal iteratively static void iterativePostorder(Node root) { Stack<Pair> st = new Stack<Pair>(); st.add(new Pair(root, 0)); while (st.size() > 0) { Node temp = st.peek().first; int b = st.peek().second; st.pop(); if (temp == null) continue; if (b == 0) { st.add(new Pair(temp, 1)); if (temp.left != null) st.add(new Pair(temp.left, 0)); } else if (b == 1) { st.add(new Pair(temp, 2)); if (temp.right != null) st.add(new Pair(temp.right, 0)); } else System.out.print( temp.data + " "); } } // Driver Code public static void main(String args[]) { // Construct the below Binary Tree // 1 // / \ // 2 3 // / \ // 4 5 Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); iterativePostorder(root); } } // This code is contributed by Arnab Kundu
Python3
# Python program to print postorder traversal # iteratively # pair class class Pair: def __init__(self, a, b): self.first = a self.second = b # Binary Tree Node class Node : def __init__(self): self.data = 0 self.left = None self.right = None # Helper function to create a # new Binary Tree node def newNode(data): node = Node() node.data = data node.left = None node.right = None return (node) # Function to perform postorder # traversal iteratively def iterativePostorder( root): st = [] st.append(Pair(root, 0)) while (len(st)> 0): temp = st[-1].first b = st[-1].second st.pop() if (temp == None): continue if (b == 0) : st.append(Pair(temp, 1)) if (temp.left != None): st.append(Pair(temp.left, 0)) elif (b == 1): st.append(Pair(temp, 2)) if (temp.right != None): st.append(Pair(temp.right, 0)) else: print( temp.data ,end= " ") # Driver Code # Construct the below Binary Tree # 1 # / \ # 2 3 # / \ # 4 5 root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) iterativePostorder(root) # This code is contributed by Arnab Kundu
C#
// C# program to print postorder traversal // iteratively using System; using System.Collections.Generic; class GFG { //pair class public class Pair { public Node first; public int second; public Pair(Node a,int b) { first = a; second = b; } } // Binary Tree Node public class Node { public int data; public Node left; public Node right; }; // Helper function to create a // new Binary Tree node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return (node); } // Function to perform postorder // traversal iteratively static void iterativePostorder(Node root) { Stack<Pair> st = new Stack<Pair>(); st.Push(new Pair(root, 0)); while (st.Count > 0) { Node temp = st.Peek().first; int b = st.Peek().second; st.Pop(); if (temp == null) continue; if (b == 0) { st.Push(new Pair(temp, 1)); if (temp.left != null) st.Push(new Pair(temp.left, 0)); } else if (b == 1) { st.Push(new Pair(temp, 2)); if (temp.right != null) st.Push(new Pair(temp.right, 0)); } else Console.Write(temp.data + " "); } } // Driver Code public static void Main(String []args) { // Construct the below Binary Tree // 1 // / \ // 2 3 // / \ // 4 5 Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); iterativePostorder(root); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to print // postorder traversal iteratively // Binary Tree Node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Helper function to create a // new Binary Tree node function newNode(data) { let node = new Node(data); return (node); } // Function to perform postorder // traversal iteratively function iterativePostorder(root) { let st = []; st.push([root, 0]); while (st.length > 0) { let temp = st[st.length - 1][0]; let b = st[st.length - 1][1]; st.pop(); if (temp == null) continue; if (b == 0) { st.push([temp, 1]); if (temp.left != null) st.push([temp.left, 0]); } else if (b == 1) { st.push([temp, 2]); if (temp.right != null) st.push([temp.right, 0]); } else document.write(temp.data + " "); } } // Construct the below Binary Tree // 1 // / \ // 2 3 // / \ // 4 5 let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); iterativePostorder(root); </script>
Producción:
4 5 2 3 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por everythingispossible y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA