Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa mental 8, Árvores, Busca e inserção em uma árvore binária, Travessias…
-
Árvores
-
A profundidade de um vértice v é o comprimento do caminho simples da raiz para v. A altura de uma árvore é o comprimento do caminho simples mais longo da raiz para uma folha.
Todos os descendentes de um vértice v com todas as arestas que os conectam formam a subárvore de T enraizada naquele vértice.
Todos os vértices para os quais um vértice v é um ancestral são ditos ser descendentes de v; os descendentes próprios excluem o próprio vértice v.
-
Se (u, v) é a última aresta do caminho simples da raiz para o vértice v (e u ≠ v), u é dito ser o pai de v e v é chamado de filho de u. Vértices que têm o mesmo pai são ditos ser irmãos.
Para qualquer vértice v em uma árvore T, todos os vértices no caminho simples da raiz para esse vértice são chamados de ancestrais de v. O próprio vértice geralmente é considerado seu próprio ancestral. O conjunto de ancestrais que exclui o próprio vértice é referido como o conjunto de ancestrais próprios.
As árvores enraizadas desempenham um papel muito importante na ciência da computação, com aplicações na descrição de hierarquias, implementação de dicionários, acesso eficiente a conjuntos de dados muito grandes, codificação de dados, análise de algoritmos recursivos e muito mais.
Uma árvore enraizada é uma árvore livre com um vértice arbitrário selecionado como raiz. A raiz é geralmente representada no topo (nível 0 da árvore), os vértices adjacentes à raiz abaixo dela (nível 1), os vértices a duas arestas de distância da raiz ainda abaixo (nível 2), e assim por diante.
Para cada dois vértices em uma árvore, sempre existe exatamente um caminho simples de um desses vértices para o outro.
-
Um subgrafo de um dado grafo G = (V, E) é um grafo G’ = (V’, E’) tal que V’ ⊆ V e E’ ⊆ E.
Uma floresta é um grafo que não tem ciclos, mas não necessariamente é conectado. Cada um de seus componentes conectados é uma árvore.
Uma árvore (ou mais precisamente, uma árvore livre) é um grafo acíclico conectado.
-
-
-
-