Recorrido de Euler por el árbol binario

Dado un árbol binario donde cada Node puede tener como máximo dos Nodes secundarios, la tarea es encontrar el recorrido de Euler del árbol binario. El recorrido de Euler está representado por un puntero al Node superior del árbol. Si el árbol está vacío, el valor de la raíz es NULL.
Ejemplos: 
 

Aporte : 
 

Salida: 1 5 4 2 4 3 4 5 1 
 

Acercarse: 
 

(1) Primero, comience con el Node raíz 1, Euler[0]=1 
(2) Vaya al Node izquierdo, es decir, Node 5, Euler[1]=5 
(3) Vaya al Node izquierdo, es decir, Node 4, Euler[2 ]=4 
(4) Ir al Node izquierdo, es decir, Node 2, Euler[3]=2 
(5) Ir al Node izquierdo, es decir, NULL, ir al Node principal 4 Euler[4]=4 
(6) Ir al Node derecho es decir, Node 3 Euler[5]=3 
(7) Ningún hijo, ir al padre, Node 4 Euler[6]=4 
(8) Todos los hijos descubiertos, ir al Node padre 5 Euler[7]=5 
(9) Todos niño descubierto, vaya al Node padre 1 Euler[8]=1 
 

Ya se ha discutido el recorrido del árbol de Euler donde se puede aplicar al árbol N-ario que está representado por la lista de adyacencia. Si un árbol binario está representado por la forma clásica estructurada por enlaces y Nodes, primero es necesario convertir el árbol en una representación de lista de adyacencia y luego podemos encontrar el recorrido de Euler si queremos aplicar el método discutido en la publicación original. Pero esto aumenta la complejidad espacial del programa. Aquí, en esta publicación, se analiza una versión optimizada para el espacio generalizada que se puede aplicar directamente a árboles binarios representados por Nodes de estructura. 
Este método: 
(1) Funciona sin el uso de arrays visitadas. 
(2) Requiere exactamente 2*N-1 vértices para almacenar el recorrido de Euler.
 

C++

// C++ program to find euler tour of binary tree #include <bits/stdc++.h> using namespace std;    /* A tree node structure */ struct Node {     int data;     struct Node* left;     struct Node* right; };    /* Utility function to create a new Binary Tree node */ struct Node* newNode(int data) {     struct Node* temp = new struct Node;     temp->data = data;     temp->left = temp->right = NULL;     return temp; }    // Find Euler Tour void eulerTree(struct Node* root, vector<int> &Euler) {     // store current node's data     Euler.push_back(root->data);        // If left node exists     if (root->left)      {         // traverse left subtree         eulerTree(root->left, Euler);            // store parent node's data          Euler.push_back(root->data);     }        // If right node exists     if (root->right)      {         // traverse right subtree         eulerTree(root->right, Euler);             // store parent node's data         Euler.push_back(root->data);     } }    // Function to print Euler Tour of tree void printEulerTour(Node *root) {     // Stores Euler Tour     vector<int> Euler;         eulerTree(root, Euler);        for (int i = 0; i < Euler.size(); i++)         cout << Euler[i] << " "; }    /* Driver function to test above functions */ int main() {     // Constructing tree given in the above figure      Node* root = newNode(1);     root->left = newNode(2);     root->right = newNode(3);     root->left->left = newNode(4);     root->left->right = newNode(5);     root->right->left = newNode(6);     root->right->right = newNode(7);     root->right->left->right = newNode(8);        // print Euler Tour     printEulerTour(root);         return 0; }

Java

// Java program to find euler tour of binary tree import java.util.*;    class GFG {        /* A tree node structure */     static class Node     {         int data;         Node left;         Node right;     };        /* Utility function to create a new Binary Tree node */     static Node newNode(int data)     {         Node temp = new Node();         temp.data = data;         temp.left = temp.right = null;         return temp;     }        // Find Euler Tour     static Vector<Integer> eulerTree(Node root, Vector<Integer> Euler)     {         // store current node's data         Euler.add(root.data);            // If left node exists         if (root.left != null)         {             // traverse left subtree             Euler = eulerTree(root.left, Euler);                // store parent node's data             Euler.add(root.data);         }            // If right node exists         if (root.right != null)         {             // traverse right subtree             Euler = eulerTree(root.right, Euler);                // store parent node's data             Euler.add(root.data);         }         return Euler;     }        // Function to print Euler Tour of tree     static void printEulerTour(Node root)      {         // Stores Euler Tour         Vector<Integer> Euler = new Vector<Integer>();            Euler = eulerTree(root, Euler);            for (int i = 0; i < Euler.size(); i++)             System.out.print(Euler.get(i) + " ");     }        /* Driver function to test above functions */     public static void main(String[] args)     {         // Constructing tree given in the above figure         Node root = newNode(1);         root.left = newNode(2);         root.right = newNode(3);         root.left.left = newNode(4);         root.left.right = newNode(5);         root.right.left = newNode(6);         root.right.right = newNode(7);         root.right.left.right = newNode(8);            // print Euler Tour         printEulerTour(root);        } }    // This code is contributed by Rajput-Ji

Python3

# python program to find euler tour of binary tree # a Node of binary tree class Node:     def __init__(self, key):         self.data = key         self.left = None         self.right = None            # Find Euler Tree def eulerTree(root, euler):          #   store current node's data     euler.append(root.data)            # If left node exists     if root.left:                  # traverse left subtree         euler = eulerTree(root.left, euler)                    # store parent node's data         euler.append(root.data)                # If right node exists     if root.right:                  # traverse right subtree         euler = eulerTree(root.right, euler)                    # store parent node's data         euler.append(root.data)     return euler      # Function to print Euler Tour of tree def printEulerTour(root):          # Stores Euler Tour     euler = []     euler = eulerTree(root, euler)     for i in range(len(euler)):         print(euler[i], end=" ")    # Driver function to test above functions */ # Constructing tree given in the above figure 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.right.left.right = Node(8)    # print Euler Tour printEulerTour(root)    # This code is contributed by RAJAT KUMAR...(GLA UNIVERSITY)....

C#

// C# program to find euler tour of binary tree using System; using System.Collections.Generic;    class GFG {        /* A tree node structure */     public class Node     {         public int data;         public Node left;         public Node right;     };        /* Utility function to create a new Binary Tree node */     static Node newNode(int data)     {         Node temp = new Node();         temp.data = data;         temp.left = temp.right = null;         return temp;     }        // Find Euler Tour     static List<int> eulerTree(Node root, List<int> Euler)     {         // store current node's data         Euler.Add(root.data);            // If left node exists         if (root.left != null)         {             // traverse left subtree             Euler = eulerTree(root.left, Euler);                // store parent node's data             Euler.Add(root.data);         }            // If right node exists         if (root.right != null)         {             // traverse right subtree             Euler = eulerTree(root.right, Euler);                // store parent node's data             Euler.Add(root.data);         }         return Euler;     }        // Function to print Euler Tour of tree     static void printEulerTour(Node root)      {         // Stores Euler Tour         List<int> Euler = new List<int>();            Euler = eulerTree(root, Euler);            for (int i = 0; i < Euler.Count; i++)             Console.Write(Euler[i] + " ");     }        /* Driver function to test above functions */     public static void Main(String[] args)     {         // Constructing tree given in the above figure         Node root = newNode(1);         root.left = newNode(2);         root.right = newNode(3);         root.left.left = newNode(4);         root.left.right = newNode(5);         root.right.left = newNode(6);         root.right.right = newNode(7);         root.right.left.right = newNode(8);            // print Euler Tour         printEulerTour(root);        } }    // This code is contributed by 29AjayKumar

JavaScript

<script>    // Javascript program to find euler tour of binary tree /* A tree node structure */ class Node {     constructor()     {         this.data = 0;         this.left = null;         this.right = null;     } };    /* Utility function to create a new Binary Tree node */ function newNode(data) {     var temp = new Node();     temp.data = data;     temp.left = temp.right = null;     return temp; } // Find Euler Tour function eulerTree(root, Euler) {     // store current node's data     Euler.push(root.data);            // If left node exists     if (root.left != null)     {         // traverse left subtree         Euler = eulerTree(root.left, Euler);                    // store parent node's data         Euler.push(root.data);     }            // If right node exists     if (root.right != null)     {         // traverse right subtree         Euler = eulerTree(root.right, Euler);                    // store parent node's data         Euler.push(root.data);     }     return Euler; }    // Function to print Euler Tour of tree function printEulerTour(root)  {        // Stores Euler Tour     var Euler = [];     Euler = eulerTree(root, Euler);     for (var i = 0; i < Euler.length; i++)         document.write(Euler[i] + " "); }    /* Driver function to test above functions */ // Constructing tree given in the above figure var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8);    // print Euler Tour printEulerTour(root);    // This code is contributed by itsok. </script>

Producción: 

1 2 4 2 5 2 1 3 6 8 6 3 7 3 1

 

Complejidad de tiempo: O(2*N-1) donde N es el número de Nodes en el árbol. 
Espacio auxiliar: O(2*N-1) donde N es el número de Nodes en el árbol.