Рубрики

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

Полное двоичное дерево — это двоичное дерево, где каждый уровень 'l', кроме последнего, имеет 2 ^ 1 узлов, а все узлы на последнем уровне выровнены по левому краю. Полные двоичные деревья в основном используются в структурах данных на основе кучи.
Узлы в полном двоичном дереве вставляются слева направо по одному уровню за раз. Если уровень заполнен, узел вставляется на новый уровень.

Ниже приведены некоторые полные двоичные деревья.

       1
      / \
     2   3

        1
       / \
      2   3
     / \  / 
    4  5 6

Ниже двоичные деревья не завершены:

     1
    / \
   2   3
  /    /
  4   5

       1
      / \
     2   3
    / \  /
   4  5 6
  /
 7

Полные двоичные деревья обычно представлены с использованием массивов. Представление массива лучше, потому что оно не содержит пустого слота. При заданном родительском индексе i его левый дочерний элемент задан как 2 * i + 1, а его правый дочерний элемент задан как 2 * i + 2. Таким образом, не теряется дополнительное место и сохраняется пространство для хранения левого и правого указателей. Тем не менее, это может быть интересным вопросом программирования для создания полного двоичного дерева с использованием связанного представления. Здесь связанные означают представление не в виде массива, где левый и правый указатели (или ссылки) используются для ссылки на левого и правого потомков соответственно. Как написать функцию вставки, которая всегда добавляет новый узел на последнем уровне и в самой левой доступной позиции?
Чтобы создать связанное полное двоичное дерево, нам нужно отслеживать узлы в порядке уровней, чтобы следующий узел, который нужно вставить, находился в крайнем левом положении. Структура данных очереди может использоваться для отслеживания вставленных узлов.

Ниже приведены шаги для вставки нового узла в полное двоичное дерево.
1. Если дерево пустое, инициализируйте корень новым узлом.

2. Иначе, получить передний узел очереди.
…… Если левый потомок этого переднего узла не существует, установите левый потомок в качестве нового узла.
……. Иначе, если правый потомок этого переднего узла не существует, установите правый потомок в качестве нового узла.

3. Если у переднего узла есть и левый, и правый дочерние узлы, удалите его ().

4. Поставьте в очередь () новый узел.

Ниже приведена реализация:

C ++

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

using namespace std;

  
// для размера очереди
#define SIZE 50 

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

class node 

    public:

    int data; 

    node *right,*left; 

}; 

  
// Узел очереди

class Queue 

    public:

    int front, rear; 

    int size; 

    node**array; 

}; 

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

node* newNode(int data) 

    node* temp = new node();

    temp->data = data; 

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

    return temp; 

  
// Утилита для создания новой очереди

Queue* createQueue(int size) 

    Queue* queue = new Queue(); 

  

    queue->front = queue->rear = -1; 

    queue->size = size; 

  

    queue->array = new node*[queue->size * sizeof( node* )]; 

  

    int i; 

    for (i = 0; i < size; ++i) 

        queue->array[i] = NULL; 

  

    return queue; 

  
// Стандартные функции очереди

int isEmpty(Queue* queue) 

    return queue->front == -1; 

  

int isFull(Queue* queue) 

{ return queue->rear == queue->size - 1; } 

  

int hasOnlyOneItem(Queue* queue) 

{ return queue->front == queue->rear; } 

  

void Enqueue(node *root, Queue* queue) 

    if (isFull(queue)) 

        return

  

    queue->array[++queue->rear] = root; 

  

    if (isEmpty(queue)) 

        ++queue->front; 

  
node* Dequeue(Queue* queue) 

    if (isEmpty(queue)) 

        return NULL; 

  

    node* temp = queue->array[queue->front]; 

  

    if (hasOnlyOneItem(queue)) 

        queue->front = queue->rear = -1; 

    else

        ++queue->front; 

  

    return temp; 

  
node* getFront(Queue* queue) 

{ return queue->array[queue->front]; } 

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

int hasBothChild(node* temp) 

    return temp && temp->left && temp->right; 

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

void insert(node **root, int data, Queue* queue) 

    // Создать новый узел для данных

    node *temp = newNode(data); 

  

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

    if (!*root) 

        *root = temp; 

  

    else

    

        // получаем передний узел очереди.

        node* front = getFront(queue); 

  

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

        // оставил дочерний как новый узел

        if (!front->left) 

            front->left = temp; 

  

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

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

        else if (!front->right) 

            front->right = temp; 

  

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

        // Dequeue () это.

        if (hasBothChild(front)) 

            Dequeue(queue); 

    

  

    // Enqueue () новый узел для последующих вставок

    Enqueue(temp, queue); 

  
// Обход ордера стандартного уровня для проверки вышеуказанной функции

void levelOrder(node* root) 

    Queue* queue = createQueue(SIZE); 

  

    Enqueue(root, queue); 

  

    while (!isEmpty(queue)) 

    

        node* temp = Dequeue(queue); 

  

        cout<<temp->data<<" "

  

        if (temp->left) 

            Enqueue(temp->left, queue); 

  

        if (temp->right) 

            Enqueue(temp->right, queue); 

    

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

int main() 

    node* root = NULL; 

    Queue* queue = createQueue(SIZE); 

    int i; 

  

    for(i = 1; i <= 12; ++i) 

        insert(&root, i, queue); 

  

    levelOrder(root); 

  

    return 0; 

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

С

// Программа для связанной реализации полного бинарного дерева
#include <stdio.h>
#include <stdlib.h>

  
// для размера очереди
#define SIZE 50

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

struct node

{

    int data;

    struct node *right,*left;

};

  
// Узел очереди

struct Queue

{

    int front, rear;

    int size;

    struct node* *array;

};

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

struct node* newNode(int data)

{

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

    temp->data = data;

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

    return temp;

}

  
// Утилита для создания новой очереди

struct Queue* createQueue(int size)

{

    struct Queue* queue = (struct Queue*) malloc(sizeof( struct Queue ));

  

    queue->front = queue->rear = -1;

    queue->size = size;

  

    queue->array = (struct node**) malloc

                   (queue->size * sizeof( struct node* ));

  

    int i;

    for (i = 0; i < size; ++i)

        queue->array[i] = NULL;

  

    return queue;

}

  
// Стандартные функции очереди

int isEmpty(struct Queue* queue)

{

    return queue->front == -1;

}

  

int isFull(struct Queue* queue)

return queue->rear == queue->size - 1; }

  

int hasOnlyOneItem(struct Queue* queue)

return queue->front == queue->rear;  }

  

void Enqueue(struct node *root, struct Queue* queue)

{

    if (isFull(queue))

        return;

  

    queue->array[++queue->rear] = root;

  

    if (isEmpty(queue))

        ++queue->front;

}

  

struct node* Dequeue(struct Queue* queue)

{

    if (isEmpty(queue))

        return NULL;

  

    struct node* temp = queue->array[queue->front];

  

    if (hasOnlyOneItem(queue))

        queue->front = queue->rear = -1;

    else

        ++queue->front;

  

    return temp;

}

  

struct node* getFront(struct Queue* queue)

return queue->array[queue->front]; }

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

int hasBothChild(struct node* temp)

{

    return temp && temp->left && temp->right;

}

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

void insert(struct node **root, int data, struct Queue* queue)

{

    // Создать новый узел для данных

    struct node *temp = newNode(data);

  

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

    if (!*root)

        *root = temp;

  

    else

    {

        // получаем передний узел очереди.

        struct node* front = getFront(queue);

  

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

        // оставил дочерний как новый узел

        if (!front->left)

            front->left = temp;

  

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

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

        else if (!front->right)

            front->right = temp;

  

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

        // Dequeue () это.

        if (hasBothChild(front))

            Dequeue(queue);

    }

  

    // Enqueue () новый узел для последующих вставок

    Enqueue(temp, queue);

}

  
// Обход ордера стандартного уровня для проверки вышеуказанной функции

void levelOrder(struct node* root)

{

    struct Queue* queue = createQueue(SIZE);

  

    Enqueue(root, queue);

  

    while (!isEmpty(queue))

    {

        struct node* temp = Dequeue(queue);

  

        printf("%d ", temp->data);

  

        if (temp->left)

            Enqueue(temp->left, queue);

  

        if (temp->right)

            Enqueue(temp->right, queue);

    }

}

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

int main()

{

    struct node* root = NULL;

    struct Queue* queue = createQueue(SIZE);

    int i;

  

    for(i = 1; i <= 12; ++i)

        insert(&root, i, queue);

  

    levelOrder(root);

  

    return 0;

}

Выход:

1 2 3 4 5 6 7 8 9 10 11 12

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

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

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

0.00 (0%) 0 votes