Recorrido de orden de mezcla de un árbol binario

Dado un Árbol Binario que consta de N Nodes, la tarea es imprimir su Recorrido de Orden de Mezcla.

Mix Order Traversal es una técnica de Tree Traversal , que involucra dos de las técnicas transversales existentes como Inorder, Preorder y Postorder Traversal. Se pueden realizar dos de ellos o se pueden alternar los niveles de un árbol dado y se puede obtener un recorrido mixto.

Ejemplos:

Entrada: N = 6

Salida: 7 4 5 1 3 6
Explicación:
El recorrido combinado en orden previo se aplica al árbol dado en el siguiente orden:
El recorrido en orden se aplica en el nivel 0 El recorrido en orden previo
se aplica en el nivel 1
El recorrido en orden en el nivel 2.

Salida: 4 5 7 1 6 3
Explicación:
El recorrido mixto en orden-posterior se aplica al árbol dado en el siguiente orden:
El recorrido en orden se aplica en el nivel 0
El recorrido en orden se aplica en el nivel 1
El recorrido en orden en el nivel 2.

Enfoque:
Los posibles cruces de orden de mezcla son los siguientes:

Recorrido de mezcla en orden-pre-pedido

Los pasos para inorder() serán:

Realice Preorder Traversal en el subárbol izquierdo .
Imprime el Node actual .
Realice Preorder Traversal en el subárbol derecho .

Los pasos para el pedido anticipado() serán:

Imprime el Node actual .
Realice Inorder Traversal en el subárbol izquierdo (raíz->izquierda).
Realice Inorder Traversal en el subárbol derecho .

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
void inOrder(struct node* root);
void preOrder(struct node* root);
 
// Node structure
struct node {
    char data;
    struct node *left, *right;
};
 
// Creates and initialize a new node
struct node* newNode(char ch)
{
    // Allocating memory to a new node
    struct node* n = (struct node*)
        malloc(sizeof(struct node));
    n->data = ch;
    n->left = NULL;
    n->right = NULL;
    return n;
}
 
// Perform Inorder Traversal
void inOrder(struct node* root)
{
    if (root) {
        preOrder(root->left);
        cout << root->data << " ";
        preOrder(root->right);
    }
}
 
// Perform Preorder Traversal
void preOrder(struct node* root)
{
    if (root) {
        cout << root->data << " ";
        inOrder(root->left);
        inOrder(root->right);
    }
}
 
