Convertir un árbol binario dado en una lista doblemente enlazada | conjunto 3

Dado un árbol binario (BT), conviértalo en una lista doblemente enlazada (DLL) en el lugar. 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 (el Node más a la izquierda en BT) debe ser el Node principal de la DLL. 

// A C++ program for in-place conversion of Binary Tree to
// DLL
#include <iostream>
using namespace std;
 
/* A binary tree node has data, and left and right pointers
 */
struct node {
    int data;
    node* left;
    node* right;
};
 
// A simple recursive function to convert a given Binary
// tree to Doubly Linked List root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked
// list
void BinaryTree2DoubleLinkedList(node* root, node** head)
{
    // Base case
    if (root == NULL)
        return;
 
    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all
    // recursive calls
    static node* prev = NULL;
 
    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(root->left, head);
 
    // Now convert this node
    if (prev == NULL)
        *head = root;
    else {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
 
    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root->right, head);
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
 
/* Function to print nodes in a given doubly linked list */
void printList(node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->right;
    }
}
 
/* Driver program to test above functions*/
int main()
{
    // Let us create the tree shown in above diagram
    node* root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
 
    // Convert to DLL
    node* head = NULL;
    BinaryTree2DoubleLinkedList(root, &head);
 
    // Print the converted list
    printList(head);
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// A C program for in-place conversion of Binary Tree to DLL
#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, and left and right pointers
 */
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} node;
 
// A simple recursive function to convert a given Binary
// tree to Doubly Linked List root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked
// list
void BinaryTree2DoubleLinkedList(node* root, node** head)
{
    // Base case
    if (root == NULL)
        return;
 
    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all
    // recursive calls
    static node* prev = NULL;
 
    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(root->left, head);
 
    // Now convert this node
    if (prev == NULL)
        *head = root;
    else {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
 
    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root->right, head);
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* new_node = (node*)malloc(sizeof(node));
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
 
/* Function to print nodes in a given doubly linked list */
void printList(node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->right;
    }
}
 
/* Driver program to test above functions*/
int main()
{
    // Let us create the tree shown in above diagram
    node* root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
 
    // Convert to DLL
    node* head = NULL;
    BinaryTree2DoubleLinkedList(root, &head);
 
    // Print the converted list
    printList(head);
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// A Java program for in-place conversion of Binary Tree to DLL
  
// A binary tree node has data, left pointers and right pointers
class Node
{
    int data;
    Node left, right;
  
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
  
class BinaryTree
{
    Node root;
      
    // head --> Pointer to head node of created doubly linked list
    Node head;
      
    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all recursive
    // calls
    static Node prev = null;
  
    // A simple recursive function to convert a given Binary tree
    // to Doubly Linked List
    // root --> Root of Binary Tree
    void BinaryTree2DoubleLinkedList(Node root)
    {
        // Base case
        if (root == null)
            return;
  
        // Recursively convert left subtree
        BinaryTree2DoubleLinkedList(root.left);
  
        // Now convert this node
        if (prev == null)
            head = root;
        else
        {
            root.left = prev;
            prev.right = root;
        }
        prev = root;
  
        // Finally convert right subtree
        BinaryTree2DoubleLinkedList(root.right);
    }
  
    /* Function to print nodes in a given doubly linked list */
    void printList(Node node)
    {
        while (node != null)
        {
            System.out.print(node.data + " ");
            node = node.right;
        }
    }
  
    // Driver program to test above functions
    public static void main(String[] args)
    {
        // Let us create the tree as shown in above diagram
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(12);
        tree.root.right = new Node(15);
        tree.root.left.left = new Node(25);
        tree.root.left.right = new Node(30);
        tree.root.right.left = new Node(36);
  
        // convert to DLL
        tree.BinaryTree2DoubleLinkedList(tree.root);
          
        // Print the converted List
        tree.printList(tree.head);
  
    }
}
// This code has been contributed by Mayank Jaiswal(mayank_24)

# Python program for conversion of
# binary tree to doubly linked list.
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
 
# Global variable used in covert
prev = None
 
def BinaryTree2DoubleLinkedList(root):
     
    # Base case
    if root is None:
        return root
             
    # Recursively convert left subtree
    head = BinaryTree2DoubleLinkedList(root.left);
     
    # Since we are going to change prev,
    # we need to use global keyword
    global prev
     
    # If prev is empty, then this is the
    # first node of DLL
    if prev is None :
        head = root
         
    else:
        root.left = prev
        prev.right = root
     
    # Update prev
    prev = root;
     
    # Recursively convert right subtree
    BinaryTree2DoubleLinkedList(root.right);
     
    return head
 
def print_dll(head):
     
    # Function to print nodes in given
    # doubly linked list
    while head is not None:
        print(head.data, end=" ")
        head = head.right
 
 
# Driver program to test above functions
# Let us create the tree as
# shown in above diagram
if __name__ == '__main__':
    root = Node(10)
    root.left = Node(12)
    root.right = Node(15)
    root.left.left = Node(25)
    root.left.right = Node(30)
    root.right.left = Node(36)
     
    head = BinaryTree2DoubleLinkedList(root)
     
    # Print the converted list
    print_dll(head)
     
# This code is contributed by codesankalp (SANKALP)

// A C# program for in-place conversion
// of Binary Tree to DLL
using System;
 
// A binary tree node has data, left
// pointers and right pointers
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
class GFG
{
public Node root;
 
// head --> Pointer to head node of
// created doubly linked list
public Node head;
 
// Initialize previously visited node
// as NULL. This is static so that the
// same value is accessible in all
// recursive calls
public static Node prev = null;
 
// A simple recursive function to
// convert a given Binary tree
// to Doubly Linked List
// root --> Root of Binary Tree
public virtual void BinaryTree2DoubleLinkedList(Node root)
{
    // Base case
    if (root == null)
    {
        return;
    }
 
    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(root.left);
 
    // Now convert this node
    if (prev == null)
    {
        head = root;
    }
    else
    {
        root.left = prev;
        prev.right = root;
    }
    prev = root;
 
    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root.right);
}
 
/* Function to print nodes in a
   given doubly linked list */
public virtual void printList(Node node)
{
    while (node != null)
    {
        Console.Write(node.data + " ");
        node = node.right;
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    // Let us create the tree as
    // shown in above diagram
    GFG tree = new GFG();
    tree.root = new Node(10);
    tree.root.left = new Node(12);
    tree.root.right = new Node(15);
    tree.root.left.left = new Node(25);
    tree.root.left.right = new Node(30);
    tree.root.right.left = new Node(36);
 
    // convert to DLL
    tree.BinaryTree2DoubleLinkedList(tree.root);
 
    // Print the converted List
    tree.printList(tree.head);
 
}
}
 
// This code is contributed by Shrikant13

<script>
    // A javascript program for in-place conversion of Binary Tree to DLL
  
    // A binary tree node has data, left pointers and right pointers
    class Node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
        }
    }
 
    var root;
      
    // head --> Pointer to head node of created doubly linked list
    var head;
      
    // Initialize previously visited node as NULL. This is
    //  so that the same value is accessible in all recursive
    // calls
    var prev = null;
  
    // A simple recursive function to convert a given Binary tree
    // to Doubly Linked List
    // root --> Root of Binary Tree
    function BinaryTree2DoubleLinkedList(root)
    {
        // Base case
        if (root == null)
            return;
  
        // Recursively convert left subtree
        BinaryTree2DoubleLinkedList(root.left);
  
        // Now convert this node
        if (prev == null)
            head = root;
        else
        {
            root.left = prev;
            prev.right = root;
        }
        prev = root;
  
        // Finally convert right subtree
        BinaryTree2DoubleLinkedList(root.right);
    }
  
    /* Function to print nodes in a given doubly linked list */
    function printList(node)
    {
        while (node != null)
        {
            document.write(node.data + " ");
            node = node.right;
        }
    }
  
    // Driver program to test above functions
 
    // Let us create the tree as shown in above diagram
      
    root = new Node(10);
    root.left = new Node(12);
    root.right = new Node(15);
    root.left.left = new Node(25);
    root.left.right = new Node(30);
    root.right.left = new Node(36);
  
    // convert to DLL
    BinaryTree2DoubleLinkedList(root);
         
    // Print the converted List
    printList(head);
  
