Рубрики

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

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

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

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

C ++

// C ++ программа для преобразования заданного двоичного файла
// Дерево к двусвязному списку
#include <stdio.h>
#include <stdlib.h>

  
// Структура для дерева и связанного списка

struct Node

{

    int data;

    Node *left, *right;

};

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

void BToDLL(Node* root, Node** head_ref)

{

    // Базовые случаи

    if (root == NULL)

        return;

  

    // Рекурсивное преобразование правого поддерева

    BToDLL(root->right, head_ref);

  

    // вставляем корень в DLL

    root->right = *head_ref;

  

    // Изменить левый указатель предыдущей головы

    if (*head_ref != NULL)

        (*head_ref)->left = root;

  

    // Изменить заголовок двусвязного списка

    *head_ref = root;

  

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

    BToDLL(root->left, head_ref);

}

  
// Сервисная функция для выделения узла для двоичного файла
// Дерево.

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Утилита для печати двойного связанного списка.

void printList(Node* head)

{

    printf("Extracted Double Linked list is:\n");

    while (head)

    {

        printf("%d ", head->data);

        head = head->right;

    }

}

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

int main()

{

    / * Построение под деревом

               5

             / /

            3 6

           ///

          1 4 8

         / / / /

        0 2 7 9 * /

    Node* root = newNode(5);

    root->left = newNode(3);

    root->right = newNode(6);

    root->left->left = newNode(1);

    root->left->right = newNode(4);

    root->right->right = newNode(8);

    root->left->left->left = newNode(0);

    root->left->left->right = newNode(2);

    root->right->right->left = newNode(7);

    root->right->right->right = newNode(9);

  

    Node* head = NULL;

    BToDLL(root, &head);

  

    printList(head);

  

    return 0;

}

Джава

// Java-программа для преобразования заданного двоичного дерева в
// Двусвязный список

  
/ * Структура для дерева и связного списка * /

class Node 

{

    int data;

    Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  

class BinaryTree 

{

    // 'root' - корень двоичного дерева

    Node root;

      

    // 'head' - ссылка на головной узел созданного

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

    Node head;

  

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

    // Двоичное дерево в двусвязный список

    void BToDLL(Node root) 

    {

        // Базовые случаи

        if (root == null)

            return;

  

        // Рекурсивное преобразование правого поддерева

        BToDLL(root.right);

  

        // вставляем корень в DLL

        root.right = head;

  

        // Изменить левый указатель предыдущей головы

        if (head != null)

            (head).left = root;

  

        // Изменить заголовок двусвязного списка

        head = root;

  

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

        BToDLL(root.left);

    }

  

    // Утилита для печати двойного связанного списка.

    void printList(Node head) 

    {

        System.out.println("Extracted Double Linked List is : ");

        while (head != null

        {

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

            head = head.right;

        }

    }

  

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

    public static void main(String[] args) 

    {

        / * Построение под деревом

               5

             / /

            3 6

           ///

          1 4 8

         / / / /

        0 2 7 9 * /

          

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(5);

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

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

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

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

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

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

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

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

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

  

        tree.BToDLL(tree.root);

        tree.printList(tree.head);

    }

}

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

python3

# Python3 программа для преобразования заданного двоичного файла
# Дерево к двусвязному списку

class Node:

    def __init__(self, data):

        self.data = data

        self.left = self.right = None

  

class BinaryTree:

    root, head = None, None

      

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

    # Двоичное дерево в двусвязный список

    def BToDll(self, root: Node):

        if root is None:

            return

  

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

        self.BToDll(root.right)

  

        # Вставить root в двусвязный список

        root.right = self.head

  

        # Изменить левый указатель предыдущей головы

        if self.head is not None:

            self.head.left = root

  

        # Изменить заголовок двусвязного списка

        self.head = root

  

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

        self.BToDll(root.left)

  

    @staticmethod

    def print_list(head: Node):

        print('Extracted Double Linked list is:')

        while head is not None:

            print(head.data, end = ' ')

            head = head.right

  
Код водителя

if __name__ == '__main__':

      

    «»»

    Построение под деревом

            5

        // //

        3 6

        // // //

        1 4 8

    // // // //

    0 2 7 9

    «»»

    tree = BinaryTree()

    tree.root = Node(5)

    tree.root.left = Node(3)

    tree.root.right = Node(6)

    tree.root.left.left = Node(1)

    tree.root.left.right = Node(4)

    tree.root.right.right = Node(8)

    tree.root.left.left.left = Node(0)

    tree.root.left.left.right = Node(2)

    tree.root.right.right.left = Node(7)

    tree.root.right.right.right = Node(9)

  

    tree.BToDll(tree.root)

    tree.print_list(tree.head)

  
# Этот код предоставлен Раджатом Шриваставой

C #

// C # программа для преобразования заданного двоичного файла
// Дерево к двусвязному списку

using System;

  
/ * Структура для дерева и связного списка * /

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  

class GFG

{
// 'root' - корень двоичного дерева

public Node root;

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

public Node head;

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

public virtual void BToDLL(Node root)

{

    // Базовые случаи

    if (root == null)

    {

        return;

    }

  

    // Рекурсивное преобразование правого поддерева

    BToDLL(root.right);

  

    // вставляем корень в DLL

    root.right = head;

  

    // Изменить левый указатель предыдущей головы

    if (head != null)

    {

        (head).left = root;

    }

  

    // Изменить заголовок двусвязного списка

    head = root;

  

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

    BToDLL(root.left);

}

  
// Сервисная функция для печати
// двойной связанный список.

public virtual void printList(Node head)

{

    Console.WriteLine("Extracted Double "

                      "Linked List is : ");

    while (head != null)

    {

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

        head = head.right;

    }

}

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

public static void Main(string[] args)

{

    / * Построение под деревом

        5

        / /

        3 6

    ///

    1 4 8

    / / / /

    0 2 7 9 * /

  

    GFG tree = new GFG();

    tree.root = new Node(5);

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

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

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

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

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

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

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

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

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

  

    tree.BToDLL(tree.root);

    tree.printList(tree.head);

}
}

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

Выход :

Extracted Double Linked list is:
0 1 2 3 4 5 6 7 8 9

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

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

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

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

0.00 (0%) 0 votes