Calculando-Altura-e-Numero-de-Nos-em-Arvore-Binaria

Q3 BinTree Calculando a altura e o número de nós de uma árvore binária Descrição Durante as aulas estudamos a estrutura de dados árvore binária generalizada uma árvore em que as chaves dos nós não tem nenhuma relação de ordem entre si e vimos a implementação das funções mais básicas que podem ser realizadas nesta estrutura de dados As árvores binárias podem ser representadas como uma string por meio da serialização dos valores de suas chaves A serialização é um processo pelo qual percorremos a árvore em préordem e adicionamos o valor de cada chave encontrada ao final de uma string que inicialmente começa vazia sendo que para cada filho nulo encontrado seu valor é representado pelo caractere Por exemplo logo abaixo mostramos o desenho de uma árvore e depois a string obtida pela serialização de suas chaves A serialização da árvore acima consiste na string 8 3 1 6 4 7 10 14 13 Para entender melhor o conceito de serialização de uma árvore binária e ver outros exemplos de árvores e sua serialização você pode acessar esse link httpswwwgeeksforgeeksorgserializedeserializebinarytree Nesta atividade a árvore é construída através de uma string de serialização Isso já está codificado Você não precisa implementar Atividade Para esta atividade é pedido que você incremente a implementação desta estrutura implementando as seguintes funções adicionais 1 Escreva uma função que calcule a altura uma árvore binária A sua função deve ser recursiva e deve ter o seguinte protótipo int heightNode node 2 Escreva uma função que calcule o número de nós de uma árvore binária A sua função deve ser recursiva e deve ter o seguinte protótipo int sizeNode node Observação Suas funções privadas devem ser recursivas e não é permitido usar variáveis globais nestas atividades Exercícios resolvidos com variáveis globais receberão nota ZERO Ajuda A atividade já vem com um código implementado para você seguir como ponto de partida O método bshow da árvore imprime a árvore em um formato amigável Você pode utilizálo para conferir se seu código está funcionando corretamente Para o caso da árvore abaixo temos essa saída serial 1 8 7 4 6 5 0 9 3 2 bshow Para simplificar o código estou utilizando a convenção para expressar quais são os métodos privados Os locais onde você deve colocar seu código estão marcados com TODO Como estamos lidando com árvores você deverá criar também os métodos recursivos privados e os métodos públicos Testes um 4 1 1 dois 1 0 2 2 tres 4 8 2 3 3 4 quatro 0 9 4 5 3 4 cinco 0 4 2 0 3 3 5 seis 2 0 0 3 7 9 4 6 dez 1 8 7 4 6 5 0 9 3 2 5 10 zero 0 0 MAINCPP include iostream include string include Treeh using namespace std int main string line getlinecin line Tree btline cout btheight btsize endl return 0 TREEH ifndef TREEH define TREEH include string include sstream struct Node class Tree public Treestdstring serial void inorder percurso em ordem simetrica void bshow exibe a arvore de forma amigavel int size int height Tree private Node root Node clearNode root void inorderNode node void bshowNode node stdstring heranca void serializeTreestdstringstream ss Node node int sizeNode node int heightNode node endif Treecpp include iostream include sstream include string include Treeh Definicao do struct Node Em C os structs podem ter funcoesmembro como construtores destrutores etc struct Node int key Node left Node right Nodeint k Node l nullptr Node r nullptr thiskey k thisleft l thisright r Construtor TreeTreestdstring serial root nullptr stdstringstream ssserial serializeTreess root Essa funcao recursiva recebe como entrada uma string contendo uma versao serializada da arvore e recebe um ponteiro para ponteiro para o no raiz A funcao ler os dados e constroi a arvore seguindo um percurso em preordem void TreeserializeTreestdstringstream ss Node node stdstring value ss value ifvalue filho nullptr return int key stdstoivalue node new Nodekey serializeTreess nodeleft serializeTreess noderight Destrutor TreeTree root clearroot Essa funcao recebe uma raiz chamada node e ela libera todos os nos decendentes de node e o proprio node Node TreeclearNode node ifnode nullptr caso geral vamos liberar essa arvore nodeleft clearnodeleft noderight clearnoderight delete node return nullptr void Treeinorder inorderroot stdcout stdendl void TreeinorderNode node ifnode nullptr Caso Geral inordernodeleft stdcout nodekey inordernoderight void Treebshow bshowroot void TreebshowNode node stdstring heranca ifnode nullptr nodeleft nullptr noderight nullptr bshownoderight heranca r forint i 0 i int herancasize 1 i stdcout herancai herancai 1 ifheranca stdcout herancaback r ifnode nullptr stdcout stdendl return stdcout nodekey stdendl ifnode nullptr nodeleft nullptr noderight nullptr bshownodeleft heranca l int Treesize TODO int TreesizeNode node TODO int Treeheight TODO int TreeheightNode node TODO Q2 queue Copa do mundo Motivação Este ano tem Copa do Mundo O país inteiro se prepara para torcer para a equipe canarinho conquistar mais um título tornandose hexacampeã Na Copa do Mundo depois de uma fase de grupos dezesseis equipes disputam a Fase Final composta de quinze jogos eliminatórios A figura abaixo mostra a tabela de jogos da Fase Final Dados os resultados dos quinze jogos da Fase Final escreva um programa que determine a equipe campeã Entrada A entrada é composta de quinze linhas cada uma contendo o resultado de um jogo A primeira linha contém o resultado do jogo de número 1 a segunda linha o resultado do jogo de número 2 e assim por diante O resultado de um jogo é representado por dois números inteiros MM e NN separados por um espaço em branco indicando respectivamente o número de gols da equipe representada à esquerda e à direita na tabela de jogos Saída Seu programa deve imprimir uma única linha contendo a letra identificadora da equipe campeã Entradas de amostra 01 4 1 1 0 0 4 3 1 2 3 1 2 2 0 0 2 1 2 4 3 0 1 3 2 3 4 1 4 1 0 F 02 2 0 1 0 2 1 1 0 1 0 1 2 1 2 1 0 2 1 1 0 0 1 0 2 2 1 1 0 2 1 A Dica Coloque as 16 letras em uma fila Pegue as duas primeiras o que no caso seriam A e B o leia os gols o decida quem você coloca de novo na fila Continue até que só existe um elemento na fila Q1 queue stack Implementando Fila com duas Pilhas Descrição da função Uma fila é um tipo de dados abstrato que mantém a ordem na qual os elementos foram adicionados a ela permitindo que os elementos mais antigos sejam removidos da frente e os novos elementos sejam adicionados na parte traseira Isso é chamado de estrutura de dados FIFO Primeiro a entrar primeiro a sair porque o primeiro elemento adicionado à fila ou seja aquele que está esperando há mais tempo é sempre o primeiro a ser removido Nesse desafio você deve primeiro implementar uma fila usando duas pilhas Em seguida processe a consultas em que cada consulta é um dos seguintes 3 tipos 1 x Enfileirar o elemento x no final da fila 2 Retirar da fila o elemento na frente da fila 3 Mostre o elemento na frente da fila Formato de entrada A primeira linha contém um único número inteiro q denotando o número de consultas Cada linha i das q linhas subsequentes contém uma única consulta no padrão descrito acima no problema Todas as três consultas começam com um número inteiro que indica o tipo da consulta mas apenas a primeira consulta é seguida por um valor adicional x separado por espaço indicando o valor a ser enfileirado Formato de saída Para cada consulta do tipo 3 imprima o valor do elemento na frente da fila em uma nova linha As consultas de tipo 1 e 2 não necessitam imprimir nada Ajuda Você pode utilizar duas pilhas Vamos chamar a primeira pilha de deposito e a segunda de prateleira Se precisar colocar algo você coloca no deposito Se precisar pegar algo você pega da prateleira Se a prateleira estiver vazia você retira tudo do deposito para a prateleira o Observe que agora o depósito foi invertido e a primeira a ser inserida no depósito é a última da prateleira Atenção nessa primeira questão é para de fato implementar a estrutura de dados FILA do zero usando duas Pilhas Por esse motivo é que a questão espera três arquivos Um é o arquivo maincpp outro é o Queuecpp e outro o Queueh Testes 9 1 1 1 2 1 3 3 2 3 2 3 2 1 2 3 01 10 1 42 2 1 14 3 1 28 3 1 60 1 78 2 2 14 14 02 10 1 76 1 33 2 1 23 1 97 1 21 3 3 1 74 3 33 33 33 03 100 1 92118642 2 1 107858633 1 110186788 1 883309178 1 430939631 2 1 739711408 1 803703507 1 643797161 1 538560826 3 1 595864615 1 490282285 1 558095366 1 893666727 1 595679828 3 1 99908215 3 1 333969117 1 604624143 1 88712599 1 224459820 3 1 153072902 3 3 2 1 156974087 2 1 387224973 1 154628865 1 256130200 1 704295204 2 3 1 928499989 2 3 2 1 319507446 1 323714081 1 772087837 1 350417458 1 193303587 1 213700781 3 1 565379092 1 284925173 2 1 794176274 3 1 766929345 3 2 1 42983700 2 1 156768862 1 205008057 1 93223219 3 2 1 17818922 1 917626659 1 829031126 1 346173907 1 78065001 2 3 2 3 1 565004472 1 753139390 2 1 629441479 1 935933973 1 650043630 3 1 158726470 1 206429620 3 1 590439448 1 139555053 1 78707344 1 989497950 1 880166047 2 1 137608768 3 1 861823671 1 625166323 1 431218849 3 1 570007363 2 3 3 2 1 978253366 110186788 110186788 110186788 110186788 110186788 110186788 739711408 803703507 643797161 538560826 538560826 490282285 893666727 595679828 99908215 99908215 333969117 333969117 604624143 604624143 Q4 BinTree Soma das chaves chave mínima e outras operações Atividade Para esta atividade é pedido que você incremente a implementação da árvore binária generalizada implementando as seguintes funções adicionais 1 Escreva uma função que devolva a soma de todas as chaves de uma árvore binária A sua função deve ser recursiva e deve ter o seguinte protótipo int sumkeysNode node 2 Escreva uma função que devolva o valor da menor chave de uma árvore binária A sua função deve ser recursiva e deve ter o seguinte protótipo int minkeyNode node Essa função supõe que o ponteiro passado como parâmetro é sempre dieferente de nullptr 3 Escreva uma função que conte o número de nós internos de uma árvore binária A sua função deve ser recursiva e deve ter o seguinte protótipo int totalinternalnodesNode node 4 Escreva uma função que retorne a quantidade de nós de uma árvore binária que possuem apenas um filho A sua função deve ser recursiva e deve ter o seguinte protótipo int umfilhoNode node Observação Suas funções privadas devem ser recursivas e não é permitido usar variáveis globais nestas atividades Exercícios resolvidos com variáveis globais receberão nota ZERO Ajuda A atividade já vem com um código implementado para você seguir como ponto de partida O método bshow da árvore imprime a árvore em um formato amigável Você pode utilizálo para conferir se seu código está funcionando corretamente Para o caso da árvore abaixo temos essa saída serial 1 8 7 4 6 5 0 9 3 2 bshow Para simplificar o código estou utilizando a convenção para expressar quais são os métodos privados Os locais onde você deve colocar seu código estão marcados com TODO Como estamos lidando com árvores você deverá criar também os métodos recursivos privados e os métodos públicos Testes um 0 4 2 0 3 0 9 2 0 dois 7 5 9 1 4 2 3 1 31 3 0 tres 1 2 3 4 5 6 1 21 3 1 quatro 1 6 2 3 4 3 7 5 1 31 5 3 cinco 1 2 4 3 6 5 7 8 1 36 4 1 seis 1 3 4 2 1 10 9999 20 500 13 9999 10553 6 3 sete 6 7 7 6 0 10 10 10 0 5 4 oito 1 3 4 2 1 4 1 3 2 nove 0 0 0 0 0 0 0 0 0 3 0 Arquivos requeridos maincpp include iostream include string include Treeh using namespace std int main string line getlinecin line Tree btline cout btminkey btsumkeys endl cout bttotalinternalnodes btumfilho endl return 0 Treeh ifndef TREEH define TREEH include string include sstream struct Node class Tree public Treestdstring serial void inorder percurso em ordem simetrica void bshow int sumkeys int minkey int totalinternalnodes int umfilho Tree private Node root void bshowNode node stdstring heranca void serializeTreestdstringstream ss Node node Node clearNode root void inorderNode node int sumkeysNode node int minkeyNode node int totalinternalnodesNode node int umfilhoNode node endif Treecpp include iostream include sstream include string include climits include Treeh struct Node int key Node left Node right Nodeint k Node l nullptr Node r nullptr thiskey k thisleft l thisright r TreeTreestdstring serial root nullptr stdstringstream ssserial serializeTreess root void TreeserializeTreestdstringstream ss Node node stdstring value ss value ifvalue filho nullptr return int key stdstoivalue node new Nodekey serializeTreess nodeleft serializeTreess noderight TreeTree clearroot Node TreeclearNode node ifnode nullptr caso geral vamos liberar essa arvore nodeleft clearnodeleft noderight clearnoderight delete node return nullptr void Treeinorder inorderroot void TreeinorderNode node ifnode nullptr Caso Geral inordernodeleft stdcout nodekey inordernoderight void Treebshow bshowroot void TreebshowNode node stdstring heranca ifnode nullptr nodeleft nullptr noderight nullptr bshownoderight heranca r forint i 0 i int herancasize 1 i stdcout herancai herancai 1 ifheranca stdcout herancaback r ifnode nullptr stdcout stdendl return stdcout nodekey stdendl ifnode nullptr nodeleft nullptr noderight nullptr bshownodeleft heranca l int Treesumkeys TODO int TreesumkeysNode node TODO Para fazer essa funcao suponha que as arvores dos testes nunca serao vazias assim sempre havera um menor valor de chave a ser retornado int Treeminkey TODO Supoe que o ponteiro recebido sempre eh diferente de nullptr int TreeminkeyNode node TODO int Treetotalinternalnodes TODO int TreetotalinternalnodesNode node TODO int Treeumfilho TODO int TreeumfilhoNode node TODO