Mostrar código-fonte de Árvore (estrutura de dados)

[[Ficheiro:Tree.example.png|thumb|300px|Representação simples de uma árvore. O nodo A, a raiz, tem como filhos diretos: B, C, E e filhos indiretos: D, F e G. B, C e E são irmãos, assim como D e F.]]
'''Árvore''', no contexto da [[programação]], [[engenharia de software]] e [[ciência da computação]], é uma das mais importantes [[estrutura de dados|estruturas de dados]] não lineares.<ref name="goodrich" /> Herda as características das [[topologia em árvore]]. Conceptualmente diferente das [[lista]]s, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica,<ref name="nina_renata" /> seus elementos se encontram "acima" ou "abaixo" de outros elementos da árvore.<ref name="goodrich" />

São estruturas eficientes e simples em relação ao tratamento computacional, diferentemente dos [[grafos]].<ref name="jayme_lilian" /> Há inúmeros problemas no mundo real que podem ser modelados e resolvidos através das árvores. [[sistema de arquivos|Estruturas de pastas]] de um sistema operacional, [[interfaces gráficas]], [[bancos de dados]] e [[site|sites da Internet]] são exemplos de aplicações de árvores.<ref name="goodrich" />

Uma árvore é formada por um conjunto de elementos que armazenam informações chamados [[nó_(ciência_da_computação)|'''nodos''' ou '''nós''']].<ref name="nina_renata" /><ref name="celes_cer_ran" /> Toda a árvore possui o elemento chamado '''raiz''', que possui ligações para outros elementos denominados ramos ou filhos. Estes ramos podem estar ligados a outros elementos que também podem possuir outros ramos. O elemento que não possui ramos é conhecido como '''nó folha''', nó terminal ou nó externo.<ref name="nina_renata" />

Uma terminologia muito utilizada nas estruturas de árvores tem origem das [[árvore genealógica|árvores genealógicas]]. O relacionamento entre nodos é descrito com os termos "pai" (ou "mãe") para os antecessores diretos de um nodo, "filhos" (ou "filhas") para os descendentes diretos e "irmãos" (ou "irmãs") para todos os nodos com mesmo pai.<ref name="goodrich" /><ref name="nina_renata" />

== Definições básicas ==
=== Definição formal de árvore ===
Formalmente, definimos uma árvore <math>T</math> como um [[conjunto finito]] de zero ou mais nodos tal que<ref name="jayme_lilian" />:<br>
:*se o número de nodos = <math>0</math>, temos uma árvore vazia, ou
:*se o número de nodos > <math>0</math>
::* existe um nó especialmente denominado raiz de <math>T</math>
::* os nós restantes formam <math>m \ge 0</math> conjuntos disjuntos <math>p_1, p_2, ..., p_m</math>, cada um desses conjuntos é uma árvore em si, chamada subárvore da raiz de <math>T</math>, ou simplesmente subárvore.

O número máximo de filhos em um nodo é chamado ''ordem'' da árvore. Uma [[árvore binária]] é aquela de ordem 2, i.e., em que cada elemento possui no máximo 2 filhos.

== Representação == 
[[Ficheiro:Tree_structure_representation.svg|thumb|400px|Diferentes representações de uma árvore: a) hierárquica, b) diagrama de barras, c) diagrama de inclusão, d) aninhamento e e) numeração por níveis]]
Há diversas formas de representação de uma árvore: hierárquica, diagrama de inclusão, diagrama de barras, numeração por níveis, por aninhamento. 

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.<ref name="celes_cer_ran" /> Na figura acima, o item (a) é um exemplo desta representação. 

