Arvores Genéricas

Árvores Genéricas

As árvores são estruturas de dados criadas usualmente através do uso de alocação dinâmica de memória, baseadas em listas encadeadas, que possuem um nodo superior (raiz / pai), apontando para os seus nodos filhos (folhas / filho). Por sua vez cada nodo pai pode possuir nodos filhos, e assim chegamos a definição “recursiva” de uma árvore: um nodo pai aponta para nodos filhos, onde estes nodos filhos também podem ser nodos pais.
Uma árvore genérica é um tipo especial de árvore onde podemos ter um número variável de nodos filhos associados a um nodo pai. Um exemplo de implementação de uma árvore genérica pode ser dado por uma estrutura onde cada nodo possui um ponteiro para o seu nodo pai, um ponteiro para o seu nodo filho, e um ponteiro para o seu nodo irmão. Assim sendo, cada nodo pode possuir um número ilimitado de filhos, pois o seu nodo filho aponta para uma lista ilimitada de nodos no mesmo nível na hierarquia das árvores (irmãos). Além disto, continuamos tendo uma estrutura em árvore, pois cada nodo possui seu nodo pai e seu(s) nodo filho(s).
Uma árvore é um conjunto finito não vazio de elementos dos quais: um é chamado raiz; os restantes estão divididos em m>=0 subconjuntos disjuntos, cada um deles sendo uma árvore.
Os termos: nós, folhas, pai, filho, ancestral, descendente, nível e profundidade de árvores binárias têm definições equivalentes para árvores genéricas.
O grau do nó de uma árvore corresponde ao número de seus filhos (m).
Pela definição de árvores genéricas acima, as árvores (a) e (b) abaixo são equivalentes (pois não há distinção na ordem das sub-árvores).

Árvores ordenadas: árvores nas quais as sub-árvores de cada nó formam um conjunto ordenado. Podemos então falar de primeiro filho, segundo filho, e assim por diante.
Se as árvores acima forem ordenadas, então não são equivalentes.

Aplicações de árvores genéricas: Árvores de Jogos

Game Trees são árvores que representam as possibilidades de jogadas para