Como imprimir todos os nós folha de uma árvore binária da esquerda para a direita em JavaScript?

A representação visual dos conceitos discutidos é mostrada na figura abaixo:

Este guia explica o processo de impressão de todos os nós folha de uma árvore binária, cobrindo as seções mencionadas abaixo:

• Como identificar nós de folha?
• Como imprimir todos os nós folha de uma árvore binária da esquerda para a direita em JavaScript?
• Dica bônus: imprimindo nós de folha de uma árvore binária da direita para a esquerda
• Conclusão

Como identificar nós de folha?

O ' folha ”nós são aqueles que não possuem nós filhos ou, para ser mais específico, que possuem o“ altura ' de ' 0 ”. Se o nó tiver um “ altura ' Maior que ' 0 ”então esse nó pode ser o nó interno ou o nó raiz. O ' folha ”Os nós geralmente são retrocedidos para identificar a fonte original de onde esse nó é gerado. É usado principalmente em algoritmos de pesquisa ou localização de erros para encontrar a causa de um erro ou problema.

Como imprimir todos os nós folha de uma árvore binária da esquerda para a direita em JavaScript?

Existem duas abordagens “ recursivo ' e ' iterativo ”para selecionar todos os nós folha disponíveis na árvore binária fornecida no desejado“ esquerda ' para ' certo ”direção. A implementação prática dessas abordagens é demonstrada nas seções abaixo:

• Imprimir todos os nós folha de uma árvore binária da esquerda para a direita recursivamente
• Imprimir todos os nós folha de uma árvore binária usando a abordagem iterativa

Método 1: imprimir todos os nós folha de uma árvore binária da esquerda para a direita recursivamente

A abordagem recursiva seleciona todos os nós em um algoritmo de pesquisa em profundidade maneira que primeiro atravessa todos os nós do lado esquerdo, depois o nó do meio e os nós do lado direito no final. Esta operação é realizada recursivamente para cada nó e quando não há mais passagem pelo “ folha ”Os nós são identificados. Para entender melhor esse conceito, visite o trecho de código abaixo:

A explicação do bloco de código acima é apresentada abaixo:

• Primeiro, crie uma classe chamada “ nó ”, que cria um novo nó e define seu valor como “ 0 ”. O anexo “ esquerda ' e ' certo ”nós laterais são definidos como“ nulo ” por padrão usando o construtor de classe.
• A seguir, defina um “ displayLeafNodes() ”Função que aceita um único parâmetro de“ rootNode ”. Este valor paramétrico é considerado o nó atualmente selecionado de uma árvore binária.
• Dentro da função, o “ se ”A instrução é utilizada para verificar se o“ rootNode ”é nulo ou não. No caso de ' nulo ”A execução adicional foi interrompida para esse nó. No outro caso, o rootNode “ esquerda ' e ' certo ”nós laterais são verificados para“ nulo ”. Se ambos forem nulos, o valor desse “ nó ”é impresso.
• Se o “ esquerda ' ou ' certo ”o nó não é “nulo”, então passe esse lado do nó para o “ displayLeafNodes() ”Função para a operação recursiva.
• Defina uma nova função chamada “ provNode() ”que aceita o único parâmetro de“ valor ”. Dentro da função crie uma nova instância do “ Nó ”classe chamada“ tempNode ”. Atribua o paramétrico “ valor ”como o valor da propriedade de classe“ contente ”E defina o“ esquerda ' e ' certo ”nós laterais para“ nulo ' por padrão.
• Finalmente, crie um objeto chamado “ rootNode ' para o ' provNode() ”Função e passe o valor do nó como este parâmetro de função. Crie os nós do lado esquerdo e direito adicionando o “ esquerda ' e ' certo ”palavras-chave com “rootNode” e atribua-lhes valor usando a mesma função “ provNode() ”.
• O ' esquerda ”Significa a posição esquerda do nó raiz e o“ esquerda.esquerda ”posição significa esquerda da esquerda, a mesma abordagem é aplicada no caso de“ certo ' e ' certo ”
• Após definir a árvore, passe o “rootNode” como argumento para o “ displayLeadNodes() ”Função para selecionar e imprimir todos os nós folha da árvore criada.

A saída gerada após a compilação confirma que o nó folha da árvore fornecida foi recuperado e impresso no console:

Método 2: imprimir todos os nós folha de uma árvore binária usando a abordagem iterativa

O ' iterativo ”A abordagem é a abordagem mais eficiente, ela usa o conceito de“ empurrar ' e ' pop ”Para selecionar o“ folha ”nós. Os pontos-chave ou funcionamento desta abordagem são declarados abaixo:

A explicação do código acima está escrita abaixo:

• Primeiro, crie um “ Nó ”classe que recebe um único parâmetro“ valor ”que é definido como o valor do nó recém-criado e os lados esquerdo e direito são definidos como nulos. Assim como feito no exemplo acima.
• Em seguida, crie uma função “ displayLeafNodes() ”que aceita um único parâmetro de“ rootNode ”. Este “rootNode” é considerado a árvore binária e seu vazio é primeiro verificado.
• Se o nó não estiver vazio, então uma lista vazia chamada “ lista ”é criado e o“ rootNode ”O parâmetro é inserido nele usando o“ empurrar() ”Método.
• Então o ' enquanto() ”é utilizado, que é executado até o comprimento de um“ lista ”. Dentro do loop, o elemento que reside na parte inferior de uma árvore ou “ lista ”é removido usando o“ pop() ”Método.
• Agora, a existência do “ esquerda ' e ' certo ”Os lados de “rootNode” são verificados e, se ambos os lados não existirem, significa que não há nó filho. Em seguida, esse nó é exibido na tela e identificado como um nó folha.
• Se houver um nó no lado esquerdo ou direito significa que ele tem filhos. Então isso ' esquerda ' e ' certo ”Nó é empurrado para dentro do“ lista ”Para posterior operação de localização do nó folha.
• No final, crie uma árvore binária personalizada passando os valores dos nós como parâmetros para “ Nó ”construtor de classe. Após a criação, passe a árvore “rootNode” como argumento para o “ displayLeafNodes() ”função.

A saída gerada após a compilação mostra que os nós folha da árvore fornecida são impressos:

Dica bônus: imprimindo nós de folha de uma árvore binária da direita para a esquerda

Para recuperar todos os nós folha que não possuem nós filhos no “ certo ' para ' esquerda ”, a abordagem recursiva é a mais recomendada devido à sua facilidade. Por exemplo, a mesma árvore discutida nas seções acima será usada para recuperar o nó folha, mas no “ certo ' para o ' esquerda ”Direção, conforme mostrado abaixo:

O código indicado acima funciona assim:

• Primeiro, a classe “ Nó ”é criado que usa o construtor padrão para adicionar um novo nó na árvore apenas o link feito nos exemplos acima.
• A seguir, o “ displayLeadNodes() ”É criada uma função que aceita um único parâmetro de“ rootNode ”. Este parâmetro é verificado para o “ nulo ”Condição por meio do“ se ' declaração.
• Se o nó fornecido não for verdadeiro, então é “ esquerda ' e ' certo ”nós laterais são verificados para“ nulo ' doença. Se ambos forem nulos, o nó será identificado como “ folha ”Nó e impresso na página da web.
• Depois disso, passe o “ certo ' e ' esquerda ”nós do“ rootNode ' para o ' displayLeafNodes() ”função.
• Aloque a posição de cada nó criando as instâncias usando o “ novo ” e a palavra-chave “ Nó() ”Construtor e especificando a posição como o parâmetro do construtor.
• O ' esquerda ”Significa a posição esquerda do nó raiz e o“ esquerda.esquerda ”Posição significa esquerda ou esquerda. A mesma abordagem é aplicada no caso de “ certo ' e ' certo ”.
• Por fim, passe o “ rootNode ”como um argumento para o“ displayLeafNode() ”função.

A saída gerada mostra que os nós folha são impressos na direção da direita para a esquerda.

Trata-se de imprimir todos os nós folhas de uma árvore binária em qualquer direção desejada.

Conclusão

Para imprimir todos os nós folha de uma árvore binária, crie uma classe aleatória que crie e atribua valores aos nós da árvore. A seguir, crie uma função aleatória que aceite um único nó da árvore em uma hierarquia de cima para baixo. Esta função contém vários “ se ”Condições que verificam se o“ nó ”Não está vazio e não possui nós no“ esquerda ' e ' certo ”Direção, então esse nó é considerado como um“ folha ”Nó e é exibido no console. Este guia explicou o procedimento de impressão de todos os nós folha de uma árvore binária da esquerda para a direita ou da direita para a esquerda.