Рубрики

Преобразовать данное двоичное дерево в двусвязный список | Комплект 1

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

Я встречал это интервью во время одного из моих интервью. Подобная проблема обсуждается в этом посте . Проблема здесь проще, так как нам не нужно создавать циклическую DLL, а просто DLL. Идея его решения довольно проста и прямолинейна.

1. Если левое поддерево существует, обработайте левое поддерево
… .. 1.a) Рекурсивно преобразовать левое поддерево в DLL.
… .. 1.b) Затем найдите предшественника по порядку корня в левом поддереве (предшественник по порядку — самый правый узел в левом поддереве).
… .. 1.c) Сделать предшественник inorder как предыдущий для root, а root как следующий за предшественником inorder.
2. Если существует правое поддерево, обработайте правое поддерево (ниже 3 шага аналогичны левому поддереву).
… .. 2.a) Рекурсивно преобразовать правильное поддерево в DLL.
… .. 2.b) Затем найдите преемника корня корня в правом поддереве (преемник корня — самый левый узел в правом поддереве).
… .. 2.c) Сделать преемник inorder следующим за root и root как предыдущий преемником inorder.
3. Найдите самый левый узел и верните его (самый левый узел всегда является главой преобразованной DLL).

Ниже приведен исходный код для вышеуказанного алгоритма.

C ++

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

using namespace std;

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Это основная функция для преобразования
Дерево в список. Эта функция следует
шаги 1 и 2 приведенного выше алгоритма * /
node* bintree2listUtil(node* root) 

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

    if (root == NULL) 

        return root; 

  

    // Преобразуем левое поддерево и ссылку на корень

    if (root->left != NULL) 

    

        // Конвертировать левое поддерево

        node* left = bintree2listUtil(root->left); 

  

        // Найти порядок предшественника. После этого цикла осталось

        // будет указывать на предшественника inorder

        for (; left->right != NULL; left = left->right); 

  

        // Сделать root следующим за предшественником

        left->right = root; 

  

        // Сделать предшественник как предыдущий из корня

        root->left = left; 

    

  

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

    if (root->right != NULL) 

    

        // Преобразовать правильное поддерево

        node* right = bintree2listUtil(root->right); 

  

        // Найти преемника по порядку. После этого цикла, справа

        // будет указывать на преемника

        for (; right->left != NULL; right = right->left); 

  

        // Сделать рут предыдущим наследником

        right->left = root; 

  

        // Сделать преемника следующим корнем

        root->right = right; 

    

  

    return root; 

  
// Основная функция, которая сначала вызывает
// bintree2listUtil (), затем следует шаг 3
// вышеуказанного алгоритма
node* bintree2list(node *root) 

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

    if (root == NULL) 

        return root; 

  

    // Преобразовать в DLL с помощью bintree2listUtil ()

    root = bintree2listUtil(root); 

  

    // bintree2listUtil () возвращает корневой узел преобразованного

    // DLL. Нам нужен указатель на самый левый узел, который

    // голова построенной DLL, поэтому переместимся на самый левый узел

    while (root->left != NULL) 

        root = root->left; 

  

    return (root); 

  
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и 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 = bintree2list(root); 

  

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

    printList(head); 

  

    return 0; 

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

С

// AC-программа для преобразования двоичного дерева в DLL на месте
#include <stdio.h>

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

struct node

{

    int data;

    node* left;

    node* right;

};

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

  шаги 1 и 2 приведенного выше алгоритма * /

