Dado un árbol binario que consta de N Nodes, la tarea es imprimir su recorrido de doble orden.
Double Order Traversal es una técnica de recorrido de árbol en la que cada Node se recorre dos veces en el siguiente orden:
- Visita el Node.
- Atraviesa el subárbol izquierdo.
- Visita el Node.
- Atraviesa el subárbol derecho.
Ejemplos:
Input:
1
/ \
7 3
/ \ /
4 5 6
Output: 1 7 4 4 7 5 5 1 3 6 6 3
Input:
1
/ \
7 3
/ \ \
4 5 6
Output: 1 7 4 4 7 5 5 1 3 3 6 6
Enfoque:
la idea es realizar Inorder Traversal de forma recursiva en el árbol binario dado e imprimir el valor del Node al visitar un vértice y después de la llamada recursiva al subárbol izquierdo durante el recorrido.
Siga los pasos a continuación para resolver el problema:
- Inicie el recorrido en orden 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.
- 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++
// C++ Program to implement
// the above approach
#include <iostream>
using namespace std;
// Node Structure
struct node {
char data;
struct node *left, *right;
};
// Function to create new node
struct node* newNode(char ch)
{
// Allocate a new node in memory
struct node* Node = new node();
Node->data = ch;
Node->left = NULL;
Node->right = NULL;
return Node;
}
// Function to print Double Order traversal
void doubleOrderTraversal(struct node* root)
{
if (!root)
return;
// Print Node Value
cout << root->data << " ";
// Traverse Left Subtree
doubleOrderTraversal(root->left);
// Print Node Value
cout << root->data << " ";
// Traverse Right SubTree
doubleOrderTraversal(root->right);
}
// Driver Code
int main()
{
struct node* root = newNode('1');
root->left = newNode('7');
root->right = newNode('3');
root->left->left = newNode('4');
root->left->right = newNode('5');
root->right->right = newNode('6');
doubleOrderTraversal(root);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Node Structure
static class node
{
char data;
node left, right;
};
// Function to create new node
static node newNode(char ch)
{
// Allocate a new node in memory
node n = new node();
n.data = ch;
n.left = null;
n.right = null;
return n;
}
// Function to print Double Order traversal
static void doubleOrderTraversal(node root)
{
if (root == null)
return;
// Print Node Value
System.out.print(root.data + " ");
// Traverse Left Subtree
doubleOrderTraversal(root.left);
// Print Node Value
System.out.print(root.data + " ");
// Traverse Right SubTree
doubleOrderTraversal(root.right);
}
// Driver Code
public static void main(String[] args)
{
node root = newNode('1');
root.left = newNode('7');
root.right = newNode('3');
root.left.left = newNode('4');
root.left.right = newNode('5');
root.right.right = newNode('6');
doubleOrderTraversal(root);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Node Structure class Node: # Initialise new node def __init__(self, ch): self.data = ch self.left = None self.right = None # Function to print Double Order traversal def doubleOrderTraveersal(root): if not root: return # Print node value print(root.data, end = " ") # Traverse left subtree doubleOrderTraveersal(root.left) # Print node value print(root.data, end = " ") # Traverse right subtree doubleOrderTraveersal(root.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(7) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) doubleOrderTraveersal(root) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Node Structure
class node
{
public char data;
public node left, right;
};
// Function to create new node
static node newNode(char ch)
{
// Allocate a new node in memory
node n = new node();
n.data = ch;
n.left = null;
n.right = null;
return n;
}
// Function to print Double Order traversal
static void doubleOrderTraversal(node root)
{
if (root == null)
return;
// Print Node Value
Console.Write(root.data + " ");
// Traverse Left Subtree
doubleOrderTraversal(root.left);
// Print Node Value
Console.Write(root.data + " ");
// Traverse Right SubTree
doubleOrderTraversal(root.right);
}
// Driver Code
public static void Main(String[] args)
{
node root = newNode('1');
root.left = newNode('7');
root.right = newNode('3');
root.left.left = newNode('4');
root.left.right = newNode('5');
root.right.right = newNode('6');
doubleOrderTraversal(root);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
// Node Structure
class node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Function to create new node
function newNode(ch)
{
// Allocate a new node in memory
var n = new node();
n.data = ch;
n.left = null;
n.right = null;
return n;
}
// Function to print Double Order traversal
function doubleOrderTraversal(root)
{
if (root == null)
return;
// Print Node Value
document.write(root.data + " ");
// Traverse Left Subtree
doubleOrderTraversal(root.left);
// Print Node Value
document.write(root.data + " ");
// Traverse Right SubTree
doubleOrderTraversal(root.right);
}
// Driver Code
var root = newNode('1');
root.left = newNode('7');
root.right = newNode('3');
root.left.left = newNode('4');
root.left.right = newNode('5');
root.right.right = newNode('6');
doubleOrderTraversal(root);
</script>
Producción:
1 7 4 4 7 5 5 1 3 3 6 6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA