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

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 el Inorder del árbol binario dado. El primer Node del recorrido Inorder (Node más a la izquierda en BT) debe ser el Node principal de la DLL.

// C++ program to convert a given Binary Tree to Doubly Linked List
#include <bits/stdc++.h>
 
// 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;
}
 
// 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 BToDLL(Node* root, Node*& head)
{
    // Base cases
    if (root == NULL)
        return;
 
    // Recursively convert right subtree
    BToDLL(root->right, head);
 
    // insert root into DLL
    root->right = head;
 
    // Change left pointer of previous head
    if (head != NULL)
        head->left = root;
 
    // Change head of Doubly linked list
    head = root;
 
    // Recursively convert left subtree
    BToDLL(root->left, head);
}
 
// Utility function for printing double linked list.
void printList(Node* head)
{
    printf("Extracted Double Linked list is:\n");
    while (head) {
        printf("%d ", head->data);
        head = head->right;
    }
}
 
// Driver program to test above function
int main()
{
    /* Constructing below tree
            5
            / \
            3     6
        / \     \
        1 4     8
        / \     / \
        0 2     7 9 */
    Node* root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(6);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
    root->right->right = newNode(8);
    root->left->left->left = newNode(0);
    root->left->left->right = newNode(2);
    root->right->right->left = newNode(7);
    root->right->right->right = newNode(9);
 
    Node* head = NULL;
    BToDLL(root, head);
 
    printList(head);
 
    return 0;
}

// Java program to convert a given Binary Tree to Doubly Linked List
 
/* Structure for tree and Linked List */
class Node {
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
class BinaryTree {
    // root    --> Root of Binary Tree
    Node root;
 
    // head --> Pointer to head node of created doubly linked list
    Node head;
 
    // A simple recursive function to convert a given
    // Binary tree to Doubly Linked List
    void BToDLL(Node root)
    {
        // Base cases
        if (root == null)
            return;
 
        // Recursively convert right subtree
        BToDLL(root.right);
 
        // insert root into DLL
        root.right = head;
 
        // Change left pointer of previous head
        if (head != null)
            head.left = root;
 
        // Change head of Doubly linked list
        head = root;
 
        // Recursively convert left subtree
        BToDLL(root.left);
    }
 
    // Utility function for printing double linked list.
    void printList(Node head)
    {
        System.out.println("Extracted Double Linked List is : ");
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.right;
        }
    }
 
