Árvores genéricas são uma coleção de nós onde cada nó é uma estrutura de dados que consiste em registros e uma lista de referências para seus filhos (referências duplicadas não são permitidas). Ao contrário da lista vinculada, cada nó armazena o endereço de vários nós. Cada nó armazena o endereço de seus filhos e o endereço do primeiro nó será armazenado em um ponteiro separado denominado raiz.

As árvores genéricas são as árvores N-árias que possuem as seguintes propriedades: 

            1. Muitas crianças em cada nó.

            2. O número de nós para cada nó não é conhecido com antecedência.

Exemplo: 
 

Árvore Genérica

Para representar a árvore acima, temos que considerar o pior caso, que é o nó com o máximo de filhos (no exemplo acima, 6 filhos) e alocar esse número de ponteiros para cada nó.
A representação do nó com base neste método pode ser escrita como:
 

//Node declaration
struct Node{
   int data;
   struct Node *firstchild;
   struct Node *secondchild;
   struct Node *thirdchild;
   struct Node *fourthchild;
   struct Node *fifthchild;
   struct Node *sixthchild;
}

As desvantagens da representação acima são: 

1. Perda de memória - todos os ponteiros não são necessários em todos os casos. Conseqüentemente, há muito desperdício de memória.
2. Número desconhecido de filhos - O número de filhos de cada nó não é conhecido com antecedência.

Abordagem Simples: 

Para armazenar o endereço dos filhos em um nó, podemos usar uma array ou lista vinculada. Mas vamos enfrentar alguns problemas com os dois.

1. Na lista vinculada , não podemos acessar aleatoriamente o endereço de nenhuma criança. Portanto, será caro.
2. No array , podemos acessar aleatoriamente o endereço de qualquer filho, mas podemos armazenar apenas um número fixo de endereços de filhos nele.

Melhor abordagem:

Podemos usar Dynamic Arrays para armazenar o endereço do endereço dos filhos. Podemos acessar aleatoriamente o endereço de qualquer criança e o tamanho do vetor também não é fixo.

//Node declaration
struct Node{
    int data;
    vector<Node*> children;
}

Abordagem Eficiente:  

Representação do primeiro filho / próximo irmão

 Na representação da primeira criança / próximo irmão, as etapas realizadas são: 

Em cada nó de ligação, os filhos do mesmo pai (irmãos) da esquerda para a direita.

• Remova os links do pai para todos os filhos, exceto o primeiro filho.

Como temos um vínculo entre os filhos, não precisamos de vínculos extras dos pais para todos os filhos. Essa representação nos permite percorrer todos os elementos começando pelo primeiro filho do pai.
 

REPRESENTAÇÃO DA PRIMEIRA CRIANÇA / PRÓXIMO IRMÃO

A declaração do nó para a representação do primeiro filho / próximo irmão pode ser escrita como: 
 

//Node declaration
struct Node{
    int data;
    struct Node *firstChild;
    struct Node *nextSibling;
}

Vantagens: 

• Eficiência de memória - nenhum link extra é necessário, portanto, muita memória é salva.
• Tratadas como árvores binárias - Como podemos converter qualquer árvore genérica em representação binária, podemos tratar todas as árvores genéricas com uma representação do primeiro filho / próximo irmão como árvores binárias. Em vez de ponteiros para a esquerda e para a direita, usamos apenas firstChild e nextSibling.
• Muitos algoritmos podem ser expressos mais facilmente porque é apenas uma árvore binária.
• Cada nó é de tamanho fixo, nenhuma array ou vetor auxiliar é necessário.

Altura da árvore genérica a partir da array pai  
Transversal da ordem no nível da árvore genérica