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

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 (el Node más a la izquierda en BT) debe ser el Node principal de la DLL.  

TreeToList

C++

// A simple inorder traversal based
// program to convert a Binary Tree to DLL
#include <bits/stdc++.h>
using namespace std;
 
// A tree node
class node
{
    public:
    int data;
    node *left, *right;
};
 
// A utility function to create
// a new tree node
node *newNode(int data)
{
    node *Node = new node();
    Node->data = data;
    Node->left = Node->right = NULL;
    return(Node);
}
 
// Standard Inorder traversal of tree
void inorder(node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        cout << "\t" << root->data;
        inorder(root->right);
    }
}
 
// Changes left pointers to work as
// previous pointers in converted DLL
// The function simply does inorder
// traversal of Binary Tree and updates
// left pointer using previously visited node
void fixPrevPtr(node *root)
{
    static node *pre = NULL;
 
    if (root != NULL)
    {
        fixPrevPtr(root->left);
        root->left = pre;
        pre = root;
        fixPrevPtr(root->right);
    }
}
 
// Changes right pointers to work
// as next pointers in converted DLL
node *fixNextPtr(node *root)
{
    node *prev = NULL;
 
    // Find the right most node
    // in BT or last node in DLL
    while (root && root->right != NULL)
        root = root->right;
 
    // Start from the rightmost node,
    // traverse back using left pointers.
    // While traversing, change right pointer of nodes.
    while (root && root->left != NULL)
    {
        prev = root;
        root = root->left;
        root->right = prev;
    }
 
    // The leftmost node is head
    // of linked list, return it
    return (root);
}
 
// The main function that converts
// BST to DLL and returns head of DLL
node *BTToDLL(node *root)
{
    // Set the previous pointer
    fixPrevPtr(root);
 
    // Set the next pointer and return head of DLL
    return fixNextPtr(root);
}
 
// Traverses the DLL from left to right
void printList(node *root)
{
    while (root != NULL)
    {
        cout<<"\t"<<root->data;
        root = root->right;
    }
}
 
// Driver code
int main(void)
{
    // 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);
 
    cout<<"\n\t\tInorder Tree Traversal\n\n";
    inorder(root);
 
    node *head = BTToDLL(root);
 
    cout << "\n\n\t\tDLL Traversal\n\n";
    printList(head);
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// A simple inorder traversal based program to convert a Binary Tree to DLL
#include<stdio.h>
#include<stdlib.h>
 
// A tree node
struct node
{
    int data;
    struct node *left, *right;
};
 
// A utility function to create a new tree node
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = node->right = NULL;
    return(node);
}
 
// Standard Inorder traversal of tree
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("\t%d",root->data);
        inorder(root->right);
    }
}
 
// Changes left pointers to work as previous pointers in converted DLL
// The function simply does inorder traversal of Binary Tree and updates
// left pointer using previously visited node
void fixPrevPtr(struct node *root)
{
    static struct node *pre = NULL;
 
    if (root != NULL)
    {
        fixPrevPtr(root->left);
        root->left = pre;
        pre = root;
        fixPrevPtr(root->right);
    }
}
 
// Changes right pointers to work as next pointers in converted DLL
struct node *fixNextPtr(struct node *root)
{
    struct node *prev = NULL;
 
    // Find the right most node in BT or last node in DLL
    while (root && root->right != NULL)
        root = root->right;
 
    // Start from the rightmost node, traverse back using left pointers.
    // While traversing, change right pointer of nodes.
    while (root && root->left != NULL)
    {
        prev = root;
        root = root->left;
        root->right = prev;
    }
 
    // The leftmost node is head of linked list, return it
    return (root);
}
 
// The main function that converts BST to DLL and returns head of DLL
struct node *BTToDLL(struct node *root)
{
    // Set the previous pointer
    fixPrevPtr(root);
 
    // Set the next pointer and return head of DLL
    return fixNextPtr(root);
}
 
// Traverses the DLL from left to right
void printList(struct node *root)
{
    while (root != NULL)
    {
        printf("\t%d", root->data);
        root = root->right;
    }
}
 
// Driver program to test above functions
int main(void)
{
    // Let us create the tree shown in above diagram
    struct 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);
 
    printf("\n\t\tInorder Tree Traversal\n\n");
    inorder(root);
 
    struct node *head = BTToDLL(root);
 
    printf("\n\n\t\tDLL Traversal\n\n");
    printList(head);
    return 0;
}

Java

// Java program to convert BTT to DLL using
// simple inorder traversal
 
public class BinaryTreeToDLL
{
    static class node
    {
        int data;
        node left, right;
 
        public node(int data)
        {
            this.data = data;
        }
    }
 
    static node prev;
 
    // Changes left pointers to work as previous
    // pointers in converted DLL The function
    // simply does inorder traversal of Binary
    // Tree and updates left pointer using
    // previously visited node
    static void fixPrevptr(node root)
    {
        if (root == null)
            return;
 
        fixPrevptr(root.left);
        root.left = prev;
        prev = root;
        fixPrevptr(root.right);
 
    }
 
    // Changes right pointers to work
    // as next pointers in converted DLL
    static node fixNextptr(node root)
    {       
        // Find the right most node in
        // BT or last node in DLL
        while (root.right != null)
            root = root.right;
 
        // Start from the rightmost node, traverse
        // back using left pointers. While traversing,
        // change right pointer of nodes
        while (root != null && root.left != null)
        {
            node left = root.left;
            left.right = root;
            root = root.left;
        }
 
        // The leftmost node is head of linked list, return it
        return root;
    }
 
    static node BTTtoDLL(node root)
    {
        prev = null;
 
        // Set the previous pointer
        fixPrevptr(root);
 
        // Set the next pointer and return head of DLL
        return fixNextptr(root);
    }
 
    // Traverses the DLL from left to right
    static void printlist(node root)
    {
        while (root != null)
        {
            System.out.print(root.data + " ");
            root = root.right;
        }
    }
 
    // Standard Inorder traversal of tree
    static void inorder(node root)
    {
        if (root == null)
            return;
        inorder(root.left);
        System.out.print(root.data + " ");
        inorder(root.right);
    }
 
    public static void main(String[] args)
    {
        // Let us create the tree shown in above diagram
        node 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);
 
        System.out.println("Inorder Tree Traversal");
        inorder(root);
 
        node head = BTTtoDLL(root);
 
        System.out.println("\nDLL Traversal");
        printlist(head);
    }
}
 
// This code is contributed by Rishabh Mahrsee

Python3

# A simple inorder traversal based program to convert a
# Binary Tree to DLL
 
# A Binary Tree node
class Node:
     
    # Constructor to create a new tree node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Standard Inorder traversal of tree
def inorder(root):
     
    if root is not None:
        inorder(root.left)
        print ("\t%d" %(root.data),end=" ")
        inorder(root.right)
 
# Changes left pointers to work as previous pointers
# in converted DLL
# The function simply does inorder traversal of
# Binary Tree and updates
# left pointer using previously visited node
def fixPrevPtr(root):
    if root is not None:
        fixPrevPtr(root.left)
        root.left = fixPrevPtr.pre
        fixPrevPtr.pre = root
        fixPrevPtr(root.right)
 
# Changes right pointers to work as next pointers in
# converted DLL
def fixNextPtr(root):
 
    prev = None
    # Find the right most node in BT or last node in DLL
    while(root and root.right != None):
        root = root.right
 
    # Start from the rightmost node, traverse back using
    # left pointers
    # While traversing, change right pointer of nodes
    while(root and root.left != None):
        prev = root
        root = root.left
        root.right = prev
 
    # The leftmost node is head of linked list, return it
    return root
 
# The main function that converts BST to DLL and returns
# head of DLL
def BTToDLL(root):
     
    # Set the previous pointer
    fixPrevPtr(root)
 
    # Set the next pointer and return head of DLL
    return fixNextPtr(root)
 
# Traversses the DLL from left to right
def printList(root):
    while(root != None):
        print ("\t%d" %(root.data),end=" ")
        root = root.right
 
# Driver program to test above function
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)
 
print ("Inorder Tree Traversal")
inorder(root)
 
# Static variable pre for function fixPrevPtr
fixPrevPtr.pre = None
head = BTToDLL(root)
 
print ("\nDLL Traversal")
printList(head)
     
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to convert BTT to DLL using
// simple inorder traversal
using System;
 
class GFG
{
public class node
{
    public int data;
    public node left, right;
 
    public node(int data)
    {
        this.data = data;
    }
}
 
public static node prev;
 
// Changes left pointers to work as previous
// pointers in converted DLL The function
// simply does inorder traversal of Binary
// Tree and updates left pointer using
// previously visited node
public static void fixPrevptr(node root)
{
    if (root == null)
    {
        return;
    }
 
    fixPrevptr(root.left);
    root.left = prev;
    prev = root;
    fixPrevptr(root.right);
 
}
 
// Changes right pointers to work
// as next pointers in converted DLL
public static node fixNextptr(node root)
{
    // Find the right most node in
    // BT or last node in DLL
    while (root.right != null)
    {
        root = root.right;
    }
 
    // Start from the rightmost node, traverse
    // back using left pointers. While traversing,
    // change right pointer of nodes
    while (root != null && root.left != null)
    {
        node left = root.left;
        left.right = root;
        root = root.left;
    }
 
    // The leftmost node is head of
    // linked list, return it
    return root;
}
 
public static node BTTtoDLL(node root)
{
    prev = null;
 
    // Set the previous pointer
    fixPrevptr(root);
 
    // Set the next pointer and
    // return head of DLL
    return fixNextptr(root);
}
 
// Traverses the DLL from left to right
public static void printlist(node root)
{
    while (root != null)
    {
        Console.Write(root.data + " ");
        root = root.right;
    }
}
 
// Standard Inorder traversal of tree
public static void inorder(node root)
{
    if (root == null)
    {
        return;
    }
    inorder(root.left);
    Console.Write(root.data + " ");
    inorder(root.right);
}
 
public static void Main()
{
    // Let us create the tree
    // shown in above diagram
    node 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);
 
    Console.WriteLine("Inorder Tree Traversal");
    inorder(root);
 
    node head = BTTtoDLL(root);
 
    Console.WriteLine("\nDLL Traversal");
    printlist(head);
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
    // javascript program to convert BTT to DLL using
    // simple inorder traversal
 
    class node {
        constructor(val) {
            this.data = val;
            this.left = null;
            this.right = null;
        }
    }
    var prev;
 
    // Changes left pointers to work as previous
    // pointers in converted DLL The function
    // simply does inorder traversal of Binary
    // Tree and updates left pointer using
    // previously visited node
    function fixPrevptr( root) {
        if (root == null)
            return;
 
        fixPrevptr(root.left);
        root.left = prev;
        prev = root;
        fixPrevptr(root.right);
 
    }
 
    // Changes right pointers to work
    // as next pointers in converted DLL
    function fixNextptr( root) {
        // Find the right most node in
        // BT or last node in DLL
        while (root.right != null)
            root = root.right;
 
        // Start from the rightmost node, traverse
        // back using left pointers. While traversing,
        // change right pointer of nodes
        while (root != null && root.left != null) {
            var left = root.left;
            left.right = root;
            root = root.left;
        }
 
        // The leftmost node is head of linked list, return it
        return root;
    }   
 
    function BTTtoDLL( root) {
        prev = null;
 
        // Set the previous pointer
        fixPrevptr(root);
 
        // Set the next pointer and return head of DLL
        return fixNextptr(root);
    }
 
    // Traverses the DLL from left to right
    function printlist( root) {
        while (root != null) {
            document.write(root.data + "   ");
            root = root.right;
        }
    }
 
    // Standard Inorder traversal of tree
    function inorder( root) {
        if (root == null)
            return;
        inorder(root.left);
        document.write(root.data + "   ");
        inorder(root.right);
    }
 
     
    // Let us create the tree shown in above diagram
    var 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);
 
    document.write("<br/>Inorder Tree Traversal<br/>");
    inorder(root);
 
    var head = BTTtoDLL(root);
 
    document.write("<br/>DLL Traversal<br/>");
    printlist(head);
 
// This code contributed by umadevi9616
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *