Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores - Coggle Diagram
Árvores
-
Árvores enraizadas
para cada dois vértices em uma árvore, sempre existe exatamente um caminho simples de um desses vértices para o outro
Esta propriedade permite selecionar um vértice arbitrário em uma árvore livre e considerá-la como a raiz da chamada árvore enraizada
Uma árvore enraizada é geralmente representado colocando sua raiz no topo (nível 0 da árvore), os vértices adjacente à raiz abaixo dela (nível 1), os vértices duas arestas além da raiz ainda abaixo (nível 2), e assim por diante
desempenham um papel muito importante na ciência da computação, uma aplicação óbvia das árvores é para descrever hierarquias, de diretórios de arquivos a organogramas de empresas
-
Árvore binária
árvore ordenada na qual cada vértice não tem mais de dois filhos e cada filho é designado como filho esquerdo ou filho direito de seu pai; uma árvore binária também pode estar vazia
geralmente é implementada para fins de computação por uma coleção de nós correspondentes aos vértices da árvore
Cada nó contém alguma informação associada ao vértice e dois ponteiros para os nós que representam o filho esquerdo e o filho direito do vértice, respectivamente
Quando precisamos procurar um elemento de um determinado valor v em tal árvore, fazemos isso recursivamente da seguinte maneira. Se a árvore estiver vazia, a pesquisa termina em falha
Se a árvore não estiver vazia, comparamos v com a raiz K(r) da árvore
Se eles corresponderem, um elemento desejado é encontrado e a pesquisa pode ser interrompida; se não corresponderem, continuamos com a busca na subárvore esquerda da raiz se v < K(r) e na subárvore direita se v > K(r)
muitos problemas sobre árvores binárias podem ser resolvidos aplicando a técnica de dividir e conquistar
Os algoritmos de divisão e conquista mais importantes para árvores binárias são os três percursos clássicos: pré-ordem, in-ordem e pós-ordem
Na travessia de pré-ordem, a raiz é visitada antes que as subárvores esquerda e direita sejam visitadas
Na travessia inorder, a raiz é visitada depois de visitar sua subárvore esquerda, mas antes de visitar a subárvore direita
No percurso pós-ordem, a raiz é visitada após visitar as subárvores esquerda e direita (nessa ordem)
é um grafo acíclico conectado. No caso de um grafo direcionado, geralmente estamos interessados em caminhos direcionados
Um grafo que não tem ciclos, mas não é necessariamente conectado é chamado de floresta: cada um de seus componentes conectados é uma árvore
As árvores têm várias propriedades importantes que outros gráficos não têm. Em particular, o número de arestas em uma árvore é sempre um a menos que o número de suas arestas
-
Árvores Ordenadas
é uma árvore enraizada na qual todos os filhos de cada vértice são ordenados. É conveniente supor que em um diagrama de árvore, todos os filhos são ordenados da esquerda para a direita