Metodo parentAninhados

O método parentAninhados tem a função de representar graficamente uma arvore binária através de parênteses como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos parentes aninhados.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi na tela o “(” mais o valor do nó.
10: Chama recursivamente o método passando o valor do nó filho da esquerda.
11: Chama recursivamente o método passando o valor do nó filho da direita.
12: Imprimi na tela o “)”.

Metodo arvoreHierarquicaII

O método arvoreHierarquicaII tem a função de representar graficamente uma arvore binária através de uma arvore de hereditária como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos arvore hierárquica II.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi a variável space que guarda os espaços em branco dados para a identação da árvore e o valor do nó atual.
10: Acrescenta espaços em branco à variável space.
11: Chama recursivamente o método passando o valor do nó filho da esquerda e os espaços em branco guardados em space.
12: Chama recursivamente o método passando o valor do nó filho da direita e os espaços em branco guardados em space.

Metodo arvoreHierarquicaI

O método arvoreHierarquicaI tem a função de representar graficamente uma arvore binária através de uma arvore de hereditária como mostra a imagem a seguir:

A diferença da imagem para como a arvore será representada no programa é que a árvore estará deitada, ou seja, a raiz da arvore ficará na extrema esquerda e a partir daí a arvore vai crescendo para a direita, ao invés de ser feito de cima para baixo.

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos arvore hierárquica I.
7: Verifica se o nó raiz passado é ou não nulo.
8: Acrescenta espaços em branco à variável space.
9: Chama recursivamente o método passando o valor do nó filho da direita e os espaços em branco guardados em space.
10: Imprimi na tela os espaços em branco que contem na variável space e o valor do nó.
11: Chama recursivamente o método passando o valor do nó filho da esquerda e os espaços em branco guardados em space.
14: No momento em que sai da condição da linha 7, a variável space recebe o caracter de quebra de linha.

Metodo isEstrBinary

O método isEstrBinary consiste em realizar uma verificação para saber se uma árvore é estritamente binária.
Uma árvore estritamente binária é nomeada dessa forma quando os nós têm ou os dois nós filhos ou não tem nenhum.


1 – 4: Método que faz interface entre o usuário e a programação para saber se uma árvore é ou não estritamente binária.
7: Verifica se o nó raiz passado é ou não nulo.
10: Condição que verifica se os nós filhos da esquerda e direita do nó raiz são nulos.
11: Se a verificação acima for verdadeira então o método retorna true.
12: Uma segunda verificação é realizada para saber se os nós filhos da esquerda e direita do nó raiz são diferente de nulos.
14: Condição for verdadeira então verifica se o lado da esquerda e o lado da direita de toda a árvore são estritamente binários.
15: Se a condição for verdadeira então é retornado true
17: Senão false será retornado20: Se a condição da linha 12 for falsa então é retornado false.

Metodo isFull

Uma árvore binária cheia é aquela em que a raiz e todos os nós internos tem dois nós filhos, portanto o objetivo do método isFull é verificar se uma árvore dada pelo usuário é ou não cheia.

O método que da linha 1 até a 10 é o método que faz a interface com o usuário e o código que verifica se a árvore é ou não cheia.
Nesse método de interface há uma diferença dos demais já apresentados:
Nele verificamos a altura dos dois lados da árvore utilizando o método já apresentado height. Se um lado for maior que o outro então não será necessário fazer o restante da verificação e o próprio método de interface retorna false para o usuário.
Se os dois lados da árvore tiverem o mesmo tamanho então chama-se a função de verificação da árvore.

13: Verifica se o nó raiz passado é ou não nulo
15: Se o nó filho direito e esquerdo forem iguais a nulo então retorna o valor true.
16: Se a condição da linha 15 for verdadeira então o valor true é retornado ao método de interface
17: Senão, é feita uma condição que verifica se a árvore do lado direito e do lado esquerdo são verdadeiros.
20: Caso a condição da linha 17 for verdadeira, então o valor true é retornado.
22: Caso contrario é retornado o valor false.
O valor true é retornado quando os nós filhos esquerdo e direito são nulos porque sabemos que o método chegou até o final da árvore. Se no meio do caminho fosse visto que a árvore não é cheia então o valor retornado é false, pois o método não permite que o restante da árvore seja verificada.

Metodo IsDegenerate

Diz-se que uma árvore é degenerada quando ela tem somente um filho. Um bom exemplo de árvore degenerada que temos são as tão famosas pilhas e listas encadeadas que nos colocaram medo por algum tempo.


123 - 126: Método que faz interface entre o usuário e a “real” programação do método.
282: Verifica se a raiz da árvore não é nula.
284: Verifica se o nó em questão tem dois filhos. Se tiver então a árvore não é degenerada.
285: Se a árvore contiver dois filhos então, nesse momento, a função retorna falso.
286: Senão, verifica se existe nó filho da esquerda.
287: Se tiver filho na esquerda então, chama-se a própria função passando como parâmetro o filho da esquerda.
288: Senão, verifica se existe nó filho da direita.
287: Se tiver filho na direita então, chama-se a própria função passando como parâmetro o filho da direita.
288: Quando nenhuma das condições acima satisfazer, então quer dizer que chegou ao final da árvore, e se até o final da árvore o sistema ainda não retornou falso quer dizer que árvore é degenerada e então retorna true.

Metodo Nos Folhas

Os nós folhas de uma árvore são todos os que não possuem nenhum nó filho.
Para descobrirmos qual são os nós filhos, será necessário certificar que o nó não tem nenhum nó filho.

110 – 113: Método que faz interface entre o usuário e a “real” programação do método.
246: Verifica se a raiz da árvore não é nula.
247: Verifica se o nó não tem filho.
248: Se a condição da linha 237 for verdadeira, então o valor do nó é impresso na tela.
250: Faz a chamada do próprio método passando como parâmetro os nós da esquerda.
251: Faz a chamada do próprio método passando como parâmetro os nós da direita.

Fazendo essas duas chamadas recursivas das linhas 240 e 241, consegue-se percorrer toda a árvore para fazer as devidas verificações e imprimir os nós internos dela.

Nós Internos

Os nós internos de uma árvore são todos os nós de uma árvore que tem ao menos um outro nó filho.
Para descobrirmos qual são os nós internos, será necessário verificar se o nó tem ao menos um filho.

105 – 108: Método que faz interface entre o usuário e a “real” programação do método.
236: Verifica se a raiz da árvore não é nula.
237: Verifica se o nó tem ao menos um filho.
238: Se a condição da linha 237 for verdadeira, então o valor do nó é impresso na tela.
240: Faz a chamada do próprio método passando como parâmetro os nós da esquerda.
241: Faz a chamada do próprio método passando como parâmetro os nós da direita.

Fazendo essas duas chamadas recursivas das linhas 240 e 241, consegue-se percorrer toda a árvore para fazer as devidas verificações e imprimir os nós internos dela.

Metodo Height

Este Metodo retorna a altura da arvore.

Para isso, ele usa o metodo MAX.

O Metodo height usa o metodo MAX que tem como finalidade comparar os dois lados da arvore e retornar o maior deles

MAX

374 - Testa se o lado a é maior que o lado b

------ Se Sim

375- Retorna a

------ Se Não

377- Retorna b

Fazendo o teste, o programa guarda sempre o valor do maior lado. Terminada essa função (recursiva) ele soma 1 que é o nó raiz da arvore.

height

110-113 - Metodos que fazem interfaces entre o usuário e o método que contém a programação da funcionalidade

293 - Testa se a raiz é diferente de nulo
------- Se Sim
294 - Soma 1 ao resiltado de MAX
------- Se Não
296 - Retorna 0 e sai da função

Metodo Size

Este metodo retorna a quantidade de valores armazenados na arvore, para isso, ele percorre por toda a arvore usando recursividade.

105-108 - Interface do metodo

277 - Testa se a raiz é diferente de nulo

------ Se Sim

278 - Ele usa recursividade para ir somando os nós das arvores. Ele soma 1 a cada vez q a resposta do teste é positiva, fazendo isso até que o teste dê negativo.

-------Se não

279 - Retorna 0 e sai do programa, mostrando o numero de nós achado.

Maior e Menor

Estes metodos buscam e mostram o maior e o menor nó da arvore, através de recursividade.

Para achar o maior valor, ele busca o nó que está mais a direita, e para achar o menor, o que está mais a esquerda.

95 - 103 - Interfaces dos metodos

244 - Inicio do metodo: maior
246 - Testa se o nó atual é nulo
248 - Testa se o nó direito do atual é nulo
------Se Sim
249 - Retorna o valor do nó
------Se Não
251 - Refaz o teste através de recursividade

259 - Inicio do metodo: menor
261 - Testa se o nó atual é nulo
263 - Testa se o nó esquerdo do atual é nulo
------Se Sim
264 - Retorna o valor do nó
------Se Não
266 - Refaz o teste através de recursividade

MostraPre - MostraPos - MostraCentro

Estes metodos servem para imprimir os nós da arvore. Eles percorrem a arvore, usando recursividade.
Cada um, segue uma ordem, sendo as seguintes

Mostra Pré

Raiz - Sub Arvore Esquerda - Sub Arvore Direita

Mostra Pós

Sub Arvore Esquerda - Sub Arvore Direita - Raiz

Mostra Centro

Sub Arvore Esquerda - Raiz - Sub Arvore Direita

------------------

80 - 93 - Interface dos Metodos
203 / 213 / 223 - Testa se o nó atual é diferente de nulo
205 / 217 / 226 - Imprime os valores do ó atual
206 / 215 / 225 - Percorre as raizes esquerdas (modo recursivo)
207 / 216 / 227 - Percorre as raizes direitas (modo recursivo)

Metodo Push

O Método push insere novos nós a arvore

75 - 78 - Interface do metodo

166 - Testa se o nó atual é nulo
168 - Inicia um novo nó
169 - Atribui o valor que você quer ao novo nó
170 - Atribui valor nulo ao lado esquerdo
171 - Atribui valor nulo ao lado direito
173 - Testa se o valor a ser inserido é maior que o nó atual
- Se Sim...
175 - Atribui o valor a ser inserido a variável aux
177 - Atribui o valor ao nó direito do atual
- Se Não....
181 - Atribui o valor a ser inserido a variável aux
183 - Atribui o valor ao nó esquerdo do atual

Class btree

27 class btree
28 {
29    private:
30       ptrno raiz;
31
32       void push (ptrno &r, int v);
33       void mostraPre(ptrno r);
34       void mostraPos(ptrno r);
35       void mostraCentro(ptrno r);
36       int maior(ptrno r);
37       int menor(ptrno r);
38       int size(ptrno r);
39       int height(ptrno r);
40       void nosInternos(ptrno r);
41       void nosFolhas(ptrno r);
42       bool isDegenerate(ptrno r);
43       bool isComplete(ptrno r);
44       bool isFull(ptrno r);
45       int MAX(int a, int b);
46       bool isEstrBinary(ptrno r);
47       void parentAninhados(ptrno r);
48
49    public:
50       btree()
51       {
52          raiz = NULL;
53       }
54       void push(int v);
55       void mostraPre();
56       void mostraPos();
57       void mostraCentro();
58       int maior();
59       int menor();
60       int size();
61       int height();
62       void nosInternos();
63       void nosFolhas();
64       bool isDegenerate();
65       bool isComplete();
66       bool isFull();
67       bool isEstrBinary();
68       void parentAninhados();
69 };

---------------------------

A Classe btree contém todos os metodos usados nos programas e quais parâmetros ele usa

29 - Private (Área Privada) - Todos os métodos, variaveis e objetos que são criados nessa área só podem ser acessados, ou ter seus valores alterados dentro da propria classe
30 - Declaração do objeto "raiz" tipo ptrno
32-47 - Protótipo dos métodos privados
49 - Public (Área Pública) - Todos os métodos, variaveis e objetos que são criados nessa área podem ser acessados, ou ter seus valores alterados de qualquer outra classe que faça referência a essa
54-68 - Protótipo dos métodos que fazem a interface entre o usuário e a classe

Class Node

A Classe Node manipula os nós das arvores

ptrno - ponteiro para o objeto node

setValor - Atribui valores ao nó atual

setEsq - Atribui valores ao lado Esquerdo

setDir - Atribui valores ao lado Direito

getValor - Ponteiro que retorna o valor do nó atual

getEsq - Ponteiro que retorna o lado esquerdo do nó

getDir- Ponteiro que retorna o lado direito do nó