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