Dado un árbol binario, conviértalo en una lista circular doblemente enlazada.
- Los punteros izquierdo y derecho en los Nodes se utilizarán como punteros anterior y siguiente, respectivamente, en la Lista enlazada circular convertida.
- El orden de los Nodes en la Lista debe ser el mismo que en el orden del Árbol Binario dado.
- El primer Node del recorrido Inorder debe ser el Node principal de la Lista circular.
Ejemplo:
Una solución en el lugar a este problema se discute en la publicación anterior.
En esta publicación, se analiza una solución mucho más simple, pero que usa espacio O (n) adicional.
En este enfoque, primero, hacemos un recorrido en orden del árbol binario dado, almacenamos este recorrido en un vector, que se pasará a la función junto con el árbol. Ahora, genere una lista circular doblemente enlazada a partir de los elementos del vector.
Para generar una lista circular doblemente enlazada a partir del vector, haga que el primer elemento del vector sea el encabezado de la lista enlazada y también cree un puntero actual que esté ahora apuntando al encabezado. Ahora comience a atravesar la array desde el segundo elemento y haga lo siguiente.
- Cree un puntero temporal que apunte al puntero actual.
- Haz un nuevo Node con el elemento actual del vector.
- Haga que el punto derecho actual a este nuevo Node.
- Convierta el puntero actual en el puntero derecho actual.
- Ahora, finalmente, el punto izquierdo actual es un puntero temporal creado en el primer paso.
Haga esto para todos los elementos y después de completar el recorrido, haga que la derecha de la corriente (la corriente ahora apunta al último elemento del vector) apunte al encabezado de la lista y que la izquierda de la cabeza apunte al puntero actual. Finalmente, devuelve la cabeza.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program for conversion
// of Binary Tree to CDLL
#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data,
// and left and right pointers
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
// Function to perform In-Order traversal of the
// tree and store the nodes in a vector
void inorder(Node* root, vector<int>& v)
{
if (!root)
return;
/* first recur on left child */
inorder(root->left, v);
/* append the data of node in vector */
v.push_back(root->data);
/* now recur on right child */
inorder(root->right, v);
}
// Function to convert Binary Tree to Circular
// Doubly Linked list using the vector which stores
// In-Order traversal of the Binary Tree
Node* bTreeToCList(Node* root)
{
// Base cases
if (root == NULL)
return NULL;
// Vector to be used for storing the nodes
// of tree in In-order form
vector<int> v;
// Calling the In-Order traversal function
inorder(root, v);
// Create the head of the linked list pointing
// to the root of the tree
Node* head_ref = new Node(v[0]);
// Create a current pointer to be used in traversal
Node* curr = head_ref;
// Traversing the nodes of the tree starting
// from the second elements
for (int i = 1; i < v.size(); i++) {
// Create a temporary pointer
// pointing to current
Node* temp = curr;
// Current's right points to the current
// node in traversal
curr->right = new Node(v[i]);
// Current points to its right
curr = curr->right;
// Current's left points to temp
curr->left = temp;
}
// Current's right points to head of the list
curr->right = head_ref;
// Head's left points to current
head_ref->left = curr;
// Return head of the list
return head_ref;
}
// Display Circular Link List
void displayCList(Node* head)
{
cout << "Circular Doubly Linked List is :\n";
Node* itr = head;
do {
cout << itr->data << " ";
itr = itr->right;
} while (head != itr);
cout << "\n";
}
// Driver Code
int main()
{
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);
Node* head = bTreeToCList(root);
displayCList(head);
return 0;
}
Java
// Java program for conversion
// of Binary Tree to CDLL
import java.util.*;
class GFG
{
// A binary tree node has data,
// and left and right pointers
static class Node
{
int data;
Node left;
Node right;
Node(int x)
{
data = x;
left = right = null;
}
};
// Function to perform In-Order traversal of the
// tree and store the nodes in a vector
static void inorder(Node root, Vector<Integer> v)
{
if (root == null)
return;
/* first recur on left child */
inorder(root.left, v);
/* append the data of node in vector */
v.add(root.data);
/* now recur on right child */
inorder(root.right, v);
}
// Function to convert Binary Tree to Circular
// Doubly Linked list using the vector which stores
// In-Order traversal of the Binary Tree
static Node bTreeToCList(Node root)
{
// Base cases
if (root == null)
return null;
// Vector to be used for storing the nodes
// of tree in In-order form
Vector<Integer> v = new Vector<>();
// Calling the In-Order traversal function
inorder(root, v);
// Create the head of the linked list pointing
// to the root of the tree
Node head_ref = new Node(v.get(0));
// Create a current pointer to be used in traversal
Node curr = head_ref;
// Traversing the nodes of the tree starting
// from the second elements
for (int i = 1; i < v.size(); i++)
{
// Create a temporary pointer
// pointing to current
Node temp = curr;
// Current's right points to the current
// node in traversal
curr.right = new Node(v.get(i));
// Current points to its right
curr = curr.right;
// Current's left points to temp
curr.left = temp;
}
// Current's right points to head of the list
curr.right = head_ref;
// Head's left points to current
head_ref.left = curr;
// Return head of the list
return head_ref;
}
// Display Circular Link List
static void displayCList(Node head)
{
System.out.println("Circular Doubly Linked List is :");
Node itr = head;
do
{
System.out.print(itr.data + " ");
itr = itr.right;
} while (head != itr);
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
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);
Node head = bTreeToCList(root);
displayCList(head);
}
}
// This code is contributed by Rajput-Ji
Python
# Python program for conversion
# of Binary Tree to CDLL
# A binary tree node has data,
# and left and right pointers
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None
v = []
# Function to perform In-Order traversal of the
# tree and store the nodes in a vector
def inorder(root):
global v
if (root == None):
return
# first recur on left child
inorder(root.left)
# append the data of node in vector
v.append(root.data)
# now recur on right child
inorder(root.right)
# Function to convert Binary Tree to Circular
# Doubly Linked list using the vector which stores
# In-Order traversal of the Binary Tree
def bTreeToCList(root):
global v
# Base cases
if (root == None):
return None
# Vector to be used for storing the nodes
# of tree in In-order form
v = []
# Calling the In-Order traversal function
inorder(root)
# Create the head of the linked list pointing
# to the root of the tree
head_ref = Node(v[0])
# Create a current pointer to be used in traversal
curr = head_ref
i = 1
# Traversing the nodes of the tree starting
# from the second elements
while ( i < len(v)) :
# Create a temporary pointer
# pointing to current
temp = curr
# Current's right points to the current
# node in traversal
curr.right = Node(v[i])
# Current points to its right
curr = curr.right
# Current's left points to temp
curr.left = temp
i = i + 1
# Current's right points to head of the list
curr.right = head_ref
# Head's left points to current
head_ref.left = curr
# Return head of the list
return head_ref
# Display Circular Link List
def displayCList(head):
print("Circular Doubly Linked List is :", end = "")
itr = head
while(True):
print(itr.data, end = " ")
itr = itr.right
if(head == itr):
break
print()
# Driver Code
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 = bTreeToCList(root)
displayCList(head)
# This code is contributed by Arnab Kundu
C#
// C# program for conversion
// of Binary Tree to CDLL
using System;
using System.Collections.Generic;
class GFG
{
// A binary tree node has data,
// and left and right pointers
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int x)
{
data = x;
left = right = null;
}
};
// Function to perform In-Order traversal of the
// tree and store the nodes in a vector
static void inorder(Node root, List<int> v)
{
if (root == null)
return;
/* first recur on left child */
inorder(root.left, v);
/* append the data of node in vector */
v.Add(root.data);
/* now recur on right child */
inorder(root.right, v);
}
// Function to convert Binary Tree to Circular
// Doubly Linked list using the vector which stores
// In-Order traversal of the Binary Tree
static Node bTreeToCList(Node root)
{
// Base cases
if (root == null)
return null;
// Vector to be used for storing the nodes
// of tree in In-order form
List<int> v = new List<int>();
// Calling the In-Order traversal function
inorder(root, v);
// Create the head of the linked list
// pointing to the root of the tree
Node head_ref = new Node(v[0]);
// Create a current pointer
// to be used in traversal
Node curr = head_ref;
// Traversing the nodes of the tree starting
// from the second elements
for (int i = 1; i < v.Count; i++)
{
// Create a temporary pointer
// pointing to current
Node temp = curr;
// Current's right points to the current
// node in traversal
curr.right = new Node(v[i]);
// Current points to its right
curr = curr.right;
// Current's left points to temp
curr.left = temp;
}
// Current's right points to head of the list
curr.right = head_ref;
// Head's left points to current
head_ref.left = curr;
// Return head of the list
return head_ref;
}
// Display Circular Link List
static void displayCList(Node head)
{
Console.WriteLine("Circular Doubly " +
"Linked List is :");
Node itr = head;
do
{
Console.Write(itr.data + " ");
itr = itr.right;
} while (head != itr);
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
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);
Node head = bTreeToCList(root);
displayCList(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for conversion
// of Binary Tree to CDLL
// A binary tree node has data,
// and left and right pointers
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Function to perform In-Order traversal of the
// tree and store the nodes in a vector
function inorder(root, v) {
if (root == null)
return;
/* first recur on left child */
inorder(root.left, v);
/* append the data of node in vector */
v.push(root.data);
/* now recur on right child */
inorder(root.right, v);
}
// Function to convert Binary Tree to Circular
// Doubly Linked list using the vector which stores
// In-Order traversal of the Binary Tree
function bTreeToCList(root) {
// Base cases
if (root == null)
return null;
// Vector to be used for storing the nodes
// of tree in In-order form
var v = [];
// Calling the In-Order traversal function
inorder(root, v);
// Create the head of the linked list pointing
// to the root of the tree
var head_ref = new Node(v[0]);
// Create a current pointer to be used in traversal
var curr = head_ref;
// Traversing the nodes of the tree starting
// from the second elements
for (i = 1; i < v.length; i++) {
// Create a temporary pointer
// pointing to current
var temp = curr;
// Current's right points to the current
// node in traversal
curr.right = new Node(v[i]);
// Current points to its right
curr = curr.right;
// Current's left points to temp
curr.left = temp;
}
// Current's right points to head of the list
curr.right = head_ref;
// Head's left points to current
head_ref.left = curr;
// Return head of the list
return head_ref;
}
// Display Circular Link List
function displayCList(head) {
document.write("Circular Doubly Linked List is :<br/>");
var itr = head;
do {
document.write(itr.data + " ");
itr = itr.right;
} while (head != itr);
document.write();
}
// Driver Code
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);
var head = bTreeToCList(root);
displayCList(head);
// This code contributed by Rajput-Ji
</script>
Producción:
Circular Doubly Linked List is : 25 12 30 10 36 15
Complejidad de Tiempo : O(N), donde N es el número de Nodes en el Árbol Binario.
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por Abhishek_Vashisht y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA