Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvore, Compostas por:, A ((B), (C)), Binary Trees, AVL, Pesquisa Binária,…
Árvore
A mais importante estrutura de dados não linear, ou seja, seus elementos são dispostos de forma hierárquica e não sequencial.
Se diferencia das linked lists porque os seus nodes podem conter ponteiros apontando para diversos elementos.
-
Compostas por:
Raiz: o node no topo da árvore, que da está conectado à todos os nodes da árvore. Folha: node que não dá origem à nenhum outro elemento, ou seja, aponta para NULL.
Pais: dizemos que um node é pai do outro quando ele dá origem á esse outro node.
FIlhos: o node do qual o outro é pai.
Irmão: dois nodes que compartilham o mesmo pai.
-
-
Binary Trees
-
Árvores especiais usadas para se realizarem buscas nos algoritmos de ordenação. Principalmente usada no Heap Sort.
AVL
-
Usada para realizar funções de inserção e busca de maneira mais fácil, visando optimizar o tempo de execução
-
-
Pré-Ordem
Primeiro o elemento acessa à si mesmo e depois o elemento à sua esquerda. Esse, por sua vez , repete o mesmo processo. Isso continua até todos os à esquerda forem lidos. Então, são acessados os elementos da direita, debaixo para cima.
Em ordem
Antes do elemento acessar à si mesmo, ele tem que acessar o elemento à sua esquerda, ou seja, ir para o endereço contido no seu ponteiro esquerdo. Só quando chegamos no elemento mais à esquerda da árvore, ai que ele é lido. Depois, vamos subindo na árvore. Os elementos à direita são lidos por último.
Pós-ordem
Os elementos de baixo-esquerda são lidos primeiro. Seguidos pelos seus irmãos da direita e depois os pais. Ou seja, o procedimento é: acessar o ponteiro da esquerda, depois o da direita e só depois à si próprio.
Ex: Nesse caso específico A seria a raiz, (D; E; F) seriam as folhas. B seria pai de D e E, os quais seriam filhos de B, por consequência. D e E seriam irmãos e a altura seria 3.
OBS: pode-se ver que só há um caminho para ir de A até as folhas. Isso acontece em todas as árvores.
-
OBS: nas árvores para ordenação, o elemento maior é sempre acrescentado À ESQUERDA. Dessa forma, quando retirarmos os elementos, começando pelo da esquerda da base da árvore, teremos uma lista ordenada