'''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.<ref name="jayme_lilian" /> O item (c) da figura ao lado mostra a árvore do item (a) usando diagrama de inclusão. 

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.<ref name="jayme_lilian" /> É similar à [[indentação]] usada em linguagens de programação.<ref name="nina_renata" /> O item (b) da imagem ao lado indica como seria a árvore do item (a) usando essa representação. 

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.<ref name="jayme_lilian" /> Item (e) da figura à direita representa a árvore (a) com representação por níveis. 

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.<ref name="nina_renata" /> Como exemplo temos o item (d) da imagem ao lado representando a árvore (a).

<!-- == Tipos de Árvores == -->
== Algoritmos ==

Uma das operações importantes consiste em percorrer cada elemento da árvore uma única vez. Esse percurso, também chamado de '''travessia''' da árvore, pode ser feito em '''pré-ordem''' (os filhos de um nó são processados após o nó) ou em '''pós-ordem''' (os filhos são processados antes do nó). Em [[árvore binária|árvores binárias]] é possível ainda fazer uma travessia '''em-ordem''', em que se processa o filho à esquerda, o nó, e finalmente o filho à direita.

O [[algoritmo]] abaixo descreve uma travessia ''pré-ordem'':
PercursoPreordem(nó):
Processa nó
Para cada filho de nó (se houver)
Executa recursivamente PercursoPreordem(filho)

Outra operação utilizada nas [[árvore de pesquisa|árvores de pesquisa]] é a travessia da raiz até uma das folhas. Essa operação tem um custo computacional proporcional ao número de níveis da árvore. O ''pior caso'' é a travessia de todos os elementos até a folha de nível mais baixo. Árvores balanceadas apresentam o melhor ''pior caso'' possível, para um certo número de nós. O ''pior caso'' apresenta-se na [[árvore degenerada]] em que cada nó possui exatamente um filho, e a árvore tem o mesmo número de níveis que de nós, assemelhando-se a uma [[lista ligada]].

{{referências|refs=
<ref name="goodrich">{{citar livro
|primeiro1=Michael T.
|ultimo1=Goodrich
|primeiro2=Roberto
|ultimo2=Tamassia
|numero-autores=2
|ano=2013
|edicao=5ª
|titulo=Estruturas de Dados e Algoritmos em Java
|url=https://books.google.com.br/books?id=3s06AgAAQBAJ
|editora=Bookman
|local=Porto Alegre
|isbn=978-85-8260-018-4}}</ref>

<ref name="nina_renata">{{citar livro
|primeiro1=Nina
|ultimo1=Edelweiss
|primeiro2=Renata
|ultimo2=Galante
|numero-autores=2
|ano=2009
|titulo=Estruturas de Dados
|url=https://books.google.com.br/books?id=FmEeJuGug3cC
|series=Série Livros Didáticos Informática UFRGS
|volume=18
|editora=Bookman
|local=Porto Alegre
|isbn=978-85-7780-381-1}}</ref>

<ref name="jayme_lilian">{{citar livro
|primeiro1=Jayme Luiz
|ultimo1=Szwarcfiter
|primeiro2=Lilian
|ultimo2=Markenzon
|numero-autores=2
|ano=2014
|titulo=Estruturas de Dados e seus Algoritmos
|url=https://books.google.com.br/books?id=ozD8AQAACAAJ
|editora=LTC
|edicao=3ª
|local=Rio de Janeiro
|isbn=978-85-216-1750-1}}</ref>

<ref name="celes_cer_ran">{{citar livro
|primeiro1=Waldemar
|ultimo1=Celes
|primeiro2=Renato
|ultimo2=Cerqueira
|primeiro3=José L.
|ultimo3=Rangel
|numero-autores=3
|ano=2004
|titulo=Introdução a estruturas de dados: com técnicas de programação em C
|url=https://books.google.com.br/books?id=_TYWOgAACAAJ
|editora=Elsevier
|local=Rio de Janeiro
|isbn=85-352-1228-0}}</ref>
}}

== Ver também ==
* [[Árvore binária]]
* [[Árvore de busca binária]]
* [[Árvore AVL]]
* [[Árvore ordenada]]
* [[Árvore rubro-negra]]
* [[Árvore 2-3]]
* [[Árvore 2-3-4]]
* [[Árvore B]]
* [[Árvore B+]]
* [[Árvore hiperbólica]]
* [[Topologia em árvore]]

== Ligações externas ==
{{Correlatos
|commons		=tree structure
|wikilivros		=Algoritmos_e_Estruturas_de_Dados/Árvore
|wikiversidade	=Estruturas_de_Dados_Intermediário/Árvore
}}

* {{link|en|2=http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html |3=QMatica.com}} - Site interativo sobre AVL (árvores balanceadas por altura)
*[https://algol.dev/arvores-estrutura-de-dados/ Algol.dev] (Português e inglês) - Artigo sobre árvores.

{{esboço-prog}}

{{Computação}}
{{Engenharia de software}}
{{Processo de desenvolvimento de software}}
{{Estrutura de dados}}

[[Categoria:Estruturas de dados|Arvore]]
[[Categoria:Tipos abstratos de dados]]

[[de:Datenstruktur#Baum]]