Nomenclatures importantes para o entendimento e estudo

Nó (Node)

• A estrutura mínima de um nó são seus dados e o endereço dos nós hierarquicamente relacionados, seja ancestral ou descendente.

Raiz (Root)

• Root é o único na árvore quer não possuirá o endereço de um nó superior hierárquico porque é o nó inicial da árvore.

Nó interno

• Nó interno, todo o nó, abaixo do Root, que possuir ao menos um nó descendente hierárquico.

Nó externo (Leaf)

• Nó externo ou, comumente chamado, nó folha, o nó que não possuir descendente hierárquico, ou seja, onde a árvore se encere em uma das ramificações possíveis.

Ancestral:

• Nós hierarquicamente superiores, independente de qual nó seja. Só pode ser um nó interno, vez que precisa ter um descendente para que a partir do ponto de vista do descendente, este seja visto como ancestral.

Descendente:

• Nós hierarquicamente descendentes de outro, independente de qual nó seja. Pode ser um Nó interno ou um Nó folha, desde que descenda do ponto de vista do nó em questão.

Grau do nó (Degree):

• Quantidade nós Descendentes diretos de um determinado nó, em um contexto isolado do nó. Se tiver 3, então o grau do nó é 3

Grau da árvore (Degree of tree):

• Quantidade nós Descendentes diretos de um determinado nó, em um contexto mais amplo, comparando toda a árvore em busca do nó com maior quantidade de descendentes. Se tiver 3, então o grau do nó é 3

Profundidade (Depth):

• Quantidade de nós a partir da raiz até a folha mais distante.

Largura (Width):

• Quantidade de nós de um nível específico da árvore.

Largura da árvore (Width of tree):

• Número de nós do nível com maior quantidade de nós se comparado com os demais da árvore.

Floresta (Forest):

• Sub-árvores dentro da árvore principal.

Tamanho da árvore (Size of tree):

• Quantidade total de nós em uma árvore

Manipulação de uma árvore

A menos que se tenha o endereço da memória de um determinado nó, para manipular uma árvore e chegar um nó, é necessário percorrer por ela, podendo ser de modo Pré ordem, Em ordem, Pós ordem.

Se for começar a percorrer a arvore através, geralmente se faz da esquerda para a direita. Mas não é uma regra da estrutura de dados.

Pré ordem

Consome o nó antes dos filhos, percorrendo

Root → Left → Right.

        1ºA
        /  \
      2ºB  7ºC
      /  \    \
   3ºD  6ºE   8ºF
   /  \
4ºG  5ºH

Fluxo:

• 1- Consome o valor do Root (A) e vai para o Nó interno (B) consome seu valor
• 2- Do Nó interno (B) vai para o Nó interno (D) consome seu valor
• 3- Do Nó interno (D) vai para a Folha (G) consome seu valor
• 4- Da Folha (G) volta e visita o Nó Interno (D)
• 5- Do Nó Interno (D) vai para a Folha (H) consome seu valor
• 6- Da Folha (H) volta e visita o Nó Interno (D), como visitou todos Descendentes volta e visita o Nó Interno (B)
• 7- Do Nó Interno (B) vai para a Folha (E)consome seu valor
• 8- Da Folha (E) volta e visita o Nó Interno (B), como visitou todos Descendentes volta e visita o Root (A)
• 9- Do Root (A) vai para o Nó interno (C) consome seu valor
• 10- Do Nó interno (C) vai para a Folha (F) consome seu valor

Em ordem

Consome primeiro os valores das folhas e, em seguida, os nós internos ascendentes a elas, oposto ao fluxo da pré ordem

Left → Root → Right.

        6ºA
        /  \
      4ºB  7ºC
      /  \    \
   2ºD  5ºE   8ºF
   /  \
1ºG  3ºH

Fluxo:

• Do Root (A), visita nó interno (B), visita o nó interno (D) e vai para a folha (G)
• Consome o valor da Folha (G) e vai para o Nó interno (D) e consome seu valor
• Do Nó interno (D) vai para a Folha (H)e consome seu valor
• Da Folha (H) volta e visita o Nó Interno (D), como visitou todos Descendentes volta para o Nó Interno (B) consome seu valor
• Do Nó Interno (B) vai para a Folha (E) e consome seu valor
• Da Folha (E) volta e visita o Nó Interno (B), como visitou todos Descendentes volta e visita o Root (A)
• Do Root (A) vai para o Nó interno (C) e consome seu valor
• Do Nó interno (C) vai para a Folha (F) e consome seu valor
• Da Folha (F) volta e visita o Nó Interno (C), como visitou todos Descendentes volta para o Root (A) e consome seu valor

Pós ordem

Consome primeiro os valores de todas as folhas e, em seguida, o nó interno ascendentes a elas, diferente do fluxo da em ordem que consome o interno após consumir a primeira folha.

Left → Right → Root

        8ºA
        /  \
      1ºB  6ºC
      /  \    \
   2ºD  5ºE   7ºF
   /  \
3ºG  4ºH

Fluxo:

• 1- Visita o Nó interno (B) visita o Nó interno (D) e vai para a Folha (G)
• 2- Consome o valor da folha (G), visita o Nó interno (D), chega a Folha (H)
• 3- Consome o valor da folha (H), vai para o Nó interno (D) e consome seu valor
• 4- Visita o Nó interno (B), vai para a Folha (E) e consome seu valor
• 5- Da Folha (E), volta para o Nó Interno (B) e consome seu valor, em seguid, visita o Root (A), visita o Nó interno (C)
• 6- Do Nó interno (C) vai para a Folha (F) e consome seu valor
• 7- Da Folha (F) vai para o Nó interno (C) e consome seu valor
• 8- Da nó interno (C) vai o Root (A) e consome seu valor

         A
       /   \
      B     I
    / | \   
   C  F  G
  / \     \
 D   E     H

         A
       /   \
      B     I
    /  \   
   C    G
  / \    \
 D   E    H