Рубрики

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

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

Решение этой проблемы обсуждается в этом посте .
В этом посте обсуждается еще одно простое и эффективное решение. Обсуждаемое здесь решение имеет два простых шага.

1) Исправление левых указателей : на этом шаге мы меняем левые указатели, чтобы они указывали на предыдущие узлы в DLL. Идея проста, мы делаем обход дерева по порядку. При прохождении по порядку мы отслеживаем предыдущий посещенный узел и меняем левый указатель на предыдущий узел. Смотрите fixPrevPtr () в приведенной ниже реализации.

2) Исправить правые указатели : вышеизложенное интуитивно понятно и просто. Как изменить правильные указатели, чтобы указать на следующий узел в DLL? Идея состоит в том, чтобы использовать левые указатели, зафиксированные на шаге 1. Мы начинаем с самого правого узла в двоичном дереве (BT). Самый правый узел — последний узел в DLL. Поскольку левые указатели изменяются, чтобы указывать на предыдущий узел в DLL, мы можем линейно перемещаться по всей DLL, используя эти указатели. Обход будет от последнего к первому узлу. Обходя DLL, мы отслеживаем ранее посещенный узел и меняем правый указатель на предыдущий узел. Смотрите fixNextPtr () в приведенной ниже реализации.

C ++

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

using namespace std;

  
// Узел дерева

class node 

    public:

    int data; 

    node *left, *right; 

}; 

  
// Полезная функция для создания
// новый узел дерева

node *newNode(int data) 

    node *Node = new node();

    Node->data = data; 

    Node->left = Node->right = NULL; 

    return(Node); 

  
// Стандартный Inorder обход дерева

void inorder(node *root) 

    if (root != NULL) 

    

        inorder(root->left); 

        cout << "\t" << root->data; 

        inorder(root->right); 

    

  
// Изменяет левые указатели, чтобы работать как
// предыдущие указатели в преобразованной DLL
// Функция просто делает порядок
// обход бинарного дерева и обновлений
// левый указатель с использованием ранее посещенного узла

void fixPrevPtr(node *root) 

    static node *pre = NULL; 

  

    if (root != NULL) 

    

        fixPrevPtr(root->left); 

        root->left = pre; 

        pre = root; 

        fixPrevPtr(root->right); 

    

  
// Изменяет правильные указатели на работу
// как следующие указатели в преобразованной DLL
node *fixNextPtr(node *root) 

    node *prev = NULL; 

  

    // Найти самый правый узел

    // в BT или последний узел в DLL

    while (root && root->right != NULL) 

        root = root->right; 

  

    // Начнем с самого правого узла,

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

    // Во время обхода меняем правый указатель узлов.

    while (root && root->left != NULL) 

    

        prev = root; 

        root = root->left; 

        root->right = prev; 

    

  

    // Самый левый узел - голова

    // связанного списка, вернуть его

    return (root); 

  
// Основная функция, которая конвертирует
// BST в DLL и возвращает голову DLL
node *BTToDLL(node *root) 

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

    fixPrevPtr(root); 

  

    // Установить следующий указатель и вернуть голову DLL

    return fixNextPtr(root); 

  
// Обходит DLL слева направо

void printList(node *root) 

    while (root != NULL) 

    

        cout<<"\t"<<root->data; 

        root = root->right; 

    

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

int main(void

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

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

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

  

    cout<<"\n\t\tInorder Tree Traversal\n\n"

    inorder(root); 

  

    node *head = BTToDLL(root); 

  

    cout << "\n\n\t\tDLL Traversal\n\n"

    printList(head); 

    return 0; 

}

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

С

// Простая программа, основанная на прохождении по порядку, для преобразования двоичного дерева в DLL
#include<stdio.h>
#include<stdlib.h>

  
// Узел дерева

struct node

{

    int data;

    struct node *left, *right;

};

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

struct node *newNode(int data)

{

    struct node *node = (struct node *)malloc(sizeof(struct node));

    node->data = data;

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

    return(node);

}

  
// Стандартный Inorder обход дерева

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("\t%d",root->data);

        inorder(root->right);

    }

}

  
// Изменяет левые указатели для работы в качестве предыдущих указателей в преобразованной DLL
// Функция просто выполняет обход бинарного дерева и обновляет его
// левый указатель с использованием ранее посещенного узла

void fixPrevPtr(struct node *root)

{

    static struct node *pre = NULL;

  

    if (root != NULL)

    {

        fixPrevPtr(root->left);

        root->left = pre;

        pre = root;

        fixPrevPtr(root->right);

    }

}

  
// Изменяет правильные указатели для работы в качестве следующих указателей в преобразованной DLL

struct node *fixNextPtr(struct node *root)

{

    struct node *prev = NULL;

  

    // Найти самый правый узел в BT или последний узел в DLL

    while (root && root->right != NULL)

        root = root->right;

  

    // Начинаем с самого правого узла, возвращаемся назад, используя левые указатели.

    // Во время обхода меняем правый указатель узлов.

    while (root && root->left != NULL)

    {

        prev = root;

        root = root->left;

        root->right = prev;

    }

  

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

    return (root);

}

  
// Основная функция, которая конвертирует BST в DLL и возвращает голову DLL

struct node *BTToDLL(struct node *root)

{

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

    fixPrevPtr(root);

  

    // Установить следующий указатель и вернуть голову DLL

    return fixNextPtr(root);

}

  
// Обходит DLL слева направо

void printList(struct node *root)

{

    while (root != NULL)

    {

        printf("\t%d", root->data);

        root = root->right;

    }

}

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

int main(void)

{

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

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

  

    printf("\n\t\tInorder Tree Traversal\n\n");

    inorder(root);

  

    struct node *head = BTToDLL(root);

  

    printf("\n\n\t\tDLL Traversal\n\n");

    printList(head);

    return 0;

}

Джава

// Java-программа для преобразования BTT в DLL с использованием
// простой обход заказа

  

public class BinaryTreeToDLL 

{

    static class node 

    {

        int data;

        node left, right;

  

        public node(int data) 

        {

            this.data = data;

        }

    }

  

    static node prev;

  

    // Изменяет левые указатели на прежние

    // указатели в преобразованной DLL Функция

    // просто выполняет обход по двоичному

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

    // ранее посещенный узел

    static void fixPrevptr(node root) 

    {

        if (root == null)

            return;

  

        fixPrevptr(root.left);

        root.left = prev;

        prev = root;

        fixPrevptr(root.right);

  

    }

  

    // Изменяет правильные указатели на работу

    // как следующие указатели в преобразованной DLL

    static node fixNextptr(node root) 

    {        

        // Найти самый правый узел в

        // BT или последний узел в DLL

        while (root.right != null)

            root = root.right;

  

        // Старт с самого правого узла, траверс

        // назад используя левые указатели. Во время прохождения,

        // меняем правый указатель узлов

        while (root != null && root.left != null

        {

            node left = root.left;

            left.right = root;

            root = root.left;

        }

  

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

        return root;

    }

  

    static node BTTtoDLL(node root) 

    {

        prev = null;

  

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

        fixPrevptr(root);

  

        // Установить следующий указатель и вернуть голову DLL

        return fixNextptr(root);

    }

  

    // Обходит DLL слева направо

    static void printlist(node root) 

    {

        while (root != null

        {

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

            root = root.right;

        }

    }

  

    // Стандартный Inorder обход дерева

    static void inorder(node root) 

    {

        if (root == null)

            return;

        inorder(root.left);

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

        inorder(root.right);

    }

  

    public static void main(String[] args) 

    {

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

        node root = new node(10);

        root.left = new node(12);

        root.right = new node(15);

        root.left.left = new node(25);

        root.left.right = new node(30);

        root.right.left = new node(36);

  

        System.out.println("Inorder Tree Traversal");

        inorder(root);

  

        node head = BTTtoDLL(root);

  

        System.out.println("\nDLL Traversal");

        printlist(head);

    }

}

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

питон

# Простая программа на основе обхода по порядку для преобразования
# Двоичное дерево в DLL

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла дерева

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Стандартный Inorder обход дерева

def inorder(root):

      

    if root is not None:

        inorder(root.left)

        print "\t%d" %(root.data),

        inorder(root.right)

  
# Изменяет левые указатели, чтобы работать как предыдущие указатели
# в преобразованной DLL
# Функция просто выполняет обход по порядку
# Двоичное дерево и обновления
# левый указатель с использованием ранее посещенного узла

def fixPrevPtr(root):

    if root is not None:

        fixPrevPtr(root.left)

        root.left = fixPrevPtr.pre

        fixPrevPtr.pre = root 

        fixPrevPtr(root.right)

  
# Изменяет правильные указатели для работы в качестве указателей nexr в
# преобразованная DLL

def fixNextPtr(root):

  

    prev = None

    # Найти самый правый узел в BT или последний узел в DLL

    while(root and root.right != None):

        root = root.right 

  

    # Начать с самого правого узла, пройти назад, используя

    # левые указатели

    # Во время обхода меняйте правый указатель узлов

    while(root and root.left != None):

        prev = root 

        root = root.left 

        root.right = prev

  

    # Самый левый узел - заголовок связанного списка, верните его

    return root 

  
# Основная функция, которая конвертирует BST в DLL и возвращает
# глава DLL

def BTToDLL(root):

      

    # Установить предыдущий указатель

    fixPrevPtr(root)

  

    # Установить следующий указатель и вернуть голову DLL

    return fixNextPtr(root)

  
# Обходит DLL слева направо

def printList(root):

    while(root != None):

        print "\t%d" %(root.data),

        root = root.right

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

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)

  

print "\n\t\t Inorder Tree Traversal\n"

inorder(root)

  
# Статическая переменная pre для функции fixPrevPtr

fixPrevPtr.pre = None

head = BTToDLL(root)

  

print "\n\n\t\tDLL Traversal\n"

printList(head)

      
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для преобразования BTT в DLL с помощью
// простой обход заказа

using System;

  

class GFG

{

public class node

{

    public int data;

    public node left, right;

  

    public node(int data)

    {

        this.data = data;

    }

}

  

public static node prev;

  
// Изменяет левые указатели на прежние
// указатели в преобразованной DLL Функция
// просто выполняет обход по двоичному
// Дерево и обновляет левый указатель используя
// ранее посещенный узел

public static void fixPrevptr(node root)

{

    if (root == null)

    {

        return;

    }

  

    fixPrevptr(root.left);

    root.left = prev;

    prev = root;

    fixPrevptr(root.right);

  
}

  
// Изменяет правильные указатели на работу
// как следующие указатели в преобразованной DLL

public static node fixNextptr(node root)

{

    // Найти самый правый узел в

    // BT или последний узел в DLL

    while (root.right != null)

    {

        root = root.right;

    }

  

    // Старт с самого правого узла, траверс

    // назад используя левые указатели. Во время прохождения,

    // меняем правый указатель узлов

    while (root != null && root.left != null)

    {

        node left = root.left;

        left.right = root;

        root = root.left;

    }

  

    // Самый левый узел является главой

    // связанный список, вернуть его

    return root;

}

  

public static node BTTtoDLL(node root)

{

    prev = null;

  

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

    fixPrevptr(root);

  

    // Установить следующий указатель и

    // возвращаем голову DLL

    return fixNextptr(root);

}

  
// Обходит DLL слева направо

public static void printlist(node root)

{

    while (root != null)

    {

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

        root = root.right;

    }

}

  
// Стандартный Inorder обход дерева

public static void inorder(node root)

{

    if (root == null)

    {

        return;

    }

    inorder(root.left);

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

    inorder(root.right);

}

  

public static void Main()

{

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

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

    node root = new node(10);

    root.left = new node(12);

    root.right = new node(15);

    root.left.left = new node(25);

    root.left.right = new node(30);

    root.right.left = new node(36);

  

    Console.WriteLine("Inorder Tree Traversal");

    inorder(root);

  

    node head = BTTtoDLL(root);

  

    Console.WriteLine("\nDLL Traversal");

    printlist(head);

}
}

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


Выход:

                Inorder Tree Traversal

        25      12      30      10      36      15

                DLL Traversal

        25      12      30      10      36      15

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

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

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

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

0.00 (0%) 0 votes