Data communication networks adopt a very interesting strategy to transmit a flow of information from one point to another. Due to possible losses that occur during transmission, this information is fragmented into data packets, so that each packet carries part of the information and also an identification number. As the order of arrival of the packets at the destination may not be the same as the departure from the source, this identification allows the fragments to be reorganized in the correct sequence when they arrive at their destination and, with that, the flow of information is duly reconstructed. During transmission, some of these packets may be lost and, as it is not possible to predict which will be lost, each packet is sent several times so that any losses are repaired. On the other hand, if the loss does not occur, the same packet will arrive several times at the destination. Thus, when the information flow is reconstructed, it is necessary to discard duplicate packets.

The implementation of this strategy uses a **binary search tree** located at the destination as a basic data structure. Thus, as packets arrive at their destination, they are **inserted** into a binary search tree, considering the packet identification number as key. This same insertion operation will ensure that duplicate packets cannot be inserted into the tree. Once all the packages are inserted in the tree, to reconstruct the information flow, it is enough to **remove** the packages from the tree in ascending order according to their keys.

Implement a program in C that simulates this data transmission strategy. General instructions are as follows:

1 - ask the user to enter a message to be transmitted over the network;

2 - print the message;

3 - fragment the message so that each character represent a packet to be transmitted, remembering that every package must be associated with an identification number;

4 - for each packet, generate a random integer number between 1 and 10, which will determine the number of times the packet must be replicated;

5 - generate a new sequence of packets in which both the packets of the original message and the replicated packets are scrambled;

6 - print the new packet sequence;

7 - build the binary search tree from the new sequence of packages;

8 - print the tree;

9 - reconstruct the original message from the binary search tree.

10 - print the message;

11 - Make sure to modify the following code to do it:

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
#include "TAD_arvore_binaria_busca.h"

int main(void)
{
    setlocale(LC_ALL, “”);
    srand(time(NULL));

    printf(“\nInsira uma mensagem para ser enviada: “);
    char mensagem[100];
    fgets(mensagem, sizeof(mensagem), stdin);

    printf(”\nMensagem a ser enviada: %s”, mensagem);

    int tamanho = 0;
    for (tamanho = 0; mensagem[tamanho] != ‘\0’ && mensagem[tamanho] != ‘\n’; tamanho++);

    printf(“\nFragmentacao da mensagem:\n   [id]”);
    int i;
    for (i = 0; i < tamanho; i++)
        printf(" %3d", i);
    printf(“\n[dado]”);
    for (i = 0; i < tamanho; i++)
        printf(" %3c", mensagem[i]);

    TipoItem Itensmisto[tamanho * 10];
    int Itensmistocontagem = 0;

    for (i = 0; i < tamanho; i++)
    {
        int replicas = rand() % 10 + 1;
        int j;
        for (j = 0; j < replicas; j++)
        {
            TipoItem novoItem;
            novoItem.chave = i;
            novoItem.pacote = mensagem[i];
            Itensmisto[Itensmistocontagem++] = novoItem;
        }
    }

    for (i = Itensmistocontagem - 1; i > 0; i–)
    {
        int j = rand() % (i + 1);
        TipoItem temp = Itensmisto[i];
        Itensmisto[i] = Itensmisto[j];
        Itensmisto[j] = temp;
    }

    printf(“\n\nOrdem de chegada dos pacotes no destino:\n[id]   “);
    for (i = 0; i < Itensmistocontagem; i++)
        printf(” %3d”, Itensmisto[i].chave);
    printf(“\n[dado]”);
    for (i = 0; i < Itensmistocontagem; i++)
        printf(" %3c", Itensmisto[i].pacote);

    TipoCelula **arvore = (TipoCelula **)malloc(sizeof(TipoCelula *));
    CriaArvoreBinariaBuscaVazia(arvore);

    for (i = 0; i < Itensmistocontagem; i++)
        InsereArvoreBinariaBusca(arvore, Itensmisto[i]);

    printf(“\n\nA arvore depois da insercao:\n”);
    ImprimeArvoreBinariaBusca(arvore, 0);

    printf(“\nMensagem reconstruida: “);
    for (i = 0; i < tamanho; i++)
    {
        TipoItem *item = BuscaArvoreBinariaBusca(arvore, i);
        if (item != NULL)
            printf(”%c”, item->pacote);
    }

    printf(“\n”);

    return 0;
}


12 - And make sure to use the following ADTs:

#include <stdio.h>
#include <stdlib.h>
#include "ADT_binary_search_tree.h"

void Antecessor1(TipoCelula **arvore1, TipoCelula *arvore2);

//creates an empty binary search tree
void CriaArvoreBinariaBuscaVazia(TipoCelula **arvore)
{
    *arvore = NULL;
}

//tests whether the binary search tree is empty
int TestaArvoreBinariaBuscaVazia(TipoCelula **arvore)
{
    return (*arvore == NULL);
}

TipoItem * BuscaArvoreBinariaBusca(TipoCelula **arvore, int chave)
{
    if (TestaArvoreBinariaBuscaVazia(arvore))
        printf("Erro: item inexistente\n");
    else if (chave < (*arvore)->item.chave)
        BuscaArvoreBinariaBusca(&(*arvore)->esquerda, chave);
    else if (chave > (*arvore)->item.chave)
        BuscaArvoreBinariaBusca(&(*arvore)->direita, chave);
    else
        return &(*arvore)->item;
}

//inserts an element of type TipoItem into the binary search tree
void InsereArvoreBinariaBusca(TipoCelula **arvore, TipoItem item)
{
    if (TestaArvoreBinariaBuscaVazia(arvore))
    {
        (*arvore) = (TipoCelula *)malloc(sizeof(TipoCelula));
        (*arvore)->item = item;
        (*arvore)->esquerda = (*arvore)->direita = NULL;
    }
    else if (item.chave < (*arvore)->item.chave)
        InsereArvoreBinariaBusca(&(*arvore)->esquerda, item);
    else if (item.chave > (*arvore)->item.chave)
        InsereArvoreBinariaBusca(&(*arvore)->direita, item);
    else
        printf("Erro: item existente\n");
}

//removes an element of type TipoItem from the binary search tree
void RemoveArvoreBinariaBusca(TipoCelula **arvore, TipoItem item)
{
    TipoCelula *aux;

    if (TestaArvoreBinariaBuscaVazia(arvore))
        printf("Erro: item inexistente\n");
    else if (item.chave < (*arvore)->item.chave)
        RemoveArvoreBinariaBusca(&(*arvore)->esquerda, item);
    else if (item.chave > (*arvore)->item.chave)
        RemoveArvoreBinariaBusca(&(*arvore)->direita, item);
    else if (TestaArvoreBinariaBuscaVazia(&(*arvore)->direita))
    {
        aux = *arvore;
        *arvore = (*arvore)->esquerda;
        free(aux);
    }
    else if (!TestaArvoreBinariaBuscaVazia(&(*arvore)->esquerda))
        Antecessor1(&(*arvore)->esquerda, *arvore);
    else
    {
        aux = *arvore;
        *arvore = (*arvore)->direita;
        free(aux);
    }
}

void Antecessor1(TipoCelula **arvore1, TipoCelula *arvore2)
{
    if (!TestaArvoreBinariaBuscaVazia(&(*arvore1)->direita))
        Antecessor1(&(*arvore1)->direita, arvore2);
    else
    {
        arvore2->item = (*arvore1)->item;
        arvore2 = *arvore1 ;
        *arvore1 = (*arvore1)->esquerda;
        free(arvore2);
    }
}

//prints the elements of the binary search tree
void ImprimeArvoreBinariaBusca(TipoCelula **arvore, int l)
{
    int i;

    if(!TestaArvoreBinariaBuscaVazia(arvore))
    {
        ImprimeArvoreBinariaBusca(&(*arvore)->esquerda, l + 1);
        for (i = 0; i < l; i++)
            printf("   ");
        printf("%i %c\n", (*arvore)->item.chave, (*arvore)->item.pacote);
        ImprimeArvoreBinariaBusca(&(*arvore)->direita, l + 1);
    }
}