Convertir árbol binario dado a lista doblemente enlazada | Conjunto 5 (Usando Morris Traversal)

Dado un árbol binario (BT), conviértalo en una lista doblemente enlazada (DLL). Los punteros izquierdo y derecho en los Nodes se utilizarán como punteros anterior y siguiente, respectivamente, en la DLL convertida. El orden de los Nodes en DLL debe ser el mismo que en Inorder para el árbol binario dado. El primer Node del recorrido Inorder debe ser el Node principal de la DLL.  

Ejemplos:

Entrada: 
     1
   / \
  3 2
Salida: 
Orden real: 3 1 2
Orden inverso: 2 1 3
Explicación: El encabezado de la lista enlazada será 3 y el último elemento será 2.
DLL será 3 <=> 1 <= > 2

Entrada:
           10
         / \
       20 30
     / \    
    40 60
Salida: 
Orden real: 40 20 60 10 30
Orden inverso: 30 10 60 20 40

A continuación se presentan varios enfoques que se han discutido anteriormente:

Acercarse:

Los enfoques anteriores utilizan la recursividad o la pila para obtener el Inorder Traversal. Este enfoque se basa en Morris Traversal para encontrar Inorder Traversal , que es iterativo y tiene una complejidad espacial de O(1). 

La idea es que primero crearemos una lista con un solo enlace mientras hacemos Morris Traversal y luego la convertiremos en una lista con doble enlace colocando el puntero izquierdo de cada Node en el Node anterior en orden.  

Siga los pasos mencionados a continuación para implementar la idea:

  • Realice Morris Traversal para atravesar el árbol en orden en tiempo lineal y cree la lista enlazada individualmente.
  • Ahora recorra la lista enlazada individualmente:
    • Cree un enlace entre el Node actual y el predecesor en orden.
    • Actualice el Node actual y anterior (predecesor) según corresponda en cada paso y pase al siguiente Node.
  • La lista doblemente enlazada generada es la requerida.

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

C++

// C++ code to implement the idea
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure for tree and linked list
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function for allocating node for
// Binary Tree.
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
Node* BToDLL(Node* root)
{
    Node* curr = root;
 
    // Store head & tail of the linked list
    // created so far
    Node *head = NULL, *tail = NULL;
 
    // Morris Traversal
    while (curr) {
 
        if (curr->left == NULL) {
 
            // If it is to be the first node
            // of the desired Linked list
            if (head == NULL) {
                head = curr;
                tail = curr;
            }
            else {
 
                // Append it to the tail of the
                // linked list we have created
                // so far & set it as new tail
                tail->right = curr;
                tail = tail->right;
            }
 
            curr = curr->right;
        }
        else {
 
            // Inorder predecessor
            Node* pred = curr->left;
            while (pred->right != NULL
                   && pred->right != curr) {
                pred = pred->right;
            }
 
            if (pred->right == NULL) {
                pred->right = curr;
                curr = curr->left;
            }
            else {
 
                // Append it to the tail of
                // the linked list
                // we have created so far & set it
                // as new tail
                // Note we don't have to unlink
                // predecessor
                tail->right = curr;
                tail = tail->right;
                curr = curr->right;
            }
        }
    }
 
    curr = head;
    Node* prev = NULL;
 
    // Converting singly linked list to
    // doubly linked list
 
    while (curr) {
        curr->left = prev;
        prev = curr;
        curr = curr->right;
    }
 
    return head;
}
 
// Utility function for printing
// double linked list.
void printList(Node* head)
{
    printf("Actual order: ");
    while (head) {
        printf("%d ", head->data);
        head = head->right;
    }
}
 
// Utility function for printing
// double linked list in Reverse Order.
void printReverseList(Node* tail)
{
    printf("\nReverse Order: ");
    while (tail) {
        printf("%d ", tail->data);
        tail = tail->left;
    }
}
 
// Driver code
int main()
{
    /* Constructing below tree
                  10
                /   \
               20    30
              / \
             40 60          */
    Node* root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(60);
 
    // Function call
    Node* head = BToDLL(root);
    printList(head);
 
    Node* tail = head;
    // Finding Tail of DLL
    while (tail && tail->right) {
        tail = tail->right;
    }
    printReverseList(tail);
 
    return 0;
}

Java

// Java code to implement the above idea
 
class GFG {
 
  // structure of tree and linked list.
  class Node {
    int data;
    Node left, right;
  }
 
  // Utility function for allocating node for binary tree.
  public Node newNode(int data)
  {
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return node;
  }
 
  public Node BToDLL(Node root)
  {
    Node curr = root;
 
    // Store head & tail of the linked list created so
    // far
    Node head = null, tail = null;
 
    // Morris Traversal
    while (curr != null) {
 
      if (curr.left == null) {
 
        // If it is to be the first node of the
        // desired Linked list.
        if (head == null) {
          head = curr;
          tail = curr;
        }
        else {
          // Append it to the tail of the linked
          // list we have created so far & set it
          // as new tail
          tail.right = curr;
          tail = tail.right;
        }
        curr = curr.right;
      }
      else {
 
        // Inorder predecessor
        Node pred = curr.left;
        while (pred.right != null
               && pred.right != curr) {
          pred = pred.right;
        }
        if (pred.right == null) {
          pred.right = curr;
          curr = curr.left;
        }
        else {
 
          // Append it to the tail of the linked
          // list we have created so far & set it
          // as new tail. Note we don't have to
          // unlink predecessor
          tail.right = curr;
          tail = tail.right;
          curr = curr.right;
        }
      }
    }
    curr = head;
    Node prev = null;
 
    // Converting singly linked list to doubly linked
    // list.
    while (curr != null) {
      curr.left = prev;
      prev = curr;
      curr = curr.right;
    }
    return head;
  }
 
  // Utility function for printing doubly linked list
  public void printList(Node head)
  {
    System.out.print("Actual order: ");
    while (head != null) {
      System.out.print(head.data + " ");
      head = head.right;
    }
  }
 
  // Utility function for printing doubly linked list in
  // reverse order.
  public void printReverseList(Node tail)
  {
    System.out.print("\nReverse Order: ");
    while (tail != null) {
      System.out.print(tail.data + " ");
      tail = tail.left;
    }
  }
 
  public static void main(String[] args)
  {
 
    GFG list = new GFG();
 
    /* Constructing below tree
                    10
                   /  \
                  20   30
                 /  \
                40   60            */
    Node root = list.newNode(10);
    root.left = list.newNode(20);
    root.right = list.newNode(30);
    root.left.left = list.newNode(40);
    root.left.right = list.newNode(60);
 
    // Function call
    Node head = list.BToDLL(root);
    list.printList(head);
 
    Node tail = head;
    // Finding tail of DLL
    while (tail != null && tail.right != null) {
      tail = tail.right;
    }
    list.printReverseList(tail);
  }
}
 
// This code is contributed by lokesh (lokeshmvs21).

C#

// C# code to implement the above idea
 
using System;
 
public class GFG {
 
  // structure of tree and linked list.
  public class Node {
    public int data;
    public Node left;
    public Node right;
  }
 
  // Utility function for allocating node for binary tree.
  public Node newNode(int data)
  {
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return node;
  }
 
  public Node BToDLL(Node root)
  {
    Node curr = root;
 
    // Store head & tail of the linked list created so
    // far
    Node head = null, tail = null;
 
    // Morris Traversal
    while (curr != null) {
 
      if (curr.left == null) {
 
        // If it is to be the first node of the
        // desired Linked list.
        if (head == null) {
          head = curr;
          tail = curr;
        }
        else {
          // Append it to the tail of the linked
          // list we have created so far & set it
          // as new tail
          tail.right = curr;
          tail = tail.right;
        }
        curr = curr.right;
      }
      else {
 
        // Inorder predecessor
        Node pred = curr.left;
        while (pred.right != null
               && pred.right != curr) {
          pred = pred.right;
        }
        if (pred.right == null) {
          pred.right = curr;
          curr = curr.left;
        }
        else {
 
          // Append it to the tail of the linked
          // list we have created so far & set it
          // as new tail. Note we don't have to
          // unlink predecessor
          tail.right = curr;
          tail = tail.right;
          curr = curr.right;
        }
      }
    }
    curr = head;
    Node prev = null;
 
    // Converting singly linked list to doubly linked
    // list.
    while (curr != null) {
      curr.left = prev;
      prev = curr;
      curr = curr.right;
    }
    return head;
  }
 
  // Utility function for printing doubly linked list
  public void printList(Node head)
  {
    Console.Write("Actual order: ");
    while (head != null) {
      Console.Write(head.data + " ");
      head = head.right;
    }
  }
 
  // Utility function for printing doubly linked list in
  // reverse order.
  public void printReverseList(Node tail)
  {
    Console.Write("\nReverse Order: ");
    while (tail != null) {
      Console.Write(tail.data + " ");
      tail = tail.left;
    }
  }
 
  static public void Main()
  {
 
    // Code
    GFG list = new GFG();
 
    /* Constructing below tree
                    10
                   /  \
                  20   30
                 /  \
                40   60            */
    Node root = list.newNode(10);
    root.left = list.newNode(20);
    root.right = list.newNode(30);
    root.left.left = list.newNode(40);
    root.left.right = list.newNode(60);
 
    // Function call
    Node head = list.BToDLL(root);
    list.printList(head);
 
    Node tail = head;
    // Finding tail of DLL
    while (tail != null && tail.right != null) {
      tail = tail.right;
    }
    list.printReverseList(tail);
  }
}
 
// This code is contributed by lokesh (lokeshmvs21).
Producción

Actual order: 40 20 60 10 30 
Reverse Order: 30 10 60 20 40 

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

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *