binary tree data structure c
Este tutorial aprofundado sobre árvore binária em C ++ explica tipos, representação, transversal, aplicativos e implementação de árvores binárias em C ++:
Uma árvore binária é uma estrutura de dados em árvore amplamente usada. Quando cada nó de uma árvore tem no máximo dois nós filhos, a árvore é chamada de árvore Binária.
Portanto, uma árvore binária típica terá os seguintes componentes:
- Uma subárvore esquerda
- Um nó raiz
- Uma subárvore direita
=> Observe a lista completa de tutoriais em C ++ nesta série.
O que você aprenderá:
- Árvore binária em C ++
- Tipos de árvore binária
- Representação de árvore binária
- Implementação de árvore binária em C ++
- Binary Tree Traversal
- Aplicações da árvore binária
- Conclusão
- Leitura recomendada
Árvore binária em C ++
Uma representação pictórica de uma árvore binária é mostrada abaixo:
Em uma determinada árvore binária, o número máximo de nós em qualquer nível é 2l-1onde 'l' é o número do nível.
Assim, no caso do nó raiz no nível 1, o número máximo de nós = 21-1= 20= 1
Como cada nó em uma árvore binária tem no máximo dois nós, o máximo de nós no próximo nível será, 2 * 2l-1.
prós e contras do linux vs windows
Dada uma árvore binária de profundidade ou altura de h, o número máximo de nós em uma árvore binária de altura h = 2h- 1.
Portanto, em uma árvore binária de altura 3 (mostrada acima), o número máximo de nós = 23-1 = 7.
Agora vamos discutir os vários tipos de árvores binárias.
Tipos de árvore binária
A seguir estão os tipos mais comuns de árvores binárias.
# 1) Árvore binária completa
Uma árvore binária em que cada nó tem 0 ou 2 filhos é denominada árvore binária completa.
Acima é mostrada uma árvore binária completa na qual podemos ver que todos os seus nós, exceto os nós folha, têm dois filhos. Se L é o número de nós folha e 'l' é o número de nós internos ou não folha, então para uma árvore binária completa, L = l + 1.
# 2) Árvore binária completa
Uma árvore binária completa tem todos os níveis preenchidos, exceto o último nível e o último nível tem todos os seus nós, tanto quanto à esquerda.
A árvore mostrada acima é uma árvore binária completa. Um exemplo típico de uma árvore binária completa é um heap binário que discutiremos nos tutoriais posteriores.
# 3) Árvore binária perfeita
Uma árvore binária é considerada perfeita quando todos os seus nós internos têm dois filhos e todos os nós folha estão no mesmo nível.
Um exemplo de árvore binária mostrado acima é uma árvore binária perfeita, pois cada um de seus nós tem dois filhos e todos os nós folha estão no mesmo nível.
Uma árvore binária perfeita de altura h tem 2h- 1 número de nós.
# 4) Uma árvore degenerada
Uma árvore binária em que cada nó interno tem apenas um filho é chamada de árvore degenerada.
A árvore mostrada acima é uma árvore degenerada. No que diz respeito ao desempenho desta árvore, as árvores degeneradas são iguais às listas vinculadas.
# 5) Árvore Binária Balanceada
Uma árvore binária na qual a profundidade das duas subárvores de cada nó nunca difere em mais de 1 é chamada de árvore binária balanceada.
A árvore binária mostrada acima é uma árvore binária balanceada, já que a profundidade das duas subárvores de cada nó não é maior que 1. As árvores AVL que iremos discutir em nossos tutoriais subsequentes são uma árvore balanceada comum.
Representação de árvore binária
Uma árvore binária tem memória alocada de duas maneiras.
# 1) Representação Sequencial
Esta é a técnica mais simples para armazenar uma estrutura de dados em árvore. Uma matriz é usada para armazenar os nós da árvore. O número de nós em uma árvore define o tamanho da matriz. O nó raiz da árvore é armazenado no primeiro índice da matriz.
Em geral, se um nó é armazenado no iºlocalização então seu filho esquerdo e direito é armazenado no local 2i e 2i + 1, respectivamente.
Considere a seguinte Árvore Binária.
A representação sequencial da árvore binária acima é a seguinte:
como abrir um arquivo jnlp
Na representação acima, vemos que os filhos esquerdo e direito de cada nó são armazenados nas localizações 2 * (node_location) e 2 * (node_location) +1 respectivamente.
Por exemplo, a localização do nó 3 na matriz é 3. Portanto, seu filho esquerdo será colocado em 2 * 3 = 6. Seu filho direito estará na localização 2 * 3 +1 = 7. Como podemos ver na matriz, os filhos de 3 que são 6 e 7 são colocados nas localizações 6 e 7 na matriz.
A representação sequencial da árvore é ineficiente, pois o array que é usado para armazenar os nós da árvore ocupa muito espaço na memória. Conforme a árvore cresce, essa representação se torna ineficiente e difícil de gerenciar.
Essa desvantagem é superada armazenando os nós da árvore em uma lista vinculada. Observe que, se a árvore estiver vazia, o primeiro local de armazenamento do nó raiz será definido como 0.
# 2) Representação de lista vinculada
Nesse tipo de representação, uma lista vinculada é usada para armazenar os nós da árvore. Vários nós estão espalhados na memória em locais não contíguos e os nós são conectados usando o relacionamento pai-filho como uma árvore.
O diagrama a seguir mostra uma representação de lista vinculada para uma árvore.
Conforme mostrado na representação acima, cada nó da lista vinculada tem três componentes:
- Apontador esquerdo
- Parte de dados
- Apontador direito
O ponteiro esquerdo tem um ponteiro para o filho esquerdo do nó; o ponteiro direito tem um ponteiro para o filho direito do nó, enquanto a parte de dados contém os dados reais do nó. Se não houver filhos para um determinado nó (nó folha), os ponteiros esquerdo e direito desse nó serão definidos como nulos, conforme mostrado na figura acima.
Implementação de árvore binária em C ++
A seguir, desenvolvemos um programa de árvore binária usando uma representação de lista vinculada em C ++. Usamos uma estrutura para declarar um único nó e, em seguida, usando uma classe, desenvolvemos uma lista vinculada de nós.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< Resultado:
Árvore binária criada:
5 10 15 20 30 40 45
Binary Tree Traversal
Já discutimos os percursos em nosso tutorial básico sobre árvores. Nesta seção, vamos implementar um programa que insere nós na árvore binária e também demonstra todas as três travessias, ou seja, ordem, pré-ordem e pós-ordem, para uma árvore binária.
#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'< Resultado:
Travessia em ordem:
ABCDEFG
Transferência de pedido por correspondência:
G F E D C B A
Pré-encomenda de traversal:
ABCDEFG
Aplicações da árvore binária
Uma árvore binária é usada em muitos aplicativos para armazenar dados.
Algumas das aplicações importantes de árvores binárias estão listadas abaixo:
- Árvores binárias de pesquisa: Árvores binárias são usadas para construir uma árvore de pesquisa binária que é usada em muitos aplicativos de pesquisa, como conjuntos e mapas em muitas bibliotecas de linguagem.
- Árvores de hash: Usado para verificar hashes principalmente em aplicativos especializados de assinatura de imagem.
- Pilhas: Heaps são usados para implementar filas de prioridade que são usadas para roteadores, processadores de agendamento no sistema operacional, etc.
- Codificação Huffman: A árvore de codificação Huffman é usada em algoritmos de compactação (como compactação de imagem), bem como em aplicativos criptográficos.
- Árvore de sintaxe: Os compiladores freqüentemente constroem árvores de sintaxe que nada mais são do que árvores binárias para analisar expressões usadas no programa.
Conclusão
Árvores binárias são estruturas de dados amplamente utilizadas na indústria de software. Árvores binárias são aquelas cujos nós têm no máximo dois nós filhos. Vimos vários tipos de árvores binárias como uma árvore binária completa, uma árvore binária completa, uma árvore binária perfeita, uma árvore binária degenerada, uma árvore binária balanceada, etc.
Os dados da árvore binária também podem ser percorridos usando técnicas de travessia em ordem, pré-ordem e pós-ordem que vimos em nosso tutorial anterior. Na memória, uma árvore binária pode ser representada usando uma lista vinculada (memória não contígua) ou matrizes (representação sequencial).
A representação de lista vinculada é mais eficiente quando comparada aos arrays, pois os arrays ocupam muito espaço.
=> Confira os melhores tutoriais de treinamento em C ++ aqui.
Leitura recomendada
- Árvore AVL e estrutura de dados de heap em C ++
- Estrutura de dados da árvore B e da árvore B + em C ++
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de pilha de dados em C ++ com ilustração
- Estrutura de dados de lista ligada circular em C ++ com ilustração
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Introdução às estruturas de dados em C ++
- Estrutura de dados da fila de prioridade em C ++ com ilustração