node* bintree2listUtil(node* root)
{

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

    if (root == NULL)

        return root;

  

    // Преобразуем левое поддерево и ссылку на корень

    if (root->left != NULL)

    {

        // Конвертировать левое поддерево

        node* left = bintree2listUtil(root->left);

  

        // Найти порядок предшественника. После этого цикла осталось

        // будет указывать на предшественника inorder

        for (; left->right!=NULL; left=left->right);

  

        // Сделать root следующим за предшественником

        left->right = root;

  

        // Сделать предшественник как предыдущий из корня

        root->left = left;

    }

  

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

    if (root->right!=NULL)

    {

        // Преобразовать правильное поддерево

        node* right = bintree2listUtil(root->right);

  

        // Найти преемника по порядку. После этого цикла, справа

        // будет указывать на преемника

        for (; right->left!=NULL; right = right->left);

  

        // Сделать рут предыдущим наследником

        right->left = root;

  

        // Сделать преемника следующим корнем

        root->right = right;

    }

  

    return root;

}

  
// Основная функция, которая сначала вызывает bintree2listUtil (), затем следует шагу 3
// вышеуказанного алгоритма
node* bintree2list(node *root)
{

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

    if (root == NULL)

        return root;

  

    // Преобразовать в DLL с помощью bintree2listUtil ()

    root = bintree2listUtil(root);

  

    // bintree2listUtil () возвращает корневой узел преобразованного

    // DLL. Нам нужен указатель на самый левый узел, который

    // голова построенной DLL, поэтому переместимся на самый левый узел

    while (root->left != NULL)

        root = root->left;

  

    return (root);

}

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

   данные даны и 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)

    {

        printf("%d ", 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 = bintree2list(root);

  

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

    printList(head);

  

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

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

       следует шагам 1 и 2 приведенного выше алгоритма * /

   

    Node bintree2listUtil(Node node) 

    {

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

        if (node == null)

            return node;

   

        // Преобразуем левое поддерево и ссылку на корень

        if (node.left != null

        {

            // Конвертировать левое поддерево

            Node left = bintree2listUtil(node.left);

   

            // Найти порядок предшественника. После этого цикла осталось

            // будет указывать на предшественника inorder

            for (; left.right != null; left = left.right);

   

            // Сделать root следующим за предшественником

            left.right = node;

   

            // Сделать предшественник как предыдущий из корня

            node.left = left;

        }

   

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

        if (node.right != null

        {

            // Преобразовать правильное поддерево

            Node right = bintree2listUtil(node.right);

   

            // Найти преемника по порядку. После этого цикла, справа

            // будет указывать на преемника

            for (; right.left != null; right = right.left);

   

            // Сделать рут предыдущим наследником

            right.left = node;

   

            // Сделать преемника следующим корнем

            node.right = right;

        }

   

        return node;

    }

   

    // Основная функция, которая сначала вызывает bintree2listUtil (), затем следует

    // шаг 3 вышеуказанного алгоритма

       

    Node bintree2list(Node node) 

    {

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

        if (node == null)

            return node;

   

        // Преобразовать в DLL с помощью bintree2listUtil ()

        node = bintree2listUtil(node);

   

        // bintree2listUtil () возвращает корневой узел преобразованного

        // DLL. Нам нужен указатель на самый левый узел, который

        // голова построенной DLL, поэтому переместимся на самый левый узел

        while (node.left != null)

            node = node.left;

   

        return node;

    }

   

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

    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

        Node head = tree.bintree2list(tree.root);

   

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

        tree.printList(head);

    }

}

питон

# Python программа для конвертации
# двоичное дерево в двусвязный список

  

class Node(object):

      

    "" "Класс узла бинарного дерева имеет

    данные, левый и правый ребенок "" "

    def __init__(self, item):

        self.data = item

        self.left = None

        self.right = None

  

def BTToDLLUtil(root):

      

    "" "Это служебная функция для

    преобразовать двоичное дерево в двойное

    связанный список. Большая часть основной задачи

    делается с помощью этой функции.

    if root is None:

        return root

  

    # Конвертировать левое поддерево

    # и ссылка на root

    if root.left:

          

        # Конвертировать левое поддерево

        left = BTToDLLUtil(root.left)

  

        # Найти по порядку предшественника, после

        # этот цикл, слева будет указывать на

        # inorder предшественник root

        while left.right:

            left = left.right

  

        # Сделать root следующим за предшественником

        left.right = root

          

        # Сделать предшественника как

        # предыдущий корень

        root.left = left

  

    # Конвертировать правильное поддерево

    # и ссылка на root

    if root.right:

          

        # Конвертировать правильное поддерево

        right = BTToDLLUtil(root.right)

  

        # Найти преемника по порядку, после

        # этот цикл справа укажет на

        # inorder наследник корня

        while right.left:

            right = right.left

  

        # Сделать рут как предыдущий

        № преемника

        right.left = root

          

        # Сделать преемником как

        # следующий корень

        root.right = right

  

    return root

  

def BTToDLL(root):

    if root is None:

        return root

  

    # Преобразовать в дважды связанный

    # список с использованием BLLToDLLUtil

    root = BTToDLLUtil(root)

      

    # Нам нужен указатель слева от большинства

    # узел, который является главой

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

    while root.left:

        root = root.left

  

    return root

  

def print_list(head):

      

    "" "Функция для печати заданного

       двусвязный список "" "

    if head is None:

        return

    while head:

        print(head.data, end = " ")

        head = head.right

  
Код водителя

if __name__ == '__main__':

    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 = BTToDLL(root)

    print_list(head)

  
# Этот код добавлен
# от viveksyngh

C #

using System;

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

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

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

       следует шагам 1 и 2 приведенного выше алгоритма * /

  

    public virtual Node bintree2listUtil(Node node)

    {

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

        if (node == null)

        {

            return node;

        }

  

        // Преобразуем левое поддерево и ссылку на корень

        if (node.left != null)

        {

            // Конвертировать левое поддерево

            Node left = bintree2listUtil(node.left);

  

            // Найти порядок предшественника. После этого цикла осталось

            // будет указывать на предшественника inorder

            for (; left.right != null; left = left.right)

            {

                ;

            }

  

            // Сделать root следующим за предшественником

            left.right = node;

  

            // Сделать предшественник как предыдущий из корня

            node.left = left;

        }

  

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

        if (node.right != null)

        {

            // Преобразовать правильное поддерево

            Node right = bintree2listUtil(node.right);

  

            // Найти преемника по порядку. После этого цикла, справа

            // будет указывать на преемника

            for (; right.left != null; right = right.left)

            {

                ;

            }

  

            // Сделать рут предыдущим наследником

            right.left = node;

  

            // Сделать преемника следующим корнем

            node.right = right;

        }

  

        return node;

    }

  

    // Основная функция, которая сначала вызывает bintree2listUtil (), затем следует

    // шаг 3 вышеуказанного алгоритма

  

    public virtual Node bintree2list(Node node)

    {

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

        if (node == null)

        {

            return node;

        }

  

        // Преобразовать в DLL с помощью bintree2listUtil ()

        node = bintree2listUtil(node);

  

        // bintree2listUtil () возвращает корневой узел преобразованного

        // DLL. Нам нужен указатель на самый левый узел, который

        // голова построенной DLL, поэтому переместимся на самый левый узел

        while (node.left != null)

        {

            node = node.left;

        }

  

        return node;

    }

  

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

    public virtual void printList(Node node)

    {

        while (node != null)

        {

            Console.Write(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

        Node head = tree.bintree2list(tree.root);

  

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

        tree.printList(head);

    }

}

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


Выход:

25 12 30 10 36 15

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

Вам также может понравиться конвертировать данное двоичное дерево в двусвязный список | Установите 2 для другого простого и эффективного решения.

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

Преобразовать данное двоичное дерево в двусвязный список | Комплект 1

0.00 (0%) 0 votes