trees c basic terminology
Este tutorial aprofundado sobre árvores C ++ explica os tipos de árvores, as técnicas transversais de árvores e a terminologia básica com imagens e programas de exemplo:
Nesta série C ++, até agora vimos a estrutura de dados linear de natureza estática e dinâmica. Agora vamos prosseguir com a estrutura de dados não linear. A primeira estrutura de dados nesta categoria é “Árvores”.
Árvores são estruturas de dados hierárquicas não lineares. Uma árvore é uma coleção de nós conectados uns aos outros por meio de “arestas” que são direcionadas ou não. Um dos nós é designado como “nó raiz” e os nós restantes são chamados de nós filhos ou nós folha do nó raiz.
Em geral, cada nó pode ter tantos filhos, mas apenas um nó pai.
=> Confira toda a série de treinamento C ++
como testar uma página da web
Os nós de uma árvore estão no mesmo nível, chamados de nós irmãos, ou podem ter um relacionamento pai-filho. Nós com o mesmo pai são nós irmãos.
O que você aprenderá:
- Árvores em C ++
- Tipos de árvores C ++
- Técnicas de travessia de árvores
- Conclusão
- Leitura recomendada
Árvores em C ++
A seguir está uma árvore de exemplo com suas várias partes.
Vamos examinar as definições de alguns termos básicos que usamos para árvores.
- Nó raiz: Este é o nó superior na hierarquia da árvore. No diagrama acima, o Nó A é o nó raiz. Observe que o nó raiz não tem nenhum pai.
- Nó da folha: É o nó mais inferior em uma hierarquia de árvore. Os nós folha são os nós que não possuem nenhum nó filho. Eles também são conhecidos como nós externos. Os nós E, F, G, H e C na árvore acima são todos nós folha.
- Subárvore: A subárvore representa vários descendentes de um nó quando a raiz não é nula. Uma árvore geralmente consiste em um nó raiz e uma ou mais subárvores. No diagrama acima, (B-E, B-F) e (D-G, D-H) são subárvores.
- Nó pai: Qualquer nó, exceto o nó raiz, que tem um nó filho e uma borda para cima em direção ao pai.
- Nó ancestral: É qualquer nó predecessor em um caminho da raiz para esse nó. Observe que a raiz não possui ancestrais. No diagrama acima, A e B são os ancestrais de E.
- Chave: Ele representa o valor de um nó.
- Nível: Representa a geração de um nó. Um nó raiz está sempre no nível 1. Os nós filhos da raiz estão no nível 2, os netos da raiz estão no nível 3 e assim por diante. Em geral, cada nó está em um nível mais alto que seu pai.
- Caminho: O caminho é uma sequência de arestas consecutivas. No diagrama acima, o caminho para E é A => B-> E.
- Grau: O grau de um nó indica o número de filhos que um nó possui. No diagrama acima, o grau de B e D é 2 cada, enquanto o grau de C é 0.
Tipos de árvores C ++
A estrutura de dados em árvore pode ser classificada nos seguintes subtipos, conforme mostrado no diagrama abaixo.
# 1) Árvore Geral
A árvore geral é a representação básica de uma árvore. Ele possui um nó e um ou mais nós filhos. O nó de nível superior, ou seja, o nó raiz está presente no nível 1 e todos os outros nós podem estar presentes em vários níveis.
Uma árvore geral é mostrada na figura abaixo.
Conforme mostrado na figura acima, uma árvore geral pode conter qualquer número de subárvores. Os nós B, C e D estão presentes no nível 2 e são nós irmãos. Da mesma forma, os nós E, F, G e H também são nós irmãos.
Os nós presentes em diferentes níveis podem exibir uma relação pai-filho. Na figura acima, os nós B, C e D são filhos de A. Os nós E e F são filhos de B, enquanto os nós G e H são filhos de D.
A árvore geral é demonstrada abaixo usando a implementação C ++:
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }
Resultado:
conversores de vídeo grátis para windows 10
A árvore geral criada é a seguinte:
10
/
20 30
/
40
# 2) Florestas
Sempre que excluímos o nó raiz da árvore e as arestas que unem os elementos do próximo nível e a raiz, obtemos conjuntos separados de árvores como mostrado abaixo.
Na figura acima, obtivemos duas florestas excluindo o nó raiz A e as três arestas que conectavam o nó raiz aos nós B, C e D.
# 3) Árvore Binária
Uma estrutura de dados em árvore na qual cada nó tem no máximo dois nós filhos é chamada de árvore binária. Uma árvore binária é a estrutura de dados de árvore mais popular e é usada em uma variedade de aplicativos, como avaliação de expressão, bancos de dados, etc.
A figura a seguir mostra uma árvore binária.
Na figura acima, vemos que os nós A, B e D têm dois filhos cada. Uma árvore binária em que cada nó tem exatamente zero ou dois filhos é chamada de árvore binária completa. Nesta árvore, não há nós com um filho.
Uma árvore binária completa possui uma árvore binária que é completamente preenchida, com exceção do nível mais baixo que é preenchido da esquerda para a direita. A árvore binária mostrada acima é uma árvore binária completa.
A seguir está um programa simples para demonstrar uma árvore binária. Observe que a saída da árvore é a sequência de passagem em ordem da árvore de entrada.
#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
# 4) Árvore de pesquisa binária
A árvore binária ordenada é chamada de árvore de pesquisa binária. Em uma árvore de pesquisa binária, os nós à esquerda são menores que o nó raiz, enquanto os nós à direita são maiores ou iguais ao nó raiz.
Um exemplo de árvore de pesquisa binária é mostrado abaixo.
Na figura acima, podemos ver que os nós da esquerda são todos menores que 20, que é o elemento raiz. Os nós certos, por outro lado, são maiores que o nó raiz. A árvore de pesquisa binária é usada em técnicas de pesquisa e classificação.
como abrir o arquivo .at no mac
# 5) Árvore de Expressão
Uma árvore binária usada para avaliar expressões aritméticas simples é chamada de árvore de expressão.
Uma árvore de expressão simples é mostrada abaixo.
No exemplo de árvore de expressão acima, representamos a expressão (a + b) / (a-b). Conforme mostrado na figura acima, os nós não-folha da árvore representam os operadores da expressão, enquanto os nós-folha representam os operandos.
Árvores de expressão são usadas principalmente para resolver expressões algébricas.
Técnicas de travessia de árvores
Vimos estruturas de dados lineares como matrizes, listas vinculadas, pilhas, filas, etc. Todas essas estruturas de dados têm uma técnica de passagem comum que atravessa a estrutura apenas de uma maneira, ou seja, linearmente.
Mas, no caso de árvores, temos diferentes técnicas de travessia, conforme listado abaixo:
# 1) Em ordem: Nesta técnica de travessia, percorremos a subárvore esquerda primeiro até que não haja mais nós na subárvore esquerda. Depois disso, visitamos o nó raiz e, em seguida, avançamos para percorrer a subárvore direita até que não haja mais nós para percorrer na subárvore direita. Portanto, a ordem de travessia de inOrder é esquerda-> raiz-> direita.
# 2) Pré-encomenda: Para a técnica de travessia de pré-ordem, processamos o nó raiz primeiro, depois percorremos toda a subárvore esquerda e, finalmente, percorremos a subárvore direita. Portanto, a ordem de travessia da pré-ordem é root-> left-> right.
# 3) Pós-pedido: Na técnica de travessia pós-ordem, percorremos a subárvore esquerda, depois a subárvore direita e, finalmente, o nó raiz. A ordem de passagem para a técnica postorder é esquerda-> direita-> raiz.
Se n é o nó raiz e 'l' e 'r' são nós esquerdo e direito da árvore, respectivamente, então os algoritmos de travessia da árvore são os seguintes:
Algoritmo de ordem (lnr):
- Percorra a subárvore esquerda usando inOrder (left- Subtree).
- Visite o nó raiz (n).
- Percorra a subárvore direita usando inOrder (subárvore direita).
Algoritmo de pré-encomenda (nlr):
- Visite o nó raiz (n).
- Percorra a subárvore esquerda usando a pré-ordem (subárvore esquerda).
- Percorra a subárvore direita usando a pré-ordem (subárvore direita).
Algoritmo Postorder (lrn):
- Percorra a subárvore esquerda usando postOrder (subárvore esquerda).
- Percorra a subárvore direita usando postOrder (subárvore direita).
- Visite o nó raiz (n).
A partir dos algoritmos de técnicas de travessia acima, vemos que as técnicas podem ser aplicadas a uma determinada árvore de maneira recursiva para obter o resultado desejado.
Considere a seguinte árvore.
Usando as técnicas de travessia acima, a sequência de travessia para a árvore acima é fornecida abaixo:
- Percurso de InOrder: 2 3 5 6 10
- Passagem de pré-pedido: 6 3 2 5 10
- PostOrder traversal: 2 5 3 10 6
Conclusão
Árvores são uma estrutura de dados hierárquica não linear usada em muitos aplicativos na área de software.
Ao contrário das estruturas de dados lineares que têm apenas uma maneira de percorrer a lista, podemos percorrer as árvores de várias maneiras. Tivemos um estudo detalhado das técnicas de travessia e os vários tipos de árvores neste tutorial.
=> Dê uma olhada no guia para iniciantes em C ++ aqui
Leitura recomendada
- Estrutura de dados da árvore B e da árvore B + em C ++
- Estrutura de dados de árvore binária em C ++
- Tipos de riscos em projetos de software
- Árvore AVL e estrutura de dados de heap em C ++
- Tipos de dados Python
- 20 perguntas simples para verificar seu conhecimento básico de teste de software [questionário online]
- Tipos de dados C ++
- Operações básicas de entrada / saída em C ++