Рубрики

Преобразование двоичного дерева в двусвязный список по спирали

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

Решение не должно выделять дополнительную память для узлов DLL. Для создания DLL следует использовать узлы двоичного дерева, т. Е. Допускается только смена указателей.

Например, для дерева на левой стороне, Двойно связанный список может быть,

1 2 3 7 6 5 4 8 9 10 11 13 14 или

1 3 2 4 5 6 7 14 13 11 10 9 8 .

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Мы можем сделать это, выполнив обход по спирали в течение O (n) времени и O (n) дополнительного пространства. Идея состоит в том, чтобы использовать deque (двустороннюю очередь), который можно расширять или сжимать на обоих концах (либо спереди, либо сзади). Мы делаем что-то похожее на обход уровня порядка, но чтобы поддерживать спиральный порядок, для каждого нечетного уровня мы снимаем узел с фронта и вставляем его левого и правого потомков в конец структуры данных deque. И для каждого четного уровня мы снимаем узел со спины и вставляем его правого и левого потомков в начало deque. Мы также поддерживаем стек для хранения узлов двоичного дерева. Всякий раз, когда мы извлекаем узлы из deque, мы помещаем этот узел в стек. Позже мы извлекаем все узлы из стека и помещаем узлы в начало списка. Мы можем избежать использования стека, если мы поддерживаем хвостовой указатель, который всегда указывает на последний узел DLL и вставляет узлы за O (1) раз в конце.

Ниже приведена реализация вышеуказанной идеи.

C ++

/ * c ++ программа для преобразования Binary Tree в Doubly

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

   спирально. * /

#include <bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    struct Node *left, *right;

};

  
/ * Учитывая ссылку на заголовок списка и узел,
вставляет узел в начало списка. * /

void push(Node** head_ref, Node* node)

{

    // Сделать право на данный узел как голову, а левое как

    // ЗНАЧЕНИЕ NULL

    node->right = (*head_ref);

    node->left = NULL;

  

    // меняем левый от головного узла на данный узел

    if ((*head_ref) !=  NULL)

        (*head_ref)->left = node ;

  

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

    (*head_ref) = node;

}

  
// Функция для печати содержимого DLL

void printList(Node *node)

{

    while (node != NULL)

    {

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

        node = node->right;

    }

}

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

void spiralLevelOrder(Node *root)

{

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

    if (root == NULL)

        return;

  

    // Создать пустую деку для спирали

    // уровень прохождения порядка и постановка в очередь root

    deque<Node*> q;

    q.push_front(root);

  

    // создаем стек для хранения узлов двоичного дерева

    // вставить в DLL позже

    stack<Node*> stk;

  

    int level = 0;

    while (!q.empty())

    {

        // nodeCount указывает количество узлов

        // на текущем уровне.

        int nodeCount = q.size();

  

        // Удаление всех узлов текущего уровня и

        // ставим в очередь все узлы следующего уровня

        if (level&1)    // нечетный уровень

        {

            while (nodeCount > 0)

            {

                // снимаем узел с фронта и выдвигаем его

                // стек

                Node *node = q.front();

                q.pop_front();

                stk.push(node);

  

                // вставляем левого и правого потомка

                // в задней части deque

                if (node->left != NULL)

                    q.push_back(node->left);

                if (node->right != NULL)

                    q.push_back(node->right);

  

                nodeCount--;

            }

        }

        else      // четный уровень

        {

            while (nodeCount > 0)

            {

                // снимаем узел со спины и толкаем его

                // укладывать

                Node *node = q.back();

                q.pop_back();

                stk.push(node);

  

                // вставляет своих правых и левых детей

                // в передней части deque

                if (node->right != NULL)

                    q.push_front(node->right);

                if (node->left != NULL)

                    q.push_front(node->left);

                nodeCount--;

            }

        }

        level++;

    }

  

    // указатель головы для DLL

    Node* head = NULL;

  

    // извлекаем все узлы из стека и

    // толкаем их в начало списка

    while (!stk.empty())

    {

        push(&head, stk.top());

        stk.pop();

    }

  

    cout << "Created DLL is:\n";

    printList(head);

}

  
// Сервисная функция для создания нового дерева Node

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

  

    return temp;

}

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

int main()

{

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

    Node *root =  newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

  

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

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

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

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

    // root-> right-> left-> left = newNode (12);

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

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

    // root-> right-> right-> right = newNode (15);

  

    spiralLevelOrder(root);

  

    return 0;

}

Джава

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

   где узлы представлены спирально * /

  

import java.util.*;

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

class Node 

{

    int data;

    Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

    Node head;

  

    / * Учитывая ссылку на узел,

       вставляет узел в начало списка. * /

    void push(Node node) 

    {

        // Сделать право на данный узел как голову, а левое как

        // ЗНАЧЕНИЕ NULL

        node.right = head;

        node.left = null;

  

        // меняем левый от головного узла на данный узел

        if (head != null

            head.left = node;

              

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

        head = node;

    }

  

    // Функция для печати содержимого DLL

    void printList(Node node) 

    {

        while (node != null

        {

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

            node = node.right;

        }

    }

  

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

    void spiralLevelOrder(Node root) 

    {

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

        if (root == null)

            return;

  

        // Создать пустую деку для спирали

        // уровень прохождения порядка и постановка в очередь root

        Deque<Node> q = new LinkedList<Node>();

        q.addFirst(root);

  

        // создаем стек для хранения узлов двоичного дерева

        // вставить в DLL позже

        Stack<Node> stk = new Stack<Node>();

  

        int level = 0;

        while (!q.isEmpty()) 

        {

            // nodeCount указывает количество узлов

            // на текущем уровне.

            int nodeCount = q.size();

  

            // Удаление всех узлов текущего уровня и

            // ставим в очередь все узлы следующего уровня

            if ((level & 1) %2 != 0) // нечетный уровень

            {

                while (nodeCount > 0

                {

                    // снимаем узел с фронта и выдвигаем его

                    // стек

                    Node node = q.peekFirst();

                    q.pollFirst();

                    stk.push(node);

  

                    // вставляем левого и правого потомка

                    // в задней части deque

                    if (node.left != null)

                        q.addLast(node.left);

                    if (node.right != null)

                        q.addLast(node.right);

  

                    nodeCount--;

                }

            

            else // четный уровень

            {

                while (nodeCount > 0

                {

                    // снимаем узел со спины и толкаем его

                    // укладывать

                    Node node = q.peekLast();

                    q.pollLast();

                    stk.push(node);

  

                    // вставляет своих правых и левых детей

                    // в передней части deque

                    if (node.right != null)

                        q.addFirst(node.right);

                    if (node.left != null)

                        q.addFirst(node.left);

                    nodeCount--;

                }

            }

            level++;

        }

  

        // извлекаем все узлы из стека и

        // толкаем их в начало списка

        while (!stk.empty()) 

        {

            push(stk.peek());

            stk.pop();

        }

  

        System.out.println("Created DLL is : ");

        printList(head);

    }

  

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

    public static void main(String[] args) 

    {

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

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

  

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

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

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

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

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

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

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

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

  

        tree.spiralLevelOrder(tree.root);

    }

}

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

python3

# Python3 программа для преобразования двоичного дерева
# в двусвязный список, где узлы
# представлены по спирали.

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

class newNode: 

  

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

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

          
"" "Приведена ссылка на заголовок списка

    и узел, вставляет узел на передней

    из списка. «»»

def push(head_ref, node):

  

    # Сделать право данного узла как

    # голова и слева как None

    node.right = (head_ref)

    node.left = None

  

    # изменить слева от головного узла на

    # данный узел

    if ((head_ref) != None):

        (head_ref).left = node 

  

    # переместите голову, чтобы указать на

    # данный узел

    (head_ref) = node

  
# Функция для печати содержимого DLL

def printList(node):

    i = 0

    while (i < len(node)):

      

        print(node[i].data, end = " ")

        i += 1

      
"" "Функция узла prcorner на каждом уровне" ""

def spiralLevelOrder(root):

  

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

    if (root == None):

        return

  

    # Создать пустую деку для выполнения спирали

    # уровень порядка обхода и постановки в очередь root

    q = []

    q.append(root)

  

    # создать стек для хранения бинарных файлов

    # Узлы дерева для вставки в DLL позже

    stk = []

  

    level = 0

    while (len(q)):

      

        # nodeCount указывает количество

        # Узлы на текущем уровне.

        nodeCount = len(q) 

          

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

        # и поставить в очередь все узлы следующего уровня

        if (level&1): # нечетный уровень

            while (nodeCount > 0):

              

                # dequeue node from front &

                # толкать его в стек

                node = q[0]

                q.pop(0)

                stk.append(node)

  

                # вставьте его левого и правого детей

                # в задней части deque

                if (node.left != None):

                    q.append(node.left)

                if (node.right != None):

                    q.append(node.right)

  

                nodeCount -= 1

              

        else:     # четный уровень

          

            while (nodeCount > 0):

              

                # узел удаления со спины &

                # толкать его в стек

                node = q[-1]

                q.pop(-1)

                stk.append(node)

  

                # вставляет его справа и слева

                # дети перед

                # deque

                if (node.right != None):

                    q.insert(0, node.right)

                if (node.left != None):

                    q.insert(0, node.left)

                nodeCount -= 1

        level += 1

          

    # указатель головы для DLL

    head = []

      

    # вытолкнуть все узлы из стека и нажать

    # их в начале списка

    while (len(stk)):

      

        head.append(stk[0])

        stk.pop(0)

  

    print("Created DLL is:")

    printList(head)

  
Код водителя

if __name__ == '__main__':

      

    "" "Давайте создадим двоичное дерево как

    показано в примере выше "" "

  

    root = newNode(1)

    root.left = newNode(2)

    root.right = newNode(3)

    root.left.left = newNode(4)

    root.left.right = newNode(5)

    root.right.left = newNode(6)

    root.right.right = newNode(7)

  

    root.left.left.left = newNode(8)

    root.left.left.right = newNode(9)

    root.left.right.left = newNode(10)

    root.left.right.right = newNode(11)

    # root.right.left.left = newNode (12)

    root.right.left.right = newNode(13)

    root.right.right.left = newNode(14)

    # root.right.right.right = newNode (15)

  

    spiralLevelOrder(root)

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

C #

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

using System;

using System.Collections.Generic;

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

public class Node 

{

    public int data;

    public Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  

public class BinaryTree 

{

    Node root;

    Node head;

  

    / * Учитывая ссылку на узел,

    вставляет узел в начало списка. * /

    void push(Node node) 

    {

        // Сделать право на данный узел как голову, а левое как

        // ЗНАЧЕНИЕ NULL

        node.right = head;

        node.left = null;

  

        // меняем левый от головного узла на данный узел

        if (head != null

            head.left = node;

              

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

        head = node;

    }

  

    // Функция для печати содержимого DLL

    void printList(Node node) 

    {

        while (node != null

        {

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

            node = node.right;

        }

    }

  

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

    void spiralLevelOrder(Node root) 

    {

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

        if (root == null)

            return;

  

        // Создать пустую деку для спирали

        // уровень прохождения порядка и постановка в очередь root

        LinkedList<Node> q = new LinkedList<Node>();

        q.AddFirst(root);

  

        // создаем стек для хранения узлов двоичного дерева

        // вставить в DLL позже

        Stack<Node> stk = new Stack<Node>();

  

        int level = 0;

        while (q.Count != 0) 

        {

            // nodeCount указывает количество узлов

            // на текущем уровне.

            int nodeCount = q.Count;

  

            // Удаление всех узлов текущего уровня и

            // ставим в очередь все узлы следующего уровня

            if ((level & 1) % 2 != 0) // нечетный уровень

            {

                while (nodeCount > 0) 

                {

                    // снимаем узел с фронта и выдвигаем его

                    // стек

                    Node node = q.First.Value;

                    q.RemoveFirst();

                    stk.Push(node);

  

                    // вставляем левого и правого потомка

                    // в задней части deque

                    if (node.left != null)

                        q.AddLast(node.left);

                    if (node.right != null)

                        q.AddLast(node.right);

  

                    nodeCount--;

                }

            

            else // четный уровень

            {

                while (nodeCount > 0) 

                {

                    // снимаем узел со спины и толкаем его

                    // укладывать

                    Node node = q.Last.Value;

                    q.RemoveLast();

                    stk.Push(node);

  

                    // вставляет своих правых и левых детей

                    // в передней части deque

                    if (node.right != null)

                        q.AddFirst(node.right);

                    if (node.left != null)

                        q.AddFirst(node.left);

                    nodeCount--;

                }

            }

            level++;

        }

  

        // извлекаем все узлы из стека и

        // толкаем их в начало списка

        while (stk.Count != 0) 

        {

            push(stk.Peek());

            stk.Pop();

        }

  

        Console.WriteLine("Created DLL is : ");

        printList(head);

    }

  

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

    public static void Main(String[] args) 

    {

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

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

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

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

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

  

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

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

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

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

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

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

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

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

  

        tree.spiralLevelOrder(tree.root);

    }

}

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


Выход :

Created DLL is:
1 2 3 7 6 5 4 8 9 10 11 13 14 

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Преобразование двоичного дерева в двусвязный список по спирали

0.00 (0%) 0 votes