Estruturas de Dados Avançadas - Árvore

 A estrutura de árvore tem diversas aplicações e pode ser usadas em pastas de um sistema operacional, interfaces gráficas, bancos de dados entre outros.

É diferente de vetor, que tem os dados em uma sequência, na árvore os dados ficam de forma hierárquica.

Uma árvore é um conjunto de elementos que armazenam informações chamados nodos ou nó, consistindo de um nós chamado raiz, abaixo do qual estão as subárvores (ramos ou filhos) que compõem a árvore. O elemento que não possui subárvore é conhecido como nós externos ou folha.

Costumamos representar uma árvore de forma invertida, com a raiz iniciando por cima

O número de subárvore de cada nó é chamado de GRAU desse nó

Os nós de grau 0 são chamados de nós externos ou folhas 

Nós abaixo de um determinado nó são seus descendentes, no exemplo abaixo os nós 2 e 12 são descentes do nó 8.

Descentes do 15: todos os outros nós.

O nível da árvore inicia pela raiz, ela tem o nível 0

A altura de um nó é o comprimento mais longo entre ele e uma folha

Profundidade de um nó é a distância percorrida da raiz a esse nó

Representação

Uma árvore pode ser representada pelas formas hierárquica, diagrama de inclusão, diagrama de barras, por aninhamento e numeração por níveis.

A hierárquica é parecida com um organograma de uma empresa, linhas unem dois nodos e indicam o relacionamento lógico entre eles. Tradicionalmente desenha-se a raiz na parte superior e todos os nodos subordinados na parte inferior, mas o contrário também é possível.

Diagrama de inclusão, um círculo representa cada nodo e seus nodos descendentes são inseridos dentro do círculo de seus pais. Também conhecida como diagrama de Venn, é muito utilizada na representação de conjuntos.

Em um diagrama de barras, linhas são usadas para mostrar a hierarquia dos nodos. A raiz possui a linha de maior tamanho e os nodos irmãos possuem linhas de tamanhos iguais. Método bastante utilizado na criação de índices de livros.

Usando numeração por níveis o nodo raiz recebe o número um e todos os nodos seguintes recebem uma numeração sequencial, sempre antecedidos pela numeração de seus nodos superiores.

Na representação por aninhamento, também conhecida por "representação por parênteses aninhados", a sucessão de parênteses reproduz as relações entre os nodos, aninhando um nodo filho ao seu pai.

Com isso,  temos uma visão geral do conceito de árvore, no próximo post iremos ver como funciona uma árvore binária.

Até a próxima

Arvore de Natal com VisuAlg

O Natal é uma data muito especial para reunir a família e celebrar a vida e uma data especial dessa, não pode passar batida, vamos criar um algoritmo em homenagem ao Natal.

Vamos fazer uma árvore de natal utilizando a ferramenta VisuAlg

 Algoritmo "arvore"  
 // Descrição  :Árvore de Natal  
 // Autor(a)  : Cléuber José  
 // Data atual : 23/12/2021  
 Var  
 // Seção de Declarações das variáveis   
   i,j,inicia, qtde, tam:inteiro  
 Inicio  
 // Seção de Comandos, procedimento, funções, operadores, etc...   
   escreval("==========Árvore de Natal========")  
   escreva("Informe o tamanho da árvore: ")  
   leia(tam)  
   inicia<-tam  
   qtde<-1  
   escreval  
   escreval  
   para i de 1 ate tam faca  
    escreva(" ")  
   fimpara  
   escreval(" *")  
   para i de 1 ate tam faca  
    para j de 1 ate inicia faca  
      escreva(" ")  
    fimpara  
    inicia<-inicia-1  
    escreva("/")  
    para j de 1 ate qtde faca  
      escreva("*")  
    fimpara  
    qtde<-qtde+2  
    escreval("\")  
   fimpara  
   para i de 1 ate tam faca  
    escreva(" ")  
   fimpara  
   escreval("|_|")  
 Fimalgoritmo