Recorrido de orden triple de un árbol binario

Dado un árbol binario , la tarea es encontrar su triple orden transversal .  

Triple Order Traversal es una técnica de recorrido de árbol en la que cada Node se recorre tres veces en el siguiente orden:  

• Visite el Node raíz
• Recorrer el subárbol izquierdo
• Visite el Node raíz
• Atraviesa el subárbol derecho
• Visite el Node raíz.

Ejemplos:

Input:
            A
           / \
          B   C
         / \   \
        F   D   E
       
Output: A B F F F B D D D B A C C E E E C A

Input:
            A
           / \
          B   C
         / \   
        E   D   
       /
      F
Output: A B E F F F E E B D D D B A C C C A 

Enfoque: 
siga los pasos a continuación para resolver el problema:  

• Inicie el recorrido desde la raíz .
• Si el Node actual no existe, simplemente regrese de él.
• De lo contrario:
  • Imprime el valor del Node actual .
  • Atraviesa recursivamente el subárbol izquierdo .
  • Nuevamente, imprima el Node actual .
  • Atraviesa recursivamente el subárbol derecho .
  • Nuevamente, imprima el Node actual .
• Repita los pasos anteriores hasta que se visiten todos los Nodes del árbol.

A continuación se muestra la implementación del enfoque anterior: 

// C++ Program to implement triple
// order traversal of a binary tree
#include <iostream>
using namespace std;
 
// Structure of a Node
struct node {
    char data;
    struct node *left, *right;
};
 
// Function to create new node
struct node* newNode(char ch)
{
    // Allocating a new node in the memory.
    struct node* Node = new node();
    Node->data = ch;
    Node->left = NULL;
    Node->right = NULL;
    return Node;
}
 
// Function to print Triple Order traversal
void tripleOrderTraversal(struct node* root)
{
    if (root) {
 
        // Print the current node
        cout << root->data << " ";
 
        // Traverse left subtree
        tripleOrderTraversal(root->left);
 
        // Print the current node
        cout << root->data << " ";
 
        // Traverse right subtree
        tripleOrderTraversal(root->right);
 
        // Print the current node
        cout << root->data << " ";
    }
}
 
// Driver Code
int main()
{
    struct node* root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('C');
    root->left->left = newNode('F');
    root->left->right = newNode('D');
    root->right->right = newNode('E');
 
    tripleOrderTraversal(root);
}

// Java program to implement triple
// order traversal of a binary tree
import java.util.*;
 
class GFG{
 
// Structure of a Node
static class node
{
    char data;
    node left, right;
};
 
// Function to create new node
static node newNode(char ch)
{
     
    // Allocating a new node in the memory.
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Function to print Triple Order traversal
static void tripleOrderTraversal(node root)
{
    if (root != null)
    {
         
        // Print the current node
        System.out.print(root.data + " ");
 
        // Traverse left subtree
        tripleOrderTraversal(root.left);
 
        // Print the current node
        System.out.print(root.data + " ");
 
        // Traverse right subtree
        tripleOrderTraversal(root.right);
 
        // Print the current node
        System.out.print(root.data + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    node root = newNode('A');
    root.left = newNode('B');
    root.right = newNode('C');
    root.left.left = newNode('F');
    root.left.right = newNode('D');
    root.right.right = newNode('E');
 
    tripleOrderTraversal(root);
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program to implement triple
# order traversal of a binary tree
 
# Structure of node
class Node:
     
    # Initialise the node
    def __init__(self, ch):
         
        self.data = ch
        self.left = None
        self.right = None
         
# Function to print the Triple Order Traversal
def tripleOrderTraversal(root):
     
    if root:
         
        # Print the current node
        print(root.data, end = ' ')
         
        # Print the left subtree
        tripleOrderTraversal(root.left)
         
        # Print the current node
        print(root.data, end = ' ')
         
        # Print the right subtree
        tripleOrderTraversal(root.right)
         
        # Print the current node
        print(root.data, end = ' ')
         
# Driver code
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('F')
root.left.right = Node('D')
root.right.right = Node('E')
 
tripleOrderTraversal(root)
     
# This code is contributed by Stuti Pathak

// C# program to implement triple
// order traversal of a binary tree
using System;
 
class GFG{
 
// Structure of a Node
public class node
{
    public char data;
    public node left, right;
};
 
// Function to create new node
static node newNode(char ch)
{
     
    // Allocating a new node in the memory.
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Function to print Triple Order traversal
static void tripleOrderTraversal(node root)
{
    if (root != null)
    {
         
        // Print the current node
        Console.Write(root.data + " ");
 
        // Traverse left subtree
        tripleOrderTraversal(root.left);
 
        // Print the current node
        Console.Write(root.data + " ");
 
        // Traverse right subtree
        tripleOrderTraversal(root.right);
 
        // Print the current node
        Console.Write(root.data + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    node root = newNode('A');
    root.left = newNode('B');
    root.right = newNode('C');
    root.left.left = newNode('F');
    root.left.right = newNode('D');
    root.right.right = newNode('E');
 
    tripleOrderTraversal(root);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// javascript Program to implement triple
// order traversal of a binary tree
 
// Structure of a Node
class node {
 
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Function to create new node
function newNode(ch)
{
    // Allocating a new node in the memory.
    var n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Function to print Triple Order traversal
function tripleOrderTraversal(root)
{
    if (root) {
 
        // Print the current node
        document.write( root.data + " ");
 
        // Traverse left subtree
        tripleOrderTraversal(root.left);
 
        // Print the current node
        document.write( root.data + " ");
 
        // Traverse right subtree
        tripleOrderTraversal(root.right);
 
        // Print the current node
        document.write( root.data + " ");
    }
}
 
// Driver Code
var root = newNode('A');
root.left = newNode('B');
root.right = newNode('C');
root.left.left = newNode('F');
root.left.right = newNode('D');
root.right.right = newNode('E');
tripleOrderTraversal(root);
 
 
</script>

A B F F F B D D D B A C C E E E C A

Complejidad de tiempo: O(N),  donde N es el número total de Nodes en el árbol binario. Espacio auxiliar: O(N) Aplicaciones: El recorrido de Euler por un árbol es una versión modificada del recorrido de triple orden.