Análise e Exercícios sobre Árvores de Busca Binária em C

Estruturas de Dados II Análise do Código Árvore De Busca Binária e Exercícios Os códigos fontes em C deste material foram desenvolvidos pelo prof Dr André Kishimoto Prof Dr Ivan Carlos Alcântara de Oliveira httpsorcidorg0000000260207535 Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Conceito BST é uma árvore binária cujo o raiz armazena o elemento ID é denominada árvore de busca binária se Todo elemento armazenado na subárvore esquerda é menor que ID Nenhum elemento armazenado na subárvore direita é menor que ID As subárvores esquerda e direita também são árvores de busca binária Observe que a definição de árvore de busca binária BST é recursiva Exemplo Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Conceito Luís é o raiz desta árvore Os elementos Diogo Carlos e Feliciana pertencentes a subárvore esquerda são menores que Luís E os elementos da subárvore direita Raí Paulo Ronaldo são maiores que Luís Além disso as subárvores cujo raiz são Diogo e Raí também possuem esta característica logo esta árvore é uma árvore de busca binária BST Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Exemplo F C B I G M Estruturas de Dados Árvores BST Definição de um nó NodeBSTh NodeBSTh ifndef NODEBSTH define NODEBSTH include string class NodeBST private int mID stdstring mData NodeBST mParent NodeBST mLeft NodeBST mRight ID Estruturas de Dados Árvores BST Definição de um nó NodeBSTh Nível do nó int GetDepthInternalconst NodeBST node const Altura do nó int GetHeightInternalconst NodeBST node const Estruturas de Dados Árvores BST Definição de um nó NodeBSTh public Construtor e Destrutor NodeBSTint id const stdstring data NodeBST parent nullptr NodeBST left nullptr NodeBST right nullptr NodeBST Copia dados de um nó para a nó da BST void CopyDataFromconst NodeBST node Métodos Get stdstring GetData const NodeBST GetParent const NodeBST GetLeft const NodeBST GetRight const int GetDegree const Obtém o grau do nó int GetDepth const Obtém o nível do nó int GetHeight const Obtém a altura do nó Estruturas de Dados Árvores BST Definição de um nó NodeBSTh public Métodos Set void SetDataconst stdstring data void SetParentNode parent void SetLeftNodeBST left void SetRightNodeBST right bool IsRoot const verifica se é raiz bool IsLeaf const verifica se é nó folha Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp NodeBSTcpp include NodeBSTh include Utilsh Construtor NodeBSTNodeBSTint id const stdstring data NodeBST parent NodeBST left NodeBST right mIDid mDatadata mParentparent mLeftleft mRightright Destrutor NodeBSTNodeBST mParent nullptr mLeft nullptr mRight nullptr Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp Obtém o nó raiz Node TreeGetRoot const return mRoot Atualiza o raiz da árvore void TreeSetRootNode root mRoot root Verifica se a árvore está vazia bool TreeIsEmpty const return mRoot nullptr Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp Copia dados de um nó para ó nó da BST void NodeBSTCopyDataFromconst NodeBST node mID nodeGetID mData nodeGetData Obtém o valor do ID do nó da BST int NodeBSTGetID const return mID Muda o valor do ID do nó da BST void NodeBSTSetIDint id mID id O nível level ou depth de um nó N é obtido pela equação dN nível do nó N nível do pai de N 1 O raiz tem nível 0 Então o nível do nó M é 2 F C B I G M Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp Nível 0 Nível 1 Nível 2 Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp int NodeGetDepth const Obtém o nível do nó return GetDepthInternalthis Obtém o nível do nó a partir do nível do nó pai int NodeGetDepthInternalconst Node node const if nodeIsRoot return 0 else return 1 GetDepthInternalnodeGetParent A altura de um nó N node height se o nó N é uma folha ou seja não tem filhos então sua altura é zero há zero arestas abaixo desse nó Caso contrário hN 1 maxhfilhos do nó N onde h é altura Então a altura de F é 2 F C B I G M Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp h 2 h 1 h 0 Estruturas de Dados Árvores BST Definição de um nó NodeBSTcpp Obtém a altura do nó int NodeGetHeight const return GetHeightInternalthis Obtém a altura do nó a partir dos nós filhos Caminha até os nós folhas int NodeGetHeightInternalconst Node node const if node nullptr nodeIsLeaf return 0 else return 1 UtilsMaxGetHeightInternalnode GetLeft GetHeightInternalnodeGetRight Estruturas de Dados Árvores Árvores Binárias Definição de um nó Utilsh ifndef UTILSH define UTILSH Cria namespace Utils contendo uma função que obtém o máximo de dois valores de qualquer tipo de dado namespace Utils template typename T static T MaxT l T r return l r l r endif Estruturas de Dados Árvores BST BSTh BSTh ifndef BSTH define BSTH include NodeBSTh class BST private NodeBST mRoot void DestroyNodeBST node int GetDegreeInternalconst NodeBST node const stdstring TraverseInOrderInternalconst NodeBST node const stdstring TraversePreOrderInternalconst NodeBST node const stdstring TraversePostOrderInternalconst NodeBST node const stdstring TraverseDepthOrderInternalconst NodeBST node const Estruturas de Dados Árvores BST BSTh NodeBST FindMinInternalNodeBST node const NodeBST FindMaxInternalNodeBST node const NodeBST PredecessorInternalNodeBST node const NodeBST SuccessorInternalNodeBST node const NodeBST SearchInternalNodeBST node int id const NodeBST InsertInternalNodeBST node NodeBST parent int id const stdstring data NodeBST RemoveInternalNodeBST node int id NodeBST RemoveNodeNodeBST node void UpdateParentChildNodeBST parent const NodeBST child NodeBST newChild Estruturas de Dados Árvores BST BSTh public Construtor e destrutor BST BST Obtém o raiz NodeBST GetRoot const Verifica se vazia e limpa árvore bool IsEmpty const void Clear Obtém o grau e o nível int GetDegree const int GetHeight const Realiza os Percursos stdstring TraverseInOrder const stdstring TraversePreOrder const stdstring TraversePostOrder const stdstring TraverseDepthOrder const Estruturas de Dados Árvores BST BSTh Obtém o mínimo e o máximo da árvore NodeBST FindMin const NodeBST FindMax const Obtém o Prédecessor e o Sucessor NodeBST Predecessorint id const NodeBST Successorint id const Busca iterativo e recursivo NodeBST SearchIterativeint id const NodeBST Searchint id const Insere recursivo NodeBST Insertint id const stdstring data Remove Recursivo void Removeint id Estruturas de Dados Árvores BST BSTcpp BSTcpp include NodeBSTh include BSTh include Utilsh include sstream include queue TraverseDepthOrderInternal Construtor sem parãmetros BSTBST mRootnullptr Destrutor BSTBST Clear Estruturas de Dados Árvores BST BSTcpp Limpa toda a árvore deixandoa vazia void BSTClear DestroymRoot mRoot nullptr Destrói todos os nós da BST void BSTDestroyNodeBST node if node nullptr DestroynodeGetLeft DestroynodeGetRight delete node node nullptr Estruturas de Dados Árvores BST BSTcpp Cama o método que retorna o menor valor da BST partindo do raiz NodeBST BSTFindMin const return FindMinInternalmRoot Encontra o menor valor da BST a partir de um nó NodeBST BSTFindMinInternalNodeBST node const if node nullptr return nullptr else if nodeGetLeft nullptr return node else return FindMinInternalnodeGetLeft Estruturas de Dados Árvores BST BSTcpp Cama o método que retorna o maior valor da BST partindo do raiz NodeBST BSTFindMax const return FindMaxInternalmRoot Encontra o maior valor da BST a partir de um nó NodeBST BSTFindMaxInternalNodeBST node const if node nullptr return nullptr else if nodeGetRight nullptr return node else return FindMaxInternalnodeGetRight Estruturas de Dados Árvores BST BSTcpp Cama o método INTERNO que procura o predecessor do nó de ID da BST NodeBST BSTPredecessorint id const NodeBST node SearchInternalmRoot id return node nullptr nullptr PredecessorInternalnode 38 92 21 74 133 35 raiz 85 Considere id 85 Estruturas de Dados Árvores BST BSTcpp Método que procura o predecessor do node da BST NodeBST BSTPredecessorInternalNodeBST node const if nodeGetLeft nullptr return FindMaxInternalnodeGetLeft else NodeBST current node NodeBST currentParent nodeGetParent while currentParent nullptr current currentParentGetLeft current currentParent currentParent currentGetParent return currentParent 38 92 21 74 133 35 raiz 85 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTcpp Chama método que busca o nó de id informado a partir do raiz NodeBST BSTSearchint id const return SearchInternalmRoot id Busca o nó de id a partir do nó informado NodeBST BSTSearchInternalNodeBST node int id const if node nullptr return nullptr else if nodeGetID id return node else if nodeGetID id return SearchInternalnodeGetLeft id else return SearchInternalnodeGetRight id 38 92 21 74 133 35 raiz 85 Considere id 38 Estruturas de Dados Árvores BST BSTcpp Cama o método INTERNO que procura o sucessor do nó de ID da BST NodeBST BSTSuccessorint id const NodeBST node SearchInternalmRoot id return node nullptr nullptr SuccessorInternalnode 38 92 21 74 133 35 raiz 85 Considere id 38 Estruturas de Dados Árvores BST BSTcpp Método que procura o sucessor do node da BST NodeBST BSTSuccessorInternalNodeBST node const if nodeGetRight nullptr return FindMinInternalnodeGetRight else NodeBST current node NodeBST currentParent nodeGetParent while currentParent nullptr current currentParentGetRight current currentParent currentParent currentGetParent return currentParent 38 92 21 74 133 35 raiz 85 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTcpp Chama o método interno que insere um novo nó na BST contendo id e data NodeBST BSTInsertint id const stdstring data if IsEmpty mRoot new NodeBSTid data return mRoot return InsertInternalmRoot nullptr id data Inserir o 38 92 21 40 74 133 35 raiz 38 38 92 21 74 133 35 raiz 40 Estruturas de Dados Árvores BST BSTcpp Método interno que insere um nó de ID NodeBST BSTInsertInternalNodeBST node NodeBST parent int id const stdstring data if node nullptr node new NodeBSTid data parent else if nodeGetID id return nullptr Error Cannot insert duplicate else if nodeGetID id nodeSetLeftInsertInternalnodeGetLeft node id data else if nodeGetID id nodeSetRightInsertInternalnode GetRight node id data return node Estruturas de Dados Árvores BST BSTcpp Chama o método interno que remove um novo nó na BST de id void BSTRemoveint id RemoveInternalmRoot id Estruturas de Dados Árvores BST BSTcpp Atualiza o nó pai void BSTUpdateParentChildNodeBST parent const NodeBST child NodeBST newChild if parent nullptr if parentGetLeft child parentSetLeftnewChild else parentSetRightnewChild else mRoot newChild if newChild nullptr newChildSetParentparent UpdateParentChildparent node newRoot Estruturas de Dados Árvores BST BSTcpp Método interno que remove um nó de ID NodeBST BSTRemoveInternalNodeBST node int id if node nullptr return nullptr else if nodeGetID id node RemoveNodenode else if nodeGetID id nodeSetLeftRemoveInternalnodeGetLeft id else nodeSetRightRemoveInternalnodeGetRight id return node 38 92 21 40 74 133 35 raiz 85 Considere a árvore ao lado Estruturas de Dados Árvores BST BSTcpp Método que atualiza os ponteiros do node removido NodeBST BSTRemoveNodeNodeBST node NodeBST parent nodeGetParent Case 1 The node to be removed is a leaf if nodeIsLeaf UpdateParentChildparent node nullptr delete node node nullptr 38 92 21 40 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTcpp Case 2 The node to be removed has no left childsubtree else if nodeGetLeft nullptr NodeBST newChild nodeGetRight UpdateParentChildparent node newChild delete node node newChild 38 92 21 40 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTcpp Case 3 The node to be removed has no right childsubtree else if nodeGetRight nullptr NodeBST newChild nodeGetLeft UpdateParentChildparent node newChild delete node node newChild 38 92 21 40 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTcpp Case 4 The node to be removed has both left and right childrensubtrees else To remove the node we are reducing the problem to Case 3In this case predecessor is located in the nodes left childsubtree and is the node that has no right childsubtree NodeBST predecessor PredecessornodeGetID Instead of only updating pointers we are copying the data from the predecessor to the node pointer and then we remove the predecessor node nodeCopyDataFrompredecessor nodeSetLeftRemoveInternalnodeGetLeft predecessorGetID return node 92 21 74 133 raiz 85 38 40 35 92 21 40 133 raiz 85 38 35 Estruturas de Dados Árvores BST BSTcpp Método do percurso em ordem simétrica público stdstring BSTTraverseInOrder const return TraverseInOrderInternalmRoot Método do percurso em préordem público stdstring BSTTraversePreOrder const return TraversePreOrderInternalmRoot Método do percurso em pósordem público stdstring BSTTraversePostOrder const return TraversePostOrderInternalmRoot Método do percurso em nívellargura stdstring BSTTraverseDepthOrder const return TraverseDepthOrderInternalmRoot Estruturas de Dados Árvores Árvores Binárias Tipos de Percurso Algoritmo Percurso em Ordem Percurso em ordem Percorre a subárvore esquerda em ordem Processa a raiz Percorre a subárvore direita em ordem Resultado Carlos Diogo Feliciana Luís Paulo Raí Ronaldo Obs A raiz está sempre no meio das subárvore esquerda e direita Estruturas de Dados Árvores BST BSTcpp Método privado para percorrer a árvore em ordem simétrica Os nós visitados são armazenados em um buffer stdstring BSTTraverseInOrderInternalconst NodeBST node const if node nullptr stdostringstream oss oss TraverseInOrderInternalnodeGetLeft oss nodeGetID nodeGetData oss TraverseInOrderInternalnodeGetRight return ossstr return null return ostringstream Classe de fluxo de saída para operar em strings Objetos dessa classe usam um buffer de string que contém uma sequência de caracteres Estruturas de Dados Árvores Árvores Binárias Tipos de Percurso Algoritmo Préordem Percurso em préordem Processa a raiz Percorre a subárvore esquerda em préordem Percorre a subárvore direita em préordem Resultado Luís Diogo Carlos Feliciana Raí Paulo Ronaldo Obs A raiz está sempre a esquerda das subárvores direita e esquerda Estruturas de Dados Árvores BST BSTcpp Método privado para percorrer a árvore em préordem Os nós visitados são armazenados em um buffer stdstring BSTTraversePreOrderInternalconst NodeBST node const if node nullptr stdostringstream oss oss nodeGetID nodeGetData oss TraversePreOrderInternalnodeGetLeft oss TraversePreOrderInternalnodeGetRight return ossstr return null return ostringstream Classe de fluxo de saída para operar em strings Objetos dessa classe usam um buffer de string que contém uma sequência de caracteres Estruturas de Dados Árvores Árvores Binárias Tipos de Percurso Algoritmo PósOrdem Percurso em pósordem Percorre a subárvore esquerda em pósordem Percorre a subárvore direita em pósordem Processa a raiz Resultado Carlos Feliciana Diogo Paulo Ronaldo Raí Luís Obs A raiz está depois das subárvores esquerda e direita Estruturas de Dados Árvores BST BSTcpp Método privado para percorrer a árvore em pósordem Os nós visitados são armazenados em um buffer stdstring BSTTraversePostOrderInternalconst NodeBST node const if node nullptr stdostringstream oss oss TraversePostOrderInternalnodeGetLeft oss TraversePostOrderInternalnodeGetRight oss nodeGetID nodeGetData return ossstr return null return ostringstream Classe de fluxo de saída para operar em strings Objetos dessa classe usam um buffer de string que contém uma sequência de caracteres Estruturas de Dados Árvores Árvores Binárias Tipos de Percurso Algoritmo Percurso em Profundidade Percurso em Profundidade nível level ou depth Percorre a árvore da esquerda para a direita partindose do nível 0 raiz até o último nível da árvore Resultado Luís Diogo Raí Carlos Feliciana Paulo Ronaldo Estruturas de Dados Árvores BST BSTcpp Método privado para percorrer a árvore em nívellargura Os nós visitados são armazenados em um buffer stdstring BSTTraverseDepthOrderInternalconst NodeBST node const if node nullptr stdostringstream oss stdqueueconst NodeBST queue queuepushnode Estruturas de Dados Árvores BST BSTcpp while queueempty const NodeBST n queuefront queuepop oss nGetData if nGetLeft nullptr queuepushnGetLeft if nGetRight nullptr queuepushnGetRight return ossstr return ostringstream Classe de fluxo de saída para operar em strings Objetos dessa classe usam um buffer de string que contém uma sequência de caracteres Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp mainBSTcpp include iostream include string include BSTh Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Método principal que cria um menu de opções para manipulação das operações da árvore BST Inicialmente cria uma árvore com os valores de um vetor int main BST bst new BST int values 30 15 38 10 20 51 8 16 27 for int value values bstInsertvalue stdtostringvalue int option 0 Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp do Monta menu de opções stdcout BST Tree 1 Insert 2 Remove 3 Search 4 Traverse inorder 5 Traverse preorder 6 Traverse postorder 7 Clear 0 Exit Option stdcin option stdcout Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp switch option Trata menu de opções case 1 Insertbst break case 2 Removebst break case 3 Searchbst break case 5 TraverseInOrderbst break case 6 TraversePreOrderbst break case 7 TraversePostOrderbst break case 8 bstClear break Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Finaliza o programa liberando a árvore delete bst return 0 Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Imprime o conteúdo do nó void PrintNodeNodeBST node if node nullptr return stdcout N nodeGetID nodeGetData Parent nodeGetParent nullptr node GetParentGetID 1 Left nodeGetLeft nullptr nodeGetLeft GetID 1 Right nodeGetRight nullptr nodeGetRight GetID 1 Degree nodeGetDegree Depth nodeGetDepth Height nodeGetHeight Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Isere um nó na BST void InsertBST bst int num stdcout Insert number stdcin num NodeBST node bstInsertIterativenum stdtostringnum if node stdcout Node inserted PrintNodenode else stdcout ERROR Couldnt insert node Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Remove um nó de num na BST void RemoveBST bst int num stdcout Remove number stdcin num bstRemovenum Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Procura um nó na BST void SearchBST bst int num stdcout Search number stdcin num NodeBST node bstSearchnum if node stdcout Node found PrintNodenode else stdcout ERROR Couldnt find node Estruturas de Dados Árvores BST Exemplo Teste mainBSTv1cpp Chama o percurso em ordem simétrica da árvore void TraverseInOrderBST bst stdcout bstTraverseInOrder Chama o percurso em pré ordem da árvore void TraversePreOrderBST bst stdcout bstTraversePreOrder Chama o percurso em pós ordem da árvore void TraversePostOrderBST bst stdcout bstTraversePostOrder Estruturas de Dados Árvores BST Atividade Uma empresa deseja realizar determinadas estatísticas a respeito dos seus funcionários Para isso a equipe técnica optou por utilizar uma BST e fazer uso dos métodos de percurso para obter essas estatísticas Sabese que os dados de um funcionário são identificação número inteiro único por funcionário categoria P Presencial O Home Office H Híbrido caracter nome string cargo string sexo F feminino M masculino caracter idade inteiro salário real A partir disso pedese a Elabore a classe Funcionário criando h e cpp em arquivos diferentes b Tendo por base o código da BST apresentado em aula alterar os arquivos da BSTNodeBST e os métodos de seus códigos fontes para permitir o armazenamento de objetos da classe Funcionário Altere os métodos do arquivo que contém o main e faça testes Estruturas de Dados Árvores BST Atividade 2 c A partir de algum dos métodos de percurso modifiqueo para percorrer a BST calcular o gasto com os salários dos funcionários da empresa e retornar o resultado dos gastos Crie uma opção do menu e um método no arquivo que contém o main que permita chamar o método e visualizar o resultado calculado d A partir de algum dos métodos de percurso modifiqueo para receber o sexo do funcionário como parâmetro percorra a BST calcule e retorne o total de funcionários com o sexo informado Crie uma opção do menu e um método no arquivo que contém o main que permita ler o sexo do funcionário chamar o método de percurso implementado e visualizar o resultado e A partir de algum dos métodos de percurso modifiqueo para receber a categoria de um funcionário percorrer a BST calcular e retornar o total de funcionários dessa categoria Criar uma opção do menu e um método no arquivo que contém o main que permita ler a categoria do funcionário processar com o método de percurso desenvolvido e visualizar o resultado f A partir de algum dos métodos de percurso modifiqueo para receber a idade percorrer a BST calcular e apresentar os dados dos funcionários com idade maior do que a informada Crie uma opção do menu e um método no arquivo que contém o main que permita ler a idade e chamar o método de percurso implementado GOODRICH M T TAMASSIA R MOUNT MN Data Structures and Algorithms in C 2ed New Yok Wiley 2011 SZWARCFITER JL MARKENZON L Estruturas de Dados e seus Algoritmos 3ª ed Rio de Janeiro LTC 2010 ZIVIANI N Projeto de Algoritmos Com Implementações em Java e C São Paulo Cengage Learning 2011 Bibliografia Básica