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.
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