Рубрики

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

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

Если корневой узел хранится в индексе i, его левый и правый дочерние элементы хранятся в индексах 2 * i + 1, 2 * i + 2 соответственно.
Предположим, что дерево представлено связанным списком таким же образом, как мы можем преобразовать это в нормальное связанное представление двоичного дерева, где каждый узел имеет данные, левый и правый указатели? В представлении связанного списка мы не можем получить прямой доступ к дочерним элементам текущего узла, пока не пройдем по списку.

В основном мы получаем прохождение порядка уровней в форме последовательного доступа. Мы знаем, что заголовок связанного списка всегда является корнем дерева. Мы берем первый узел как корень, и мы также знаем, что следующие два узла — левый и правый потомки корня. Итак, мы знаем частичное двоичное дерево. Идея состоит в том, чтобы выполнить обход порядка уровня частично построенного двоичного дерева с использованием очереди и одновременно пройти по связанному списку. На каждом шаге мы берем родительский узел из очереди, делаем следующие два узла связанного списка дочерними по отношению к родительскому узлу и ставим в очередь следующие два узла в очередь.

1. Создайте пустую очередь.
2. Сделайте первый узел списка корневым и поместите его в очередь.
3. Пока мы не достигнем конца списка, сделайте следующее.
……… . Исключите один узел из очереди. Это текущий родитель.
……… б. Пройдите через два узла в списке, добавьте их в качестве дочерних элементов текущего родителя.
……… с. Поставьте два узла в очередь.

Ниже приведен код, который реализует то же самое в C ++.

C ++

// C ++ программа для создания полного двоичного дерева из его связанного списка
// Представление
#include <iostream>
#include <string>
#include <queue>

using namespace std;

  
// Узел связанного списка

struct ListNode

{

    int data;

    ListNode* next;

};

  
// Двоичная структура дерева

struct BinaryTreeNode

{

    int data;

    BinaryTreeNode *left, *right;

};

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

void push(struct ListNode** head_ref, int new_data)

{

    // выделить узел и назначить данные

    struct ListNode* new_node = new ListNode;

    new_node->data = new_data;

  

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

    new_node->next = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

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

BinaryTreeNode* newBinaryTreeNode(int data)

{

    BinaryTreeNode *temp = new BinaryTreeNode;

    temp->data = data;

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

    return temp;

}

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

void convertList2Binary(ListNode *head, BinaryTreeNode* &root)

{

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

    queue<BinaryTreeNode *> q;

  

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

    if (head == NULL)

    {

        root = NULL; // Обратите внимание, что корень передается по ссылке

        return;

    }

  

    // 1.) Первый узел всегда является корневым узлом, и добавляем его в очередь

    root = newBinaryTreeNode(head->data);

    q.push(root);

  

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

    head = head->next;

  

    // пока не будет достигнут конец связанного списка, выполните следующие шаги

    while (head)

    {

        // 2.a) взять родительский узел из q и удалить его из q

        BinaryTreeNode* parent = q.front();

        q.pop();

  

        // 2.c) взять следующие два узла из связанного списка. Мы добавим

        // они как дочерние элементы текущего родительского узла на шаге 2.b. Толкать их

        // в очередь, чтобы они были родителями для будущих узлов

        BinaryTreeNode *leftChild = NULL, *rightChild = NULL;

        leftChild = newBinaryTreeNode(head->data);

        q.push(leftChild);

        head = head->next;

        if (head)

        {

            rightChild = newBinaryTreeNode(head->data);

            q.push(rightChild);

            head = head->next;

        }

  

        // 2.b) назначаем левого и правого потомков родителя

        parent->left = leftChild;

        parent->right = rightChild;

    }

}

  
// Утилита для обхода двоичного дерева после преобразования

void inorderTraversal(BinaryTreeNode* root)

{

    if (root)

    {

        inorderTraversal( root->left );

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

        inorderTraversal( root->right );

    }

}

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

int main()

{

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

    struct ListNode* head = NULL;

    push(&head, 36);  / * Последний узел связанного списка * /

    push(&head, 30);

    push(&head, 25);

    push(&head, 15);

    push(&head, 12);

    push(&head, 10); / * Первый узел связанного списка * /

  

    BinaryTreeNode *root;

    convertList2Binary(head, root);

  

    cout << "Inorder Traversal of the constructed Binary Tree is: \n";

    inorderTraversal(root);

    return 0;

}

Джава

// Java-программа для создания полного двоичного дерева из его связанного списка
// представление

   
// импортируем необходимые классы

import java.util.*;

   
// Узел связанного списка

class ListNode 

{

    int data;

    ListNode next;

    ListNode(int d)

    {

        data = d;

        next = null;

    }

}

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

class BinaryTreeNode 

{

    int data;

    BinaryTreeNode left, right = null;

    BinaryTreeNode(int data)

    {

        this.data = data;

        left = right = null;

    }

}

   

class BinaryTree 

{

    ListNode head;

    BinaryTreeNode root;

   

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

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

    void push(int new_data) 

    {

        // выделить узел и назначить данные

        ListNode new_node = new ListNode(new_data);

   

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

        new_node.next = head;

   

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

        head = new_node;

    }

   

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

    // завершаем двоичное дерево в связанный

    // представление двоичного дерева.

    BinaryTreeNode convertList2Binary(BinaryTreeNode node) 

    {

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

        Queue<BinaryTreeNode> q = 

                       new LinkedList<BinaryTreeNode>();

   

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

        if (head == null

        {

            node = null

            return null;

        }

   

        // 1.) Первый узел всегда является корневым узлом, и

        // добавляем его в очередь

        node = new BinaryTreeNode(head.data);

        q.add(node);

   

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

        head = head.next;

   

        // пока не будет достигнут конец связанного списка, выполните

        // следующие шаги

        while (head != null

        {

            // 2.a) взять родительский узел из q и

            // удаляем его из q

            BinaryTreeNode parent = q.peek();

            BinaryTreeNode pp = q.poll();

               

            // 2.c) взять следующие два узла из связанного списка.

            // Мы добавим их как детей текущего

            // родительский узел на шаге 2.b. Подтолкнуть их в

            // очередь, чтобы они были родителями

            // будущие узлы

            BinaryTreeNode leftChild = null, rightChild = null;

            leftChild = new BinaryTreeNode(head.data);

            q.add(leftChild);

            head = head.next;

            if (head != null

            {

                rightChild = new BinaryTreeNode(head.data);

                q.add(rightChild);

                head = head.next;

            }

   

            // 2.b) назначаем левого и правого потомка

            // родитель

            parent.left = leftChild;

            parent.right = rightChild;

        }

           

        return node;

    }

   

    // Утилита для обхода двоичного дерева

    // после конвертации

    void inorderTraversal(BinaryTreeNode node) 

    {

        if (node != null

        {

            inorderTraversal(node.left);

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

            inorderTraversal(node.right);

        }

    }

   

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.push(36); / * Последний узел связанного списка * /

        tree.push(30);

        tree.push(25);

        tree.push(15);

        tree.push(12);

        tree.push(10); / * Первый узел связанного списка * /

        BinaryTreeNode node = tree.convertList2Binary(tree.root);

   

        System.out.println("Inorder Traversal of the"+

                        " constructed Binary Tree is:");

        tree.inorderTraversal(node);

    }

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

питон

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

  
# Узел связанного списка

class ListNode:

  

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

        def __init__(self, data):

            self.data = data

            self.next = None

  
# Двоичная структура дерева

class BinaryTreeNode:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Класс для преобразования связанного списка в двоичное дерево

class Conversion:

  

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

    # и root для двоичного дерева

    def __init__(self, data = None):

        self.head = None

        self.root = None

  

    def push(self, new_data):

  

        # Создание нового узла связанного списка и сохранение данных

        new_node = ListNode(new_data)

  

        # Сделать следующий из нового узла в качестве головы

        new_node.next = self.head

  

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

        self.head = new_node

  

    def convertList2Binary(self):

  

        # Очередь для хранения родительских узлов

        q = []

  

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

        if self.head is None:

            self.root = None

            return 

  

        # 1.) Первый узел всегда является корневым узлом,

        # и добавить его в очередь

        self.root = BinaryTreeNode(self.head.data)

        q.append(self.root)

  

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

        self.head = self.head.next

  

        # До достижения конца связанного списка выполните:

        while(self.head):

  

            # 2.a) Возьмите родительский узел из q и

            # и удалите его из q

            parent = q.pop(0) # Фронт очереди

  

            # 2.c) Возьмите следующие два узла из связанного списка.

            # Мы добавим их как детей текущего

            # родительский узел на шаге 2.b.

            # Вставьте их в очередь, чтобы они были

            # родитель для будущего узла

            leftChild= None

            rightChild = None

  

            leftChild = BinaryTreeNode(self.head.data)

            q.append(leftChild)

            self.head = self.head.next

            if(self.head):

                rightChild = BinaryTreeNode(self.head.data)

                q.append(rightChild)

                self.head = self.head.next

  

            # 2.b) Назначьте левых и правых детей родителей

            parent.left = leftChild

            parent.right = rightChild

  

    def inorderTraversal(self, root):

        if(root):

            self.inorderTraversal(root.left)

            print root.data,

            self.inorderTraversal(root.right)

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

  
# Объект класса преобразования

conv = Conversion()

conv.push(36)

conv.push(30)

conv.push(25)

conv.push(15)

conv.push(12)

conv.push(10)

  
conv.convertList2Binary()

  

print "Inorder Traversal of the contructed Binary Tree is:"

conv.inorderTraversal(conv.root)

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

C #

// C # программа для создания завершена
// Двоичное дерево из связанного списка
// представление

  
// импортируем необходимые классы

using System;

using System.Collections.Generic; 

  
// Узел связанного списка

public class ListNode 

{

    public int data;

    public ListNode next;

    public ListNode(int d)

    {

        data = d;

        next = null;

    }

}

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

public class BinaryTreeNode 

{

    public int data;

    public BinaryTreeNode left, right = null;

    public BinaryTreeNode(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  

public class BinaryTree 

{

    ListNode head;

    BinaryTreeNode root;

  

    // Функция для вставки узла в

    // начало связанного списка

    void push(int new_data) 

    {

        // выделить узел и назначить данные

        ListNode new_node = new ListNode(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    // завершаем двоичное дерево в связанный

    // представление двоичного дерева.

    BinaryTreeNode convertList2Binary(BinaryTreeNode node) 

    {

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

        Queue<BinaryTreeNode> q = 

                    new Queue<BinaryTreeNode>();

  

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

        if (head == null

        {

            node = null

            return null;

        }

  

        // 1.) Первый узел всегда является корневым узлом, и

        // добавляем его в очередь

        node = new BinaryTreeNode(head.data);

        q.Enqueue(node);

  

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

        head = head.next;

  

        // пока не будет достигнут конец связанного списка,

        // делаем следующие шаги

        while (head != null

        {

            // 2.a) взять родительский узел из q и

            // удаляем его из q

            BinaryTreeNode parent = q.Peek();

            BinaryTreeNode pp = q.Dequeue();

              

            // 2.c) взять следующие два узла из связанного списка.

            // Мы добавим их как детей текущего

            // родительский узел на шаге 2.b. Подтолкнуть их в

            // очередь, чтобы они были родителями

            // будущие узлы

            BinaryTreeNode leftChild = null, rightChild = null;

              

            leftChild = new BinaryTreeNode(head.data);

            q.Enqueue(leftChild);

            head = head.next;

              

            if (head != null

            {

                rightChild = new BinaryTreeNode(head.data);

                q.Enqueue(rightChild);

                head = head.next;

            }

  

            // 2.b) назначаем левого и правого потомка

            // родитель

            parent.left = leftChild;

            parent.right = rightChild;

        }

          

        return node;

    }

  

    // Утилита для обхода двоичного дерева

    // после конвертации

    void inorderTraversal(BinaryTreeNode node) 

    {

        if (node != null

        {

            inorderTraversal(node.left);

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

            inorderTraversal(node.right);

        }

    }

  

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

    public static void Main() 

    {

        BinaryTree tree = new BinaryTree();

          

        / * Последний узел связанного списка * /

        tree.push(36); 

        tree.push(30);

        tree.push(25);

        tree.push(15);

        tree.push(12);

          

        / * Первый узел связанного списка * /

        tree.push(10); 

        BinaryTreeNode node = tree.convertList2Binary(tree.root);

  

        Console.WriteLine("Inorder Traversal of the"+

                        " constructed Binary Tree is:");

        tree.inorderTraversal(node);

    }

}

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


Выход:

Inorder Traversal of the constructed Binary Tree is:
25 12 30 10 36 15

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

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

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

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

0.00 (0%) 0 votes