// Driver Code
int main()
{
    // Given tree
    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->left = newNode('6');
 
    // Perform Mix order traversal
    inOrder(root);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Node structure
static class node
{
    char data;
    node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
     
    // Allocating memory to a new node
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Inorder Traversal
static void inOrder(node root)
{
    if (root != null)
    {
        preOrder(root.left);
        System.out.print(root.data + " ");
        preOrder(root.right);
    }
}
 
// Perform Preorder Traversal
static void preOrder(node root)
{
    if (root != null)
    {
        System.out.print(root.data + " ");
        inOrder(root.left);
        inOrder(root.right);
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given tree
    node root = newNode('1');
    root.left = newNode('7');
    root.right = newNode('3');
    root.left.left = newNode('4');
    root.left.right = newNode('5');
    root.right.left = newNode('6');
 
    // Perform Mix order traversal
    inOrder(root);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement the above approach
 
# Node structure
class node:
    def __init__(self):
        self.data = 0
        self.left = None
        self.right = None
 
# Creates and initialize a new node
def newNode(ch):
   
    # Allocating memory to a new node
    n = node()
    n.data = ch
    n.left = None
    n.right = None
    return n
  
# Perform Inorder Traversal
def inOrder(root):
    if root != None:
        preOrder(root.left)
        print(root.data, end = " ")
        preOrder(root.right)
  
# Perform Preorder Traversal
def preOrder(root):
    if root != None:
        print(root.data, end = " ")
        inOrder(root.left)
        inOrder(root.right)
 
# Driver Code
# Given tree
root = newNode('1')
root.left = newNode('7')
root.right = newNode('3')
root.left.left = newNode('4')
root.left.right = newNode('5')
root.right.left = newNode('6')
 
# Perform Mix order traversal
inOrder(root)
 
# This code is contributed by divyeshrabadiya07.

C#

// C# program to implement
// the above approach
using System;
class GFG{
 
// Node structure
class node
{
    public char data;
    public node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
     
    // Allocating memory to a new node
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Inorder Traversal
static void inOrder(node root)
{
    if (root != null)
    {
        preOrder(root.left);
        Console.Write(root.data + " ");
        preOrder(root.right);
    }
}
 
// Perform Preorder Traversal
static void preOrder(node root)
{
    if (root != null)
    {
        Console.Write(root.data + " ");
        inOrder(root.left);
        inOrder(root.right);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given tree
    node root = newNode('1');
    root.left = newNode('7');
    root.right = newNode('3');
    root.left.left = newNode('4');
    root.left.right = newNode('5');
    root.right.left = newNode('6');
 
    // Perform Mix order traversal
    inOrder(root);
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Node structure
class node
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right =  null;
    }
};
 
// Creates and initialize a new node
function newNode(ch)
{
     
    // Allocating memory to a new node
    var n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Inorder Traversal
function inOrder(root)
{
    if (root != null)
    {
        preOrder(root.left);
        document.write(root.data + " ");
        preOrder(root.right);
    }
}
 
// Perform Preorder Traversal
function preOrder(root)
{
    if (root != null)
    {
        document.write(root.data + " ");
        inOrder(root.left);
        inOrder(root.right);
    }
}
 
// Driver Code
// Given tree
var root = newNode('1');
root.left = newNode('7');
root.right = newNode('3');
root.left.left = newNode('4');
root.left.right = newNode('5');
root.right.left = newNode('6');
// Perform Mix order traversal
inOrder(root);
 
 
</script>

Producción:

7 4 5 1 3 6

Preorder-Postorder Mix Traversal

Los pasos para preorder() son los siguientes:

Imprime el Node actual .
Realice un recorrido posterior al pedido en el subárbol izquierdo .
Realice Postorder Traversal en el subárbol derecho .

Los pasos para postorder() son los siguientes:

Realice un recorrido de preorden en el subárbol izquierdo .
Realice un recorrido de preorden en el subárbol derecho .
Imprime el Node actual.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
void preOrder(struct node* root);
void postOrder(struct node* root);
 
// Node structure
struct node {
    char data;
    struct node *left, *right;
};
 
// Creates and initialize a new node
struct node* newNode(char ch)
{
    // Allocating memory to a new node
    struct node* n = (struct node*)
        malloc(sizeof(struct node));
    n->data = ch;
    n->left = NULL;
    n->right = NULL;
    return n;
}
 
// Perform Preorder Traversal
void preOrder(struct node* root)
{
    if (root) {
        cout << root->data << " ";
        postOrder(root->left);
        postOrder(root->right);
    }
}
 
// Perform Postorder Traversal
void postOrder(struct node* root)
{
    if (root) {
        preOrder(root->left);
        preOrder(root->right);
        cout << root->data << " ";
    }
}
 
// Driver Code
int main()
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    preOrder(root);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
class GFG{
 
// Node structure
static class node
{
    char data;
    node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
    // Allocating memory to a new node
    node n = new node();
      
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Preorder Traversal
static void preOrder(node root)
{
    if (root != null)
    {
        System.out.print(root.data + " ");
        postOrder(root.left);
        postOrder(root.right);
    }
}
 
// Perform Postorder Traversal
static void postOrder(node root)
{
    if (root != null)
    {
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.data + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    preOrder(root);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 Program to implement the above approach
 
# Node structure
class node:
    def __init__(self):
        self.data = '0'
        self.left = None
        self.right = None
 
# Creates and initialize a new node
def newNode(ch):
    # Allocating memory to a new node
    n = node()
 
    n.data = ch
    n.left = None
    n.right = None
    return n
 
# Perform Preorder Traversal
def preOrder(root):
    if root != None:
        print(root.data,  end = " ")
        postOrder(root.left)
        postOrder(root.right)
 
# Perform Postorder Traversal
def postOrder(root):
    if root != None:
        preOrder(root.left)
        preOrder(root.right)
        print(root.data, end = " ")
 
# Given tree
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')
 
# Starting Mix order traversal
preOrder(root)
 
# This code is contributed by divyesh072019.

C#

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Node structure
class node
{
    public char data;
    public node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
    // Allocating memory to a new node
    node n = new node();
      
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Preorder Traversal
static void preOrder(node root)
{
    if (root != null)
    {
        Console.Write(root.data + " ");
        postOrder(root.left);
        postOrder(root.right);
    }
}
 
// Perform Postorder Traversal
static void postOrder(node root)
{
    if (root != null)
    {
        preOrder(root.left);
        preOrder(root.right);
        Console.Write(root.data + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    preOrder(root);
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
    // Javascript Program to implement the above approach
     
    // Node structure
    class node
    {
        constructor() {
           this.left;
           this.right;
           this.data;
        }
    }
     
    // Creates and initialize a new node
    function newNode(ch)
    {
        // Allocating memory to a new node
        let n = new node();
 
        n.data = ch;
        n.left = null;
        n.right = null;
        return n;
    }
 
    // Perform Preorder Traversal
    function preOrder(root)
    {
        if (root != null)
        {
            document.write(root.data + " ");
            postOrder(root.left);
            postOrder(root.right);
        }
    }
 
    // Perform Postorder Traversal
    function postOrder(root)
    {
        if (root != null)
        {
            preOrder(root.left);
            preOrder(root.right);
            document.write(root.data + " ");
        }
    }
     
    // Given tree
    let 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');
  
    // Starting Mix order traversal
    preOrder(root);
     
    // This code is contributed by rameshtravel07.
</script>

Producción:

A F D B E C

Recorrido de mezcla en orden-postorden

Los pasos para inorder() son los siguientes:

Realice Postorder Traversal en el subárbol izquierdo .
Imprime el Node actual .
Realice Postorder Traversal en el subárbol derecho.

Los pasos para postorder() serán:

Realice Inorder Traversal en el subárbol izquierdo .
Realice Inorder Traversal en el subárbol derecho .
Imprime el Node actual .

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
void inOrder(struct node* root);
void postOrder(struct node* root);
 
// Node structure
struct node {
    char data;
    struct node *left, *right;
};
 
// Creates and initialize a new node
struct node* newNode(char ch)
{
 
    // Allocating memory to a new node
    struct node* n = (struct node*)
        malloc(sizeof(struct node));
    n->data = ch;
    n->left = NULL;
    n->right = NULL;
    return n;
}
 
// Perform Inorder Traversal
void inOrder(struct node* root)
{
    if (root) {
        postOrder(root->left);
        cout << root->data << " ";
        postOrder(root->right);
    }
}
 
// Perform Postorder Traversal
void postOrder(struct node* root)
{
    if (root) {
        inOrder(root->left);
        inOrder(root->right);
        cout << root->data << " ";
    }
}
 
// Driver Code
int main()
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    inOrder(root);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
// Node structure
static class node
{
    char data;
    node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
 
    // Allocating memory to a new node
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Inorder Traversal
static void inOrder(node root)
{
    if (root != null)
    {
        postOrder(root.left);
        System.out.print(root.data + " ");
        postOrder(root.right);
    }
}
 
// Perform Postorder Traversal
static void postOrder(node root)
{
    if (root != null)
    {
        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.data + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    inOrder(root);
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 Program to implement the above approach
 
# Node structure
class node:
    def __init__(self):
        self.data = '0'
        self.left = None
        self.right = None
 
# Creates and initialize a new node
def newNode(ch):
    # Allocating memory to a new node
    n = node()
    n.data = ch
    n.left = None
    n.right = None
    return n
 
# Perform Inorder Traversal
def inOrder(root):
    if root != None:
        postOrder(root.left)
        print(root.data, end = " ")
        postOrder(root.right)
 
# Perform Postorder Traversal
def postOrder(root):
    if root != None:
        inOrder(root.left)
        inOrder(root.right)
        print(root.data, end = " ")
 
# Given tree
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')
 
# Starting Mix order traversal
inOrder(root)
 
# This code is contributed by decode2207.

C#

// C# Program to implement
// the above approach
using System;
class GFG{
 
// Node structure
class node
{
    public char data;
    public node left, right;
};
 
// Creates and initialize a new node
static node newNode(char ch)
{
 
    // Allocating memory to a new node
    node n = new node();
    n.data = ch;
    n.left = null;
    n.right = null;
    return n;
}
 
// Perform Inorder Traversal
static void inOrder(node root)
{
    if (root != null)
    {
        postOrder(root.left);
        Console.Write(root.data + " ");
        postOrder(root.right);
    }
}
 
// Perform Postorder Traversal
static void postOrder(node root)
{
    if (root != null)
    {
        inOrder(root.left);
        inOrder(root.right);
        Console.Write(root.data + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given tree
    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');
 
    // Starting Mix order traversal
    inOrder(root);
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
    // Javascript Program to implement the above approach
     
    // Node structure
    class node
    {
        constructor() {
           this.left;
           this.right;
           this.data;
        }
    }
     
    // Creates and initialize a new node
    function newNode(ch)
    {
 
        // Allocating memory to a new node
        let n = new node();
        n.data = ch;
        n.left = null;
        n.right = null;
        return n;
    }
 
    // Perform Inorder Traversal
    function inOrder(root)
    {
        if (root != null)
        {
            postOrder(root.left);
            document.write(root.data + " ");
            postOrder(root.right);
        }
    }
 
    // Perform Postorder Traversal
    function postOrder(root)
    {
        if (root != null)
        {
            inOrder(root.left);
            inOrder(root.right);
            document.write(root.data + " ");
        }
    }
     
    // Given tree
    let 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');
  
    // Starting Mix order traversal
    inOrder(root);
   
  // This code is contributed by mukesh07.
</script>

Producción:

F D B A E C

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta