Рубрики

Преобразовать данное двоичное дерево в двусвязный список | Набор 3

Получив двоичное дерево (BT), преобразуйте его в список двусвязных списков (DLL) на месте. Левый и правый указатели в узлах должны использоваться как предыдущий и следующий указатели соответственно в преобразованной DLL. Порядок узлов в DLL должен совпадать с порядком следования данного двоичного дерева. Первый узел обхода Inorder (самый левый узел в BT) должен быть головным узлом DLL.

Следующие два различных решения были обсуждены для этой проблемы.
Преобразовать данное двоичное дерево в двусвязный список | Комплект 1
Преобразовать данное двоичное дерево в двусвязный список | Набор 2

В этом посте обсуждается третье решение, которое кажется самым простым из всех. Идея состоит в том, чтобы выполнить обход по порядку двоичного дерева. При выполнении обхода inorder отслеживайте ранее посещенный узел в переменной скажем prev . Для каждого посещенного узла сделайте его следующим из prev и previous этого узла как prev .

Спасибо rahul, wishall и всем остальным читателям за их полезные комментарии к вышеупомянутым двум постам.

Ниже приводится реализация этого решения.

C ++

// Программа на C ++ для преобразования двоичного дерева в DLL на месте
#include <iostream>

using namespace std;

  
/ * Узел двоичного дерева имеет данные, а также левый и правый указатели * /

struct node

{

    int data;

    node* left;

    node* right;

};

  
// Простая рекурсивная функция для преобразования заданного двоичного дерева в Doubly
// Связанный список
// root -> Root of Binary Tree
// head -> Указатель на головной узел созданного двусвязного списка

void BinaryTree2DoubleLinkedList(node *root, node **head)

{

    // Базовый вариант

    if (root == NULL) return;

  

    // Инициализируем ранее посещенный узел как NULL. Это

    // статический, чтобы одно и то же значение было доступно во всех рекурсивных

    // звонки

    static node* prev = NULL;

  

    // Рекурсивно конвертировать левое поддерево

    BinaryTree2DoubleLinkedList(root->left, head);

  

    // Теперь конвертируем этот узел

    if (prev == NULL)

        *head = root;

    else

    {

        root->left = prev;

        prev->right = root;

    }

    prev = root;

  

    // Окончательно конвертируем правое поддерево

    BinaryTree2DoubleLinkedList(root->right, head);

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

node* newNode(int data)

{

    node* new_node = new node;

    new_node->data = data;

    new_node->left = new_node->right = NULL;

    return (new_node);

}

  
/ * Функция для печати узлов в заданном двусвязном списке * /

void printList(node *node)

{

    while (node!=NULL)

    {

        cout << node->data << " ";

        node = node->right;

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    // Давайте создадим дерево, показанное на диаграмме выше

    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);

  

    // Конвертировать в DLL

    node *head = NULL;

    BinaryTree2DoubleLinkedList(root, &head);

  

    // Распечатать преобразованный список

    printList(head);

  

    return 0;

}

Джава

// Java-программа для преобразования двоичного дерева в DLL на месте

   
// Узел двоичного дерева имеет данные, левые указатели и правые указатели

class Node 

{

    int data;

    Node left, right;

   

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

       

    // head -> Указатель на головной узел созданного двусвязного списка

    Node head;

       

    // Инициализируем ранее посещенный узел как NULL. Это

    // статический, чтобы одно и то же значение было доступно во всех рекурсивных

    // звонки

    static Node prev = null;

   

    // Простая рекурсивная функция для преобразования заданного двоичного дерева

    // к двусвязному списку

    // root -> Root of Binary Tree

    void BinaryTree2DoubleLinkedList(Node root) 

    {

        // Базовый вариант

        if (root == null)

            return;

   

        // Рекурсивно конвертировать левое поддерево

        BinaryTree2DoubleLinkedList(root.left);

   

        // Теперь конвертируем этот узел

        if (prev == null

            head = root;

        else

        {

            root.left = prev;

            prev.right = root;

        }

        prev = root;

   

        // Окончательно конвертируем правое поддерево

        BinaryTree2DoubleLinkedList(root.right);

    }

   

    / * Функция для печати узлов в заданном двусвязном списке * /

    void printList(Node node)

    {

        while (node != null

        {

            System.out.print(node.data + " ");

            node = node.right;

        }

    }

   

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        // Давайте создадим дерево, как показано на диаграмме выше

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(12);

        tree.root.right = new Node(15);

        tree.root.left.left = new Node(25);

        tree.root.left.right = new Node(30);

        tree.root.right.left = new Node(36);

   

        // преобразовать в DLL

        tree.BinaryTree2DoubleLinkedList(tree.root);

           

        // Распечатать преобразованный список

        tree.printList(tree.head);

   

    }

}
// Этот код предоставлен Mayank Jaiswal (mayank_24)

C #

// AC # программа для преобразования на месте
// двоичного дерева в DLL

using System;

  
// У узла двоичного дерева есть данные, слева
// указатели и правильные указатели

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  
// head -> Указатель на головной узел
// создал двусвязный список

public Node head;

  
// Инициализируем ранее посещенный узел
// как NULL. Это статично, так что
// одно и то же значение доступно во всех
// рекурсивные вызовы

public static Node prev = null;

  
// Простая рекурсивная функция для
// преобразовать данное двоичное дерево
// к двусвязному списку
// root -> Root of Binary Tree

public virtual void BinaryTree2DoubleLinkedList(Node root)

{

    // Базовый вариант

    if (root == null)

    {

        return;

    }

  

    // Рекурсивно конвертировать левое поддерево

    BinaryTree2DoubleLinkedList(root.left);

  

    // Теперь конвертируем этот узел

    if (prev == null)

    {

        head = root;

    }

    else

    {

        root.left = prev;

        prev.right = root;

    }

    prev = root;

  

    // Окончательно конвертируем правое поддерево

    BinaryTree2DoubleLinkedList(root.right);

}

  
/ * Функция для печати узлов в

   данный двусвязный список * /

public virtual void printList(Node node)

{

    while (node != null)

    {

        Console.Write(node.data + " ");

        node = node.right;

    }

}

  
// Код драйвера

public static void Main(string[] args)

{

    // Давайте создадим дерево как

    // показано на диаграмме выше

    GFG tree = new GFG();

    tree.root = new Node(10);

    tree.root.left = new Node(12);

    tree.root.right = new Node(15);

    tree.root.left.left = new Node(25);

    tree.root.left.right = new Node(30);

    tree.root.right.left = new Node(36);

  

    // преобразовать в DLL

    tree.BinaryTree2DoubleLinkedList(tree.root);

  

    // Распечатать преобразованный список

    tree.printList(tree.head);

  
}
}

  
// Этот код предоставлен Shrikant13


Выход:

25 12 30 10 36 15

Обратите внимание, что использование статических переменных, как указано выше, не рекомендуется (мы использовали статические для простоты). Представьте себе ситуацию, когда одна и та же функция вызывается для двух или более деревьев, при следующем вызове для другого дерева будет использоваться старое значение prev . Чтобы избежать таких проблем, мы можем использовать двойной указатель или ссылку на указатель.

Сложность времени: вышеупомянутая программа выполняет простой обход по порядку, поэтому сложность времени равна O (n), где n — количество узлов в данном двоичном дереве.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Преобразовать данное двоичное дерево в двусвязный список | Набор 3

0.00 (0%) 0 votes