Travessal de pré -encomenda de árvores binárias em Java
Esta é na verdade uma árvore binária. Uma árvore binária é uma árvore onde cada nó tem no máximo dois nós de crianças. Se um nó tiver apenas um nó filho, esse nó deve ser feito o nó esquerdo. Se tiver os dois filhos, então há um nó esquerdo e um nó direito.
Vocabulário de árvore
A explicação da travessia de árvores é feita usando vocabulário de árvore.
Nó raiz: Todo nó em uma árvore tem um pai, exceto o nó raiz.
Nós da folha: Os nós finais são nós de folha. Um nó de folha não tem filho.
Chave: Este é o valor de um nó. Pode ser um valor de tipo de dados primitivo ou um caractere. Também pode ser um operador, e.g., + ot - .
Níveis: Uma árvore é organizada em níveis, com o nó raiz no primeiro nível. Os nós podem ser imaginados em níveis horizontais. A árvore acima tem quatro níveis.
Nó pai: O nó raiz é o único nó que não tem um pai. Qualquer outro nó tem um nó pai.
Nós irmãos: Os filhos de qualquer nó em particular são nós irmãos.
Caminho: Um caminho é uma série de nós e seus ramos únicos.
Nó ancestral: Todos os nós mais altos conectados a uma criança, incluindo o pai e o nó raiz, são nós ancestrais.
Nó descendente: Todos os nós inferiores, conectados a um nó específico, até as folhas conectadas, são nós descendentes. O nó em questão não faz parte dos nós descendentes. O nó em questão não precisa ser o nó raiz.
Subárvore: Um nó mais todos os seus descendentes, até as folhas relacionadas, formam uma subárvore. O nó inicial está incluído e não precisa ser a raiz; Caso contrário, seria toda a árvore.
Grau: O nó de uma árvore binária pode ter um ou dois filhos. Se um nó tem um filho, seu diploma é considerado um. Se houver dois filhos, diz -se que seu diploma é dois.
Este artigo explica como atravessar uma árvore binária de maneira pré-encomenda, usando a língua java.
Conteúdo do artigo
- Modelo Traversal
- A abordagem de travessia ilustrada
- Aulas de Java
- O método principal ()
- Conclusão
Modelo Traversal
Ordens
O menor sub-árvore típico de uma árvore binária consiste em um nó pai e dois nós de filhos. Os nós das crianças são irmãos compostos pelo nó da criança esquerda e do nó da criança direita. Um nó infantil certo pode estar ausente.
Pedido antecipado
O nó pai é visitado primeiro com este pedido, depois o nó esquerdo e depois o nó direito. Se o nó esquerdo tiver sua própria subárvore, todos os nós da subárvore serão visitados primeiro antes que o nó direito seja visitado. Se o nó certo tiver sua própria subárvore, toda a sua subárvore será visitada por último. Ao visitar uma subárvore, o esquema de pré-encomenda do pai-esquerdo é seguido para cada triângulo de três nós. Se um nó tem apenas um filho, o que significa que não há triângulo real, o único filho deve ser considerado o nó esquerdo enquanto o nó direito está ausente.
Postrome
O nó esquerdo é visitado primeiro com este pedido, depois o nó direito e depois o nó pai. Se o nó esquerdo tiver sua própria subárvore, todos os nós da subárvore serão visitados primeiro antes que o nó direito seja visitado. Se o nó certo tiver sua própria subárvore, toda a sua subárvore será visitada em segundo lugar antes de o pai ser visitado. Ao visitar uma subárvore, o esquema de pós-ordem de parente esquerdo-direita é seguido para cada triângulo de três nós.
Em ordem
O nó esquerdo é visitado primeiro com este pedido, depois o nó pai e depois o nó direito. Se o nó esquerdo tiver sua própria subárvore, todos os nós da subárvore serão visitados primeiro antes que o nó pai seja visitado. Se o nó certo tiver sua própria subárvore, toda a sua subárvore será visitada por último. Ao visitar uma subárvore, o esquema em ordem do lado esquerdo é seguido para cada triângulo de três nós.
Neste artigo, apenas o esquema de pré -encomenda é ilustrado.
Recursão ou iteração
O esquema de pré -encomenda pode ser implementado usando recursão ou iteração. Neste artigo, a única recursão é ilustrada.
A abordagem de travessia ilustrada
Neste artigo, o esquema de pré-encomenda e a recursão são usados. O diagrama acima será usado. O diagrama foi re-exibido aqui para facilitar a referência:
Nesta seção, este diagrama é usado para mostrar a sequência de valores (letras) que são exibidos (acessados), usando o esquema de pré -encomenda e a recursão. As letras A, B, C, etc., são os valores (chaves) dos diferentes nós.
O acesso de pré -encomenda à árvore começa a partir da raiz. Então A é o acesso primeiro. A tem dois filhos: B (à esquerda) e C (direita). A pré-encomenda é pai-esquerda-direita. Então B é acessado a seguir. Se B nunca tivesse filhos, então C teria sido acessado a seguir. Como B tem filhos: D (esquerda) e E (direita), seu filho esquerdo deve ser acessado em seguida. Lembre-se de que a pré-encomenda é a direita-mãe-esquerda. Após B, o pai foi acessado, seu filho esquerdo, D, deve ser acessado em seguida, de acordo com o pai-leftcild-rightchild.
O triângulo para o nó pai, B, é BDE. Neste triângulo, o nó pai, seguido pelo nó esquerdo da criança, acaba de ser acessado. Acessar todos os nós do triângulo deve ser concluído primeiro. Portanto, o próximo nó a ser acessado é o filho certo do nó B, que é e.
Agora, o triângulo BDE é uma subárvore, que é liderada pelo nó B. Neste ponto, o nó B e seu triângulo foram completamente acessados. O nó B é o filho esquerdo do nó a. O acesso do nó B e sua subárvore acabaram de ser concluídos. Seguindo os pais-esquerda-direita, depois que o filho esquerdo, o nó B foi acessado, o filho direito do pai A, C, deve ser acessado a seguir.
O triângulo que C leva é CFG. C é o pai, F é o filho esquerdo e G é o filho certo. Assim, assim que C foi acessado, F deve ser acessado de acordo com a regra dos pais à esquerda-esquerda. F também tem um filho, h. Assim, assim que F foi acessado, seu filho esquerdo, H, deve ser acessado pela regra dos pais-esquerda-direita.
Depois disso, F e sua subárvore teriam sido acessados completamente. Nesse ponto, não haveria acesso a f. F é o filho esquerdo de C, que tem um filho certo, g. Depois que o filho esquerdo, F foi completamente acessado, a criança certa, G, deve ser acessada pela regra dos pais-esquerda-direita.
E assim a sequência de acesso é: abdecfhg.
Aulas de Java
A árvore é re-exibida aqui para facilitar a referência:
Nó
carta) do nó. Também deve ter duas outras propriedades nomeadas para a esquerda e direita. A propriedade esquerda será atribuída a um nó filho se o nó tiver um filho esquerdo. A propriedade certa será atribuída o nó "a" se o nó tiver "a" criança certa.
A classe do nó precisa de um construtor que crie o objeto do nó e atribua um valor à chave. O código da classe é:
classe nó
chave de char;
Nó para a esquerda, direita;
nó público (valor de char)
chave = valor;
esquerda = direita = nulo;
Quando um nó é criado, ele não tem nenhum filho. É por isso que as propriedades esquerda e direita são atribuídas nulas. No método main (), se um nó específico tiver um filho esquerdo, a criança será criada e designada para a propriedade esquerda do nó em particular. Se um nó específico tiver uma criança certa, a criança será criada e designada para a propriedade certa do nó em particular.
A classe de árvores
O código para a classe da árvore é:
classe BinaryTree
Raiz do nó;
Binarytree ()
raiz = nulo;
A classe de árvores indica a raiz. Possui uma propriedade chamada root, que é para o nó raiz. Tem um construtor sem parâmetros. Este construtor atribui nulo à raiz. Quando uma árvore é criada, ela não tem nó, e é por isso que a raiz da propriedade é nula. O primeiro nó criado será o nó raiz e será atribuído a esta propriedade, raiz. A partir daí, a árvore crescerá no método principal () (veja abaixo).
A classe BinaryTree possui os métodos, pré -encomendar () e main () ver abaixo.
O método de pré -encomenda
Este é o núcleo do programa, embora o método principal () também seja importante. O método de pré-encomenda implementa a regra dos pais-leftchild-rightchild. Esta é uma função recursiva, cujo código é:
PREVELA DE VOID (NODE)
if (nó == nulo)
retornar;
// Acesse o nó pai
Sistema.fora.Imprimir (nó.chave + "->");
// Acesse a criança esquerda
pré -encomenda (nó.esquerda);
// Acesse a criança certa
pré -encomenda (nó.certo);
No final da travessia da árvore, nenhum nó vai atravessar, então o valor de qualquer nó será nulo. Isso explica a primeira declaração na função de pré -encomenda. A segunda declaração imprime a chave do nó atual. A terceira declaração lembra a mesma função de pré -encomenda com o nó da criança esquerda. A próxima e última declaração lembra a função de pré -encomenda com o nó da criança certo. Dessa forma, toda a árvore é atravessada.
Ao exibir a sequência, a-> b-> d, depois de B foi acessado, “pré-encomenda (nó.à direita) ”é chamado para o nó C, mas reservado. Depois que D foi acessado, “Prede -se (nó.à direita) ”é chamado para o nó e. A chamada para o nó C, que foi reservada, é executada depois disso. Esta explicação se aplica ao ramo direito de toda a árvore.
E assim a sequência de saída deve ser: a-> b-> d-> e-> c-> f-> h-> g .
O método principal ()
O método principal constrói a árvore atribuindo novos nós com suas chaves para a propriedade esquerda ou direita do nó dos pais. Primeiro, uma árvore vazia é criada. No final do método Main (), o método de pré -encomenda é chamado uma vez. Como é uma função recursiva, continuará se chamando até que toda a árvore seja atravessada. O código é:
public static void main (string [] args)
// Crie objeto de árvore sem nenhum nó
BinaryTree Tree = New BinaryTree ();
// Crie nós para a árvore
árvore.root = new Node ('A');
árvore.raiz.esquerda = novo nó ('b');
árvore.raiz.direita = novo nó ('c');
árvore.raiz.esquerda.esquerda = novo nó ('d');
árvore.raiz.esquerda.direita = novo nó ('e');
árvore.raiz.certo.esquerda = novo nó ('f');
árvore.raiz.certo.direita = novo nó ('g');
árvore.raiz.certo.esquerda.esquerda = novo nó ('h');
// Travessal de árvore de pré -encomenda
Sistema.fora.println ("Travessal de pré -encomenda");
árvore.pré -encomenda (árvore.raiz);
Sistema.fora.println ();
Todos os códigos acima podem ser montados em um programa para testar.
A saída é:
A-> b-> d-> e-> c-> f-> h-> g->
O último -> pode ser ignorado.
Conclusão
A travessia de pré -encomenda de árvores binárias em Java, que usa recursão, tem duas classes. Tem a classe de nó e a classe binária. A classe de nó tem uma propriedade para a chave. Ele também possui duas propriedades de nós para o nó da criança esquerda e o nó da criança direita. A classe BinaryTree possui dois métodos: o método de pré -encomenda () e o método principal (). O método de pré-encomenda () implementa o esquema dos pais-leftchild-rightchild. O método Main () constrói a árvore atribuindo novos nós com as chaves como filhos esquerda e direita para os nós dos pais.
O problema com o algoritmo recursivo para a pré -encomenda é que, se a árvore for muito grande, a memória pode ficar curta. Para resolver esse problema, use o algoritmo iterativo - veja mais tarde.