// This code contributed by umadevi9616
</script>

Node * bToDLL(Node *root)
{
    stack<pair<Node*, int>> s;
    s.push({root, 0});
    vector<int> res;
    bool flag = true;
    Node* head = NULL;
    Node* prev = NULL;
    while(!s.empty()) {
        auto x = s.top();
        Node* t = x.first;
        int state = x.second;
        s.pop();
        if(state == 3 or t == NULL) continue;
        s.push({t, state+1});
        if(state == 0) s.push({t->left, 0});
        else if(state == 1) {
            if(prev) prev->right = t;
            t->left = prev;
            prev = t;
            if(flag) {
                head = t;
                flag = false;
            }
        }
        else if(state == 2) s.push({t->right, 0});
    }
    return head;
}

Node bToDLL(Node root)
{
    Stack<Pair> s = new Stack<Pair>();
    s.push(new Pair(root, 0));
    int[] res;
    boolean flag = true;
    Node head = null;
    Node prev = null;
    while (!s.empty()) {
        Pair x = s.peek();
        Node t = x.first;
        int state = x.second;
        s.pop();
        if (state == 3 || t == null)
            continue;
        s.push(new Pair(t, state + 1));
        if (state == 0)
            s.push(new Pair(t.left, 0));
        else if (state == 1) {
            if (prev != null)
                prev.right = t;
            t.left = prev;
            prev = t;
            if (flag) {
                head = t;
                flag = false;
            }
        }
        else if (state == 2)
            s.push(new Pair(t.right, 0));
    }
    return head;
}
 
// This code is contributed by Lovely Jain

def bToDLL(root):
    s = []
    s.append([root, 0])
    res = []
    flag = True
    head = None
    prev = None
    while len(s) > 0:
        x = s.pop()
        t = x[0]
        state = x[1]
        if state == 3 or t == None: continue
        s.append([t, state+1])
        if state == 0: s.append([t.left, 0])
        elif state == 1:
            if prev != None: prev.right = t
            t.left = prev
            prev = t
 
            if flag: 
                head = t
                flag = False 
 
        elif state == 2: s.append([t.right, 0])
 
    return head
   
  # This code is contributed by Tapeshdua420.

Node bToDLL(Node root)
{
    Stack<Tuple<Node, int> > s
        = new Stack<Tuple<Node, int> >();
    s.Push(new Tuple<Node, int>(root, 0));
    List<int> res = new List<int>();
    bool flag = true;
    Node head = null;
    Node prev = null;
    while (s.Count > 0) {
        var x = s.Pop();
        Node t = x.Item1;
        int state = x.Item2;
        if (state == 3 || t == null)
            continue;
        s.Push(new Tuple<Node, int>(t, state + 1));
        if (state == 0)
            s.Push(new Tuple<Node, int>(t.left, 0));
        else if (state == 1) {
            if (prev != null)
                prev.right = t;
            t.left = prev;
            prev = t;
            if (flag) {
                head = t;
                flag = false;
            }
        }
        else if (state == 2)
            s.Push(new Tuple<Node, int>(t.right, 0));
    }
 
    return head;
}
 
// This code is contributed by Tapesh(tapeshdua420)