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

// Программа на 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)

// 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