    // Driver program to test the above functions
    public static void main(String[] args)
    {
        /* Constructing below tree
               5
             /   \
            3     6
           / \     \
          1   4     8
         / \       / \
        0   2     7   9  */
 
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(6);
        tree.root.left.right = new Node(4);
        tree.root.left.left = new Node(1);
        tree.root.right.right = new Node(8);
        tree.root.left.left.right = new Node(2);
        tree.root.left.left.left = new Node(0);
        tree.root.right.right.left = new Node(7);
        tree.root.right.right.right = new Node(9);
 
        tree.BToDLL(tree.root);
        tree.printList(tree.head);
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

# Python3 program to convert a given Binary Tree to Doubly Linked List
class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
 
class BinaryTree:
    # 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
    root, head = None, None
     
    def BToDll(self, root: Node):
        if root is None:
            return
 
        # Recursively convert right subtree
        self.BToDll(root.right)
 
        # Insert root into doubly linked list
        root.right = self.head
 
        # Change left pointer of previous head
        if self.head is not None:
            self.head.left = root
 
        # Change head of doubly linked list
        self.head = root
 
        # Recursively convert left subtree
        self.BToDll(root.left)
 
    @staticmethod
    def print_list(head: Node):
        print('Extracted Double Linked list is:')
        while head is not None:
            print(head.data, end = ' ')
            head = head.right
 
# Driver program to test above function
if __name__ == '__main__':
     
    """
    Constructing below tree
            5
        // \\
        3 6
        // \\ \\
        1 4 8
    // \\ // \\
    0 2 7 9
    """
    tree = BinaryTree()
    tree.root = Node(5)
    tree.root.left = Node(3)
    tree.root.right = Node(6)
    tree.root.left.left = Node(1)
    tree.root.left.right = Node(4)
    tree.root.right.right = Node(8)
    tree.root.left.left.left = Node(0)
    tree.root.left.left.right = Node(2)
    tree.root.right.right.left = Node(7)
    tree.root.right.right.right = Node(9)
 
    tree.BToDll(tree.root)
    tree.print_list(tree.head)
 
# This code is contributed by Rajat Srivastava

// C# program to convert a given Binary Tree to Doubly Linked List
using System;
 
/* Structure for tree and Linked List */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
class GFG {
    // root    --> Root of Binary Tree
    public Node root;
 
    // head --> Pointer to head node of created doubly linked list
    public Node head;
 
    // A simple recursive function to convert a given
    // Binary tree to Doubly Linked List
    public virtual void BToDLL(Node root)
    {
        // Base cases
        if (root == null)
            return;
 
        // Recursively convert right subtree
        BToDLL(root.right);
 
        // insert root into DLL
        root.right = head;
 
        // Change left pointer of previous head
        if (head != null)
            head.left = root;
 
        // Change head of Doubly linked list
        head = root;
 
        // Recursively convert left subtree
        BToDLL(root.left);
    }
 
    // Utility function for printing double linked list.
    public virtual void printList(Node head)
    {
        Console.WriteLine("Extracted Double "
                          + "Linked List is : ");
        while (head != null) {
            Console.Write(head.data + " ");
            head = head.right;
        }
    }
 
    // Driver program to test above function
    public static void Main(string[] args)
    {
        /* Constructing below tree
            5
            / \
            3     6
        / \     \
        1 4     8
        / \     / \
        0 2     7 9 */
 
        GFG tree = new GFG();
        tree.root = new Node(5);
        tree.root.left = new Node(3);
        tree.root.right = new Node(6);
        tree.root.left.right = new Node(4);
        tree.root.left.left = new Node(1);
        tree.root.right.right = new Node(8);
        tree.root.left.left.right = new Node(2);
        tree.root.left.left.left = new Node(0);
        tree.root.right.right.left = new Node(7);
        tree.root.right.right.right = new Node(9);
 
        tree.BToDLL(tree.root);
        tree.printList(tree.head);
    }
}
 
// This code is contributed by Shrikant13

<script>
// javascript program to convert a given
// Binary Tree to Doubly Linked List
 
/* Structure for tree and Linked List */
class Node {
  constructor(data)
    {
        this.data = data;
        this.left = this.right = null;
    }
}
 
 
    // root    --> Root of Binary Tree
    var root;
 
    // head --> Pointer to head node of created doubly linked list
    var head;
 
    // A simple recursive function to convert a given
    // Binary tree to Doubly Linked List
    function BToDLL( root)
    {
        // Base cases
        if (root == null)
            return;
 
        // Recursively convert right subtree
        BToDLL(root.right);
 
        // insert root into DLL
        root.right = head;
 
        // Change left pointer of previous head
        if (head != null)
            head.left = root;
 
        // Change head of Doubly linked list
        head = root;
 
        // Recursively convert left subtree
        BToDLL(root.left);
    }
 
    // Utility function for printing var linked list.
    function printList( head)
    {
        document.write("Extracted Double Linked List is :<br/> ");
        while (head != null) {
            document.write(head.data + " ");
            head = head.right;
        }
    }
 
    // Driver program to test the above functions
 
        /* Constructing below tree
               5
             /   \
            3     6
           / \     \
          1   4     8
         / \       / \
        0   2     7   9  */
 
        root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(6);
        root.left.right = new Node(4);
        root.left.left = new Node(1);
        root.right.right = new Node(8);
        root.left.left.right = new Node(2);
        root.left.left.left = new Node(0);
        root.right.right.left = new Node(7);
        root.right.right.right = new Node(9);
 
        BToDLL(root);
        printList(head);
 
// This code contributed by umadevi9616
</script>