Dado un árbol N-ario, la tarea es encontrar iterativamente el recorrido posterior al orden del árbol dado.
Ejemplos:
Input:
1
/ | \
3 2 4
/ \
5 6
Output: [5, 6, 3, 2, 4, 1]
Input:
1
/ \
2 3
Output: [2, 3, 1]
Enfoque:
ya hemos discutido el recorrido iterativo posterior al pedido del árbol binario usando una pila . Extenderemos ese enfoque para el árbol n-ario. La idea es muy simple, para cada Node tenemos que atravesar todos los hijos de este Node (de izquierda a derecha) antes de atravesar el Node.
Pseudocódigo:
- Empezar desde la raíz.
- Repita todos los pasos a continuación hasta que root != null OR stack no esté vacío.
- Si root != null, empuje root y es un índice en la pila y continúa hacia el Node izquierdo.
- Extraiga el elemento de la pila e imprímalo.
- Saque todos los elementos de la pila hasta que la pila no esté vacía && el Node sacado es el último hijo de
su padre. - Asigne la raíz a los siguientes elementos secundarios del Node de la parte superior de la pila.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to iterative Postorder
// Traversal of N-ary Tree
#include<bits/stdc++.h>
using namespace std;
// Node class
class Node
{
public :
int val;
vector<Node*> children ;
// Default constructor
Node() {}
Node(int _val)
{
val = _val;
}
Node(int _val, vector<Node*> _children)
{
val = _val;
children = _children;
}
};
// Helper class to push node and it's index
// into the st
class Pair
{
public:
Node* node;
int childrenIndex;
Pair(Node* _node, int _childrenIndex)
{
node = _node;
childrenIndex = _childrenIndex;
}
};
// We will keep the start index as 0,
// because first we always
// process the left most children
int currentRootIndex = 0;
stack<Pair*> st;
vector<int> postorderTraversal ;
// Function to perform iterative postorder traversal
vector<int> postorder(Node* root)
{
while (root != NULL || st.size() > 0)
{
if (root != NULL)
{
// Push the root and it's index
// into the st
st.push(new Pair(root, currentRootIndex));
currentRootIndex = 0;
// If root don't have any children's that
// means we are already at the left most
// node, so we will mark root as NULL
if (root->children.size() >= 1)
{
root = root->children[0];
}
else
{
root = NULL;
}
continue;
}
// We will pop the top of the st and
// push_back it to our answer
Pair* temp = st.top();
st.pop();
postorderTraversal.push_back(temp->node->val);
// Repeatedly we will the pop all the
// elements from the st till popped
// element is last children of top of
// the st
while (st.size() > 0 && temp->childrenIndex ==
st.top()->node->children.size() - 1)
{
temp = st.top();
st.pop();
postorderTraversal.push_back(temp->node->val);
}
// If st is not empty, then simply assign
// the root to the next children of top
// of st's node
if (st.size() > 0)
{
root = st.top()->node->children[temp->childrenIndex + 1];
currentRootIndex = temp->childrenIndex + 1;
}
}
return postorderTraversal;
}
// Driver Code
int main()
{
Node* root = new Node(1);
root->children.push_back(new Node(3));
root->children.push_back(new Node(2));
root->children.push_back(new Node(4));
root->children[0]->children.push_back(new Node(5));
root->children[0]->children.push_back(new Node(6));
vector<int> v = postorder(root);
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
}
// This code is contributed by Arnab Kundu
Java
// Node class
static class Node {
public int val;
public List<Node> children = new ArrayList<Node>();
// Default constructor
public Node() {}
public Node(int _val)
{
val = _val;
}
public Node(int _val, List<Node> _children)
{
val = _val;
children = _children;
}
};
// Helper class to push node and it's index
// into the stack
static class Pair {
public Node node;
public int childrenIndex;
public Pair(Node _node, int _childrenIndex)
{
node = _node;
childrenIndex = _childrenIndex;
}
}
// We will keep the start index as 0,
// because first we always
// process the left most children
int currentRootIndex = 0;
Stack<Pair> stack = new Stack<Pair>();
ArrayList<Integer> postorderTraversal =
new ArrayList<Integer>();
// Function to perform iterative postorder traversal
public ArrayList<Integer> postorder(Node root)
{
while (root != null || !stack.isEmpty()) {
if (root != null) {
// Push the root and it's index
// into the stack
stack.push(new Pair(root, currentRootIndex));
currentRootIndex = 0;
// If root don't have any children's that
// means we are already at the left most
// node, so we will mark root as null
if (root.children.size() >= 1) {
root = root.children.get(0);
}
else {
root = null;
}
continue;
}
// We will pop the top of the stack and
// add it to our answer
Pair temp = stack.pop();
postorderTraversal.add(temp.node.val);
// Repeatedly we will the pop all the
// elements from the stack till popped
// element is last children of top of
// the stack
while (!stack.isEmpty() && temp.childrenIndex ==
stack.peek().node.children.size() - 1) {
temp = stack.pop();
postorderTraversal.add(temp.node.val);
}
// If stack is not empty, then simply assign
// the root to the next children of top
// of stack's node
if (!stack.isEmpty()) {
root = stack.peek().node.children.get(
temp.childrenIndex + 1);
currentRootIndex = temp.childrenIndex + 1;
}
}
return postorderTraversal;
}
// Driver Code
public static void main(String[] args)
{
GFG solution = new GFG();
Node root = new Node(1);
root.children.add(new Node(3));
root.children.add(new Node(2));
root.children.add(new Node(4));
root.children.get(0).children.add(new Node(5));
root.children.get(0).children.add(new Node(6));
System.out.println(solution.postorder(root));
}
}
Python3
# Python Program to iterative
# Postorder Traversal of N-ary Tree
# Node class
class Node:
def __init__(self,_val):
self.val = _val
self.children = []
# Helper class to.append node and it's index
# into the stack
class Pair:
def __init__(self,_node, _childrenIndex):
self.node = _node
self.childrenIndex = _childrenIndex
# We will keep the start index as 0,
# because first we always
# process the left most children
currentRootIndex = 0
stack = []
postorderTraversal = []
# Function to perform iterative postorder traversal
def postorder(root):
global currentRootIndex
global stack
global postorderTraversal
while (root != None or len(stack) != 0):
if (root != None):
# append the root and it's index
# into the stack
stack.append(Pair(root, currentRootIndex))
currentRootIndex = 0
# If root don't have any children's that
# means we are already at the left most
# node, so we will mark root as None
if (len(root.children) >= 1):
root = root.children[0]
else:
root = None
continue
# We will.Pop the top of the stack and
#.append it to our answer
temp = stack.pop()
postorderTraversal.append(temp.node.val)
# Repeatedly we will the.Pop all the
# elements from the stack till.Popped
# element is last children of top of
# the stack
while (len(stack) != 0 and temp.childrenIndex ==
len(stack[-1].node.children) - 1):
temp = stack[-1]
stack.pop()
postorderTraversal.append(temp.node.val)
# If stack is not empty, then simply assign
# the root to the next children of top
# of stack's node
if (len(stack) != 0):
root = stack[-1].node.children[temp.childrenIndex + 1]
currentRootIndex = temp.childrenIndex + 1
return postorderTraversal
# Driver Code
root = Node(1)
root.children.append(Node(3))
root.children.append(Node(2))
root.children.append(Node(4))
root.children[0].children.append(Node(5))
root.children[0].children.append(Node(6))
print("[",end="")
temp = postorder(root)
size = len(temp)
count = 0
for v in temp:
print(v,end="")
count += 1
if(count < size):
print(",",end=" ")
print("]")
# This code is contributed by shinjanpatra
C#
// C# Program to iterative Postorder Traversal of N-ary Tree
using System;
using System.Collections.Generic;
class GFG
{
// Node class
public class Node
{
public int val;
public List<Node> children = new List<Node>();
// Default constructor
public Node() {}
public Node(int _val)
{
val = _val;
}
public Node(int _val, List<Node> _children)
{
val = _val;
children = _children;
}
};
// Helper class to.Push node and it's index
// into the stack
class Pair
{
public Node node;
public int childrenIndex;
public Pair(Node _node, int _childrenIndex)
{
node = _node;
childrenIndex = _childrenIndex;
}
}
// We will keep the start index as 0,
// because first we always
// process the left most children
int currentRootIndex = 0;
Stack<Pair> stack = new Stack<Pair>();
List<int> postorderTraversal =
new List<int>();
// Function to perform iterative postorder traversal
public List<int> postorder(Node root)
{
while (root != null || stack.Count != 0)
{
if (root != null)
{
// Push the root and it's index
// into the stack
stack.Push(new Pair(root, currentRootIndex));
currentRootIndex = 0;
// If root don't have any children's that
// means we are already at the left most
// node, so we will mark root as null
if (root.children.Count >= 1)
{
root = root.children[0];
}
else
{
root = null;
}
continue;
}
// We will.Pop the top of the stack and
//.Add it to our answer
Pair temp = stack.Pop();
postorderTraversal.Add(temp.node.val);
// Repeatedly we will the.Pop all the
// elements from the stack till.Popped
// element is last children of top of
// the stack
while (stack.Count != 0 && temp.childrenIndex ==
stack.Peek().node.children.Count - 1)
{
temp = stack.Pop();
postorderTraversal.Add(temp.node.val);
}
// If stack is not empty, then simply assign
// the root to the next children of top
// of stack's node
if (stack.Count != 0)
{
root = stack.Peek().node.children[temp.childrenIndex + 1];
currentRootIndex = temp.childrenIndex + 1;
}
}
return postorderTraversal;
}
// Driver Code
public static void Main(String[] args)
{
GFG solution = new GFG();
Node root = new Node(1);
root.children.Add(new Node(3));
root.children.Add(new Node(2));
root.children.Add(new Node(4));
root.children[0].children.Add(new Node(5));
root.children[0].children.Add(new Node(6));
Console.Write("[");
List<int> temp = solution.postorder(root);
int size = temp.Count;
int count = 0;
foreach(int v in temp)
{
Console.Write(v);
count++;
if(count < size)
Console.Write(", ");
}
Console.Write("]");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript Program to iterative
// Postorder Traversal of N-ary Tree
// Node class
class Node
{
constructor(_val)
{
this.val = _val;
this.children = [];
}
};
// Helper class to.Push node and it's index
// into the stack
class Pair
{
constructor(_node, _childrenIndex)
{
this.node = _node;
this.childrenIndex = _childrenIndex;
}
}
// We will keep the start index as 0,
// because first we always
// process the left most children
var currentRootIndex = 0;
var stack = [];
var postorderTraversal = [];
// Function to perform iterative postorder traversal
function postorder(root)
{
while (root != null || stack.length != 0)
{
if (root != null)
{
// Push the root and it's index
// into the stack
stack.push(new Pair(root, currentRootIndex));
currentRootIndex = 0;
// If root don't have any children's that
// means we are already at the left most
// node, so we will mark root as null
if (root.children.length >= 1)
{
root = root.children[0];
}
else
{
root = null;
}
continue;
}
// We will.Pop the top of the stack and
//.push it to our answer
var temp = stack.pop();
postorderTraversal.push(temp.node.val);
// Repeatedly we will the.Pop all the
// elements from the stack till.Popped
// element is last children of top of
// the stack
while (stack.length != 0 && temp.childrenIndex ==
stack[stack.length-1].node.children.Count - 1)
{
temp = stack.pop();
postorderTraversal.push(temp.node.val);
}
// If stack is not empty, then simply assign
// the root to the next children of top
// of stack's node
if (stack.length != 0)
{
root = stack[stack.length-1].node.children[temp.childrenIndex + 1];
currentRootIndex = temp.childrenIndex + 1;
}
}
return postorderTraversal;
}
// Driver Code
var root = new Node(1);
root.children.push(new Node(3));
root.children.push(new Node(2));
root.children.push(new Node(4));
root.children[0].children.push(new Node(5));
root.children[0].children.push(new Node(6));
document.write("[");
var temp = postorder(root);
var size = temp.length;
var count = 0;
for(var v of temp)
{
document.write(v);
count++;
if(count < size)
document.write(", ");
}
document.write("]");
</script>
Producción:
[5, 6, 3, 2, 4, 1]
Complejidad temporal : O(n) donde n no es ningún Node en un árbol binario
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