Dado un árbol binario , la tarea es imprimir todos los Nodes del árbol binario en Pre-order, Post-order y In-order en una iteración.
Ejemplos:
Aporte:
Salida:
Pedido previo: 1 2 4 5 3 6 7
Pedido posterior: 4 5 2 6 7 3 1
En pedido: 4 2 5 1 6 3 7Aporte:
Salida:
Pedido previo: 1 2 4 8 12 5 9 3 6 7 10 11
Pedido posterior: 12 8 4 9 5 2 6 10 11 7 3 1
En pedido: 8 12 4 2 9 5 1 6 3 10 7 11
Enfoque: La solución iterativa para este problema se proporciona en este artículo . Aquí este enfoque se basa en el concepto de recursividad .
La idea es colocar las llamadas recursivas correctamente como se hace para cada uno de los recorridos inorder, preorder y postorder .
Siga los pasos que se mencionan a continuación para resolver el problema.
- Cree 3 arrays para almacenar el recorrido en orden, en orden previo y en orden posterior.
- Empuje el Node actual en la array de preorden y llame a la función de recursión para el hijo izquierdo .
- Ahora empuje el Node actual en la array en orden y haga la llamada recursiva para el hijo correcto (subárbol derecho).
- Visite los datos del Node actual en la array posorden antes de salir de la recursividad actual.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
// Function for traversing tree using
// preorder postorder and inorder method
void PostPreInOrderInOneFlowRecursive(Node* root,
vector<int>& pre,
vector<int>& post,
vector<int>& in)
{
// Return if root is NULL
if (root == NULL)
return;
// Pushes the root data into the pre
// order vector
pre.push_back(root->data);
// Recursively calls for the left node
PostPreInOrderInOneFlowRecursive(
root->left, pre, post, in);
// Pushes node data into the inorder vector
in.push_back(root->data);
// Recursively calls for the right node
PostPreInOrderInOneFlowRecursive(
root->right, pre, post, in);
// Pushes the node data into the Post Order
// Vector
post.push_back(root->data);
}
// Driver Code
int main()
{
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->left->right
= new Node(12);
root->left->right->left = new Node(9);
root->right->right->left = new Node(10);
root->right->right->right = new Node(11);
// Declaring the vector function to store
// in, post, pre order values
vector<int> pre, post, in;
// Calling the function;
PostPreInOrderInOneFlowRecursive(
root, pre, post, in);
// Print the values of Pre order, Post order
// and In order
cout << "Pre Order : ";
for (auto i : pre) {
cout << i << " ";
}
cout << endl;
cout << "Post Order : ";
for (auto i : post) {
cout << i << " ";
}
cout << endl;
cout << "In Order : ";
for (auto i : in) {
cout << i << " ";
}
return 0;
}
Java
/*package whatever //do not write package name here */
// Java program for above approach
import java.io.*;
import java.util.*;
class GFG {
// Class of a tree node
static class Node {
public int data;
public Node left,right;
public Node(int val)
{
this.data = val;
this.left = null;
this.right = null;
}
};
// Function for traversing tree using
// preorder postorder and inorder method
static void PostPreInOrderInOneFlowRecursive(Node root,ArrayList<Integer> pre,ArrayList<Integer> post,ArrayList<Integer> in)
{
// Return if root is null
if (root == null)
return;
// Pushes the root data into the pre
// order vector
pre.add(root.data);
// Recursively calls for the left node
PostPreInOrderInOneFlowRecursive(root.left, pre, post, in);
// Pushes node data into the inorder vector
in.add(root.data);
// Recursively calls for the right node
PostPreInOrderInOneFlowRecursive(
root.right, pre, post, in);
// Pushes the node data into the Post Order
// Vector
post.add(root.data);
}
// Driver Code
public static void main(String args[])
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.left.right = new Node(12);
root.left.right.left = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
// Declaring the vector function to store
// in, post, pre order values
ArrayList<Integer> pre = new ArrayList<>();
ArrayList<Integer> post = new ArrayList<>();
ArrayList<Integer> in = new ArrayList<>();
// Calling the function;
PostPreInOrderInOneFlowRecursive(root, pre, post, in);
// Print the values of Pre order, Post order
// and In order
System.out.print("Pre Order : ");
for (int i : pre) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("Post Order : ");
for (int i : post) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("In Order : ");
for (int i : in) {
System.out.print(i + " ");
}
}
}
// This code is contributed by shinjanpatra
C#
//C# program to print all the nodes of the binary tree
//in Pre-order, Post-order, and In-order in one iteration.
using System;
using System.Collections.Generic;
public class GFG{
// Class of a tree node
class Node {
public int data;
public Node left,right;
public Node(int val)
{
this.data = val;
this.left = null;
this.right = null;
}
}
// Function for traversing tree using
// preorder postorder and inorder method
static void PostPreInOrderInOneFlowRecursive(Node root,List<int> pre,List<int> post,List<int> inOrder)
{
// Return if root is null
if (root == null)
return;
// Pushes the root data into the pre
// order vector
pre.Add(root.data);
// Recursively calls for the left node
PostPreInOrderInOneFlowRecursive(root.left, pre, post, inOrder);
// Pushes node data into the inorder vector
inOrder.Add(root.data);
// Recursively calls for the right node
PostPreInOrderInOneFlowRecursive(root.right, pre, post, inOrder);
// Pushes the node data into the Post Order
// Vector
post.Add(root.data);
}
// Driver Code
static public void Main (){
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.left.right = new Node(12);
root.left.right.left = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
// Declaring the vector function to store
// in, post, pre order values
List<int> pre = new List<int>();
List<int> post = new List<int>();
List<int> inOrder = new List<int>();
// Calling the function;
PostPreInOrderInOneFlowRecursive(root, pre, post, inOrder);
// Print the values of Pre order, Post order
// and In order
Console.Write("Pre Order : ");
foreach (var i in pre) {
Console.Write(i + " ");
}
Console.Write("\n");
Console.Write("Post Order : ");
foreach (var i in post) {
Console.Write(i + " ");
}
Console.Write("\n");
Console.Write("In Order : ");
foreach (var i in inOrder) {
Console.Write(i + " ");
}
}
}
//This code is contributed by shruti456rawal
Python3
# Python program for above approach
# Structure of a tree node
class Node:
def __init__(self,val):
self.data = val
self.left = None
self.right = None
# Function for traversing tree using
# preorder postorder and inorder method
def PostPreInOrderInOneFlowRecursive(root, pre, post, In):
# Return if root is None
if (root == None):
return
# Pushes the root data into the pre
# order vector
pre.append(root.data)
# Recursively calls for the left node
PostPreInOrderInOneFlowRecursive(root.left, pre, post, In)
# Pushes node data into the inorder vector
In.append(root.data)
# Recursively calls for the right node
PostPreInOrderInOneFlowRecursive(root.right, pre, post, In)
# Pushes the node data into the Post Order
# Vector
post.append(root.data)
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.left.right= Node(12)
root.left.right.left = Node(9)
root.right.right.left = Node(10)
root.right.right.right = Node(11)
# Declaring the vector function to store
# in, post, pre order values
pre,post,In = [],[],[]
# Calling the function
PostPreInOrderInOneFlowRecursive(root, pre, post, In)
# Print the values of Pre order, Post order
# and In order
print("Pre Order : ",end = "")
for i in pre:
print(i,end = " ")
print()
print("Post Order : ",end = "")
for i in post:
print(i,end = " ")
print()
print("In Order : ",end = "")
for i in In:
print(i,end = " ")
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program for above approach
// Structure of a tree node
class Node {
constructor(val)
{
this.data = val;
this.left = null;
this.right = null;
}
};
// Function for traversing tree using
// preorder postorder and inorder method
function PostPreInOrderInOneFlowRecursive(root,pre,post,In)
{
// Return if root is null
if (root == null)
return;
// Pushes the root data into the pre
// order vector
pre.push(root.data);
// Recursively calls for the left node
PostPreInOrderInOneFlowRecursive(root.left, pre, post, In);
// Pushes node data into the inorder vector
In.push(root.data);
// Recursively calls for the right node
PostPreInOrderInOneFlowRecursive(root.right, pre, post, In);
// Pushes the node data into the Post Order
// Vector
post.push(root.data);
}
// Driver Code
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.left.right= new Node(12);
root.left.right.left = new Node(9);
root.right.right.left = new Node(10);
root.right.right.right = new Node(11);
// Declaring the vector function to store
// in, post, pre order values
let pre = [], post = [], In = [];
// Calling the function;
PostPreInOrderInOneFlowRecursive(root, pre, post, In);
// Print the values of Pre order, Post order
// and In order
document.write("Pre Order : ");
for (let i of pre) {
document.write(i," ");
}
document.write("</br>");
document.write("Post Order : ");
for (let i of post) {
document.write(i," ");
}
document.write("</br>");
document.write("In Order : ");
for (let i of In) {
document.write(i," ");
}
// This code is contributed by shinjanpatra
</script>
Producción
Pre Order : 1 2 4 8 12 5 9 3 6 7 10 11 Post Order : 12 8 4 9 5 2 6 10 11 7 3 1 In Order : 8 12 4 2 9 5 1 6 3 10 7 11
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por thilakreddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA