Árbol binario completo enlazado y su creación.

Posted on by Rudeus Greyrat

Un árbol binario completo es un árbol binario donde cada nivel ‘l’ excepto el último tiene 2^l Nodes y los Nodes en el último nivel están todos alineados a la izquierda. Los árboles binarios completos se utilizan principalmente en estructuras de datos basadas en montón. 
Los Nodes en el árbol binario completo se insertan de izquierda a derecha en un nivel a la vez. Si un nivel está lleno, el Node se inserta en un nuevo nivel.
A continuación se muestran algunos árboles binarios completos. 

       1
      / \
     2   3

        1
       / \
      2   3
     / \  / 
    4  5 6

Los siguientes árboles binarios no están completos:  

     1
    / \
   2   3
  /    /
  4   5

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

Los árboles binarios completos generalmente se representan mediante arrays. La representación de la array es mejor porque no contiene ranuras vacías. Dado el índice principal i, su hijo izquierdo está dado por 2 * i + 1, y su hijo derecho está dado por 2 * i + 2. Por lo tanto, no se desperdicia espacio adicional y se ahorra espacio para almacenar punteros izquierdo y derecho. Sin embargo, puede ser una cuestión de programación interesante crear un árbol binario completo utilizando una representación vinculada. Aquí Vinculado significa una representación sin array donde los punteros izquierdo y derecho (o referencias) se utilizan para referirse a los niños izquierdo y derecho respectivamente. ¿Cómo escribir una función de inserción que siempre agregue un nuevo Node en el último nivel y en la posición disponible más a la izquierda? 
Para crear un árbol binario completo vinculado, debemos realizar un seguimiento de los Nodes en orden de nivel, de modo que el siguiente Node que se inserte se encuentre en la posición más a la izquierda. Se puede utilizar una estructura de datos de cola para realizar un seguimiento de los Nodes insertados. 

Los siguientes son los pasos para insertar un nuevo Node en el árbol binario completo. 

  1. Si el árbol está vacío, inicialice la raíz con un nuevo Node.
  2. De lo contrario, obtenga el Node frontal de la cola. 
    1. …….Si el hijo izquierdo de este Node frontal no existe, configure el hijo izquierdo como el nuevo Node. 
    2. …….de lo contrario, si el hijo derecho de este Node frontal no existe, configure el hijo derecho como el nuevo Node.
  3. Si el Node frontal tiene tanto el hijo izquierdo como el hijo derecho, Dequeue() lo.
  4. Enqueue() el nuevo Node.

A continuación se muestra la implementación: 

C++

// Program for linked implementation of complete binary tree
#include <bits/stdc++.h>
using namespace std;
 
// For Queue Size
#define SIZE 50
 
// A tree node
class node
{
    public:
    int data;
    node *right,*left;
};
 
// A queue node
class Queue
{
    public:
    int front, rear;
    int size;
    node**array;
};
 
// A utility function to create a new tree node
node* newNode(int data)
{
    node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to create a new Queue
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;
}
 
// Standard Queue Functions
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]; }
 
// A utility function to check if a tree node
// has both left and right children
int hasBothChild(node* temp)
{
    return temp && temp->left && temp->right;
}
 
// Function to insert a new node in complete binary tree
void insert(node **root, int data, Queue* queue)
{
    // Create a new node for given data
    node *temp = newNode(data);
 
    // If the tree is empty, initialize the root with new node.
    if (!*root)
        *root = temp;
 
    else
    {
        // get the front node of the queue.
        node* front = getFront(queue);
 
        // If the left child of this front node doesn’t exist, set the
        // left child as the new node
        if (!front->left)
            front->left = temp;
 
        // If the right child of this front node doesn’t exist, set the
        // right child as the new node
        else if (!front->right)
            front->right = temp;
 
        // If the front node has both the left child and right child,
        // Dequeue() it.
        if (hasBothChild(front))
            Dequeue(queue);
    }
 
    // Enqueue() the new node for later insertions
    Enqueue(temp, queue);
}
 
// Standard level order traversal to test above function
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);
    }
}
 
// Driver program to test above functions
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;
}
 
//This code is contributed by rathbhupendra

C

// Program for linked implementation of complete binary tree
#include <stdio.h>
#include <stdlib.h>
 
// For Queue Size
#define SIZE 50
 
// A tree node
struct node
{
    int data;
    struct node *right,*left;
};
 
// A queue node
struct Queue
{
    int front, rear;
    int size;
    struct node* *array;
};
 
// A utility function to create a new tree node
struct node* newNode(int data)
{
    struct node* temp = (struct node*) malloc(sizeof( struct node ));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to create a new Queue
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;
}
 
// Standard Queue Functions
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]; }
 
// A utility function to check if a tree node
// has both left and right children
int hasBothChild(struct node* temp)
{
    return temp && temp->left && temp->right;
}
 
// Function to insert a new node in complete binary tree
void insert(struct node **root, int data, struct Queue* queue)
{
    // Create a new node for given data
    struct node *temp = newNode(data);
 
    // If the tree is empty, initialize the root with new node.
    if (!*root)
        *root = temp;
 
    else
    {
        // get the front node of the queue.
        struct node* front = getFront(queue);
 
        // If the left child of this front node doesn’t exist, set the
        // left child as the new node
        if (!front->left)
            front->left = temp;
 
        // If the right child of this front node doesn’t exist, set the
        // right child as the new node
        else if (!front->right)
            front->right = temp;
 
        // If the front node has both the left child and right child,
        // Dequeue() it.
        if (hasBothChild(front))
            Dequeue(queue);
    }
 
    // Enqueue() the new node for later insertions
    Enqueue(temp, queue);
}
 
// Standard level order traversal to test above function
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);
    }
}
 
// Driver program to test above functions
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;
}

Python3

# Program for linked implementation
# of complete binary tree
 
# For Queue Size
SIZE = 50
 
# A tree node
class node:
     
    def __init__(self, data):
       
        self.data = data
        self.right = None
        self.left = None
 
# A queue node
class Queue:
     
    def __init__(self):
       
        self.front = None
        self.rear = None
        self.size = 0
        self.array = []
 
# A utility function to
# create a new tree node
def newNode(data):
     
    temp = node(data)
    return temp
 
# A utility function to
# create a new Queue
def createQueue(size):
     
    global queue   
    queue = Queue();
    queue.front = queue.rear = -1;
    queue.size = size;
    queue.array = [None for i in range(size)]
    return queue;
     
# Standard Queue Functions
def isEmpty(queue):
 
    return queue.front == -1
 
def isFull(queue):
     
    return queue.rear == queue.size - 1;
 
def hasOnlyOneItem(queue):
     
    return queue.front == queue.rear;
 
def Enqueue(root):
 
    if (isFull(queue)):
        return;
     
    queue.rear+=1
    queue.array[queue.rear] = root;
 
    if (isEmpty(queue)):
        queue.front+=1;
 
def Dequeue():
 
    if (isEmpty(queue)):
        return None;
 
    temp = queue.array[queue.front];
 
    if(hasOnlyOneItem(queue)):
        queue.front = queue.rear = -1;
    else:
        queue.front+=1
 
    return temp;
 
def getFront(queue):
     
    return queue.array[queue.front];
 
# A utility function to check
# if a tree node has both left
# and right children
def hasBothChild(temp):
 
    return (temp and temp.left and
            temp.right);
     
# Function to insert a new
# node in complete binary tree
def insert(root, data, queue):
 
    # Create a new node for
    # given data
    temp = newNode(data);
 
    # If the tree is empty,
    # initialize the root
    # with new node.
    if not root:
        root = temp;
    else:
     
        # get the front node of
        # the queue.
        front = getFront(queue);
 
        # If the left child of this
        # front node doesn’t exist,
        # set the left child as the
        # new node
        if (not front.left):
            front.left = temp;
 
        # If the right child of this
        # front node doesn’t exist, set
        # the right child as the new node
        elif (not front.right):
            front.right = temp;
 
        # If the front node has both the
        # left child and right child,
        # Dequeue() it.
        if (hasBothChild(front)):
            Dequeue();
 
    # Enqueue() the new node for
    # later insertions
    Enqueue(temp);
    return root
  
# Standard level order
# traversal to test above
# function
def levelOrder(root):
 
    queue = createQueue(SIZE);
    Enqueue(root);
     
    while (not isEmpty(queue)):   
        temp = Dequeue();        
        print(temp.data, end = ' ')
        if (temp.left):
            Enqueue(temp.left);
        if (temp.right):
            Enqueue(temp.right);
 
# Driver code 
if __name__ == "__main__":
     
    root = None
    queue = createQueue(SIZE);
     
    for i in range(1, 13):
        root=insert(root, i,
                    queue);
      
    levelOrder(root);
 
# This code is contributed by Rutvik_56
Producción: 

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

 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *