Implementar traversal post-fin usando el programa C ++

En este artículo, vamos a aprender, cómo implementar recorrido posterior a la orden usando el programa C ++ ? Este programa contiene diferentes métodos, algoritmos y ejemplos.

En post-orden transversal el subárbol izquierdo es primero entonces el subárbol derecho y más tarde a continuación, la raíz es decir, en el orden LRN (Nodo Izquierda Derecha) donde nodo es el nodo actual.

Aquí,
L (recursivamente traverse subárbol izquierdo)
R (recursivamente traverse derecho subárbol)
N (proceso de nodo es decir raíz actual)

A post-orden transversal lata puede hacer de dos maneras:

1. por el método recursivo

Algoritmo:

postorder(root)
a. Traverse the left subtree (inorder(root->left))
b. Traverse the right subtree (inorder(root->right))
c. visit the root

2. por método no recursivo

Este método se implementa mediante el uso de la pila.

a. push root into the ‘post’ (first stack)    
b. repeat while ‘post’ is not empty
1. pop the node from ‘post’ and push it to ‘pout’ (second stack)
2. push the left and right child of the node to ‘post’
c. print the elements of ‘pout’

C ++ código para implementar post-orden transversal

#include<iostream>
#include<stack>
using namespace std;

struct node
{
int info;
node *left,*right;
};

node *newNode(int n)
{
node *ptr=new node;
ptr->info=n;
ptr->left=ptr->right=NULL;
return ptr;
}

node *insert(node* node,int info)
{
if(node==NULL)
{
return newNode(info);
}
if(info < node->info)
{
node->left=insert(node->left,info);
}
else
{
node->right=insert(node->right,info);
}
return node;
}

void postorder(node *root)
{
stack<node*> post;
post.push(root);
stack<int> pout;
while(!post.empty())
{
node *curr=post.top();
post.pop();
pout.push(curr->info);
if(curr->left)
{
post.push(curr->left);
}
if(curr->right)
{
post.push(curr->right);
}
}
cout<<"PostOrder traversal :";
while(!pout.empty())
{
cout<<pout.top()<<" ";
pout.pop();
}
}
//Main program
int main()
{
node* root=newNode(60);
insert(root,50);
insert(root,70);
insert(root,40);
insert(root,30);
insert(root,80);
insert(root,75);
insert(root,65);
insert(root,45);
insert(root,55);
insert(root,90);
insert(root,67);

postorder(root);
cout<<endl;
return 0;
}

salida

PostOrder traversal :30 45 40 55 50 67 65 90 80 75 70 60


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *