Convertir un árbol binario dado a lista doblemente enlazada (DLL)

En este artículo, vamos a aprender cómo convertir un árbol binario de una DLL (doblemente enlazada Lista) mediante el programa C ++?

Dado un árbol binario y tenemos que convertirlo en una lista doblemente enlazada (DLL).

Convert a given binary Tree to Doubly Linked List (DLL) - 4

Algoritmo:

Para resolver el problema, podemos seguir este algoritmo:

  1. Empezamos a convertir el nodo del árbol de DLL desde el nodo del árbol del extremo derecho para el nodo del árbol de la izquierda.
  2. Cada vez que conectamos el puntero derecho de un nodo a la cabeza de la DLL.
  3. Conectar el puntero izquierdo de la DLL a ese nodo.
  4. Hacer que el nodo a la cabeza de la lista enlazada.
  5. Repita el proceso de derecha a izquierda más nodo del árbol.

implementación en C ++:

#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node* left;
node* right;
};
//Create a new node
struct node* create_node(int x)
{
struct node* temp = new node;
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp;
}
//convert a BST to a DLL
void BinarytoDll(node* root, node** head)
{
if (root == NULL)
return;
BinarytoDll(root->right, head);
root->right = *head;
if (*head != NULL) {
(*head)->left = root;
}
*head = root;
BinarytoDll(root->left, head);
}
//Print the list
void print(node* head)
{
struct node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->right;
}
}
//print the tree in inorder traversal
void print_tree(node* root)
{
if (root == NULL) {
return;
}
print_tree(root->left);
cout << root->data << " ";
print_tree(root->right);
}
int main()
{
struct node* root = create_node(5);
root->left = create_node(6);
root->right = create_node(7);
root->left->left = create_node(8);
root->left->right = create_node(1);
root->right->right = create_node(0);
cout << "Print Tree" << endl;
print_tree(root);
struct node* head = NULL;
BinarytoDll(root, &head);
cout << "nDoubly Linked List" << endl;
print(head);
return 0;
}

salida

Print Tree
8 6 1 5 7 0
Doubly Linked List
8 6 1 5 7 0


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *