Imprima todos los Nodes de hoja de un árbol binario de izquierda a derecha

Dado un árbol binario, necesitamos escribir un programa para imprimir todos los Nodes hoja del árbol binario dado de izquierda a derecha. Es decir, los Nodes deben imprimirse en el orden en que aparecen de izquierda a derecha en el árbol dado. 

Por ejemplo, 
 

Para el árbol binario anterior, la salida será como se muestra a continuación: 

4 6 7 9 10

La idea de hacer esto es similar al algoritmo DFS . A continuación se muestra un algoritmo paso a paso para hacer esto: 

  1. Compruebe si el Node dado es nulo. Si es nulo, vuelve de la función.
  2. Compruebe si es un Node hoja. Si el Node es un Node hoja, imprima sus datos.
  3. Si en el paso anterior, el Node no es un Node hoja, compruebe si existen los elementos secundarios izquierdo y derecho del Node. En caso afirmativo, llame recursivamente a la función para el hijo izquierdo y derecho del Node.

A continuación se muestra la implementación del enfoque anterior. 

C++

/* C++ program to print leaf nodes from left
   to right */
#include <iostream>
using namespace std;
  
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// function to print leaf
// nodes from left to right
void printLeafNodes(Node *root)
{
    // if node is null, return
    if (!root)
        return;
     
    // if node is leaf node, print its data   
    if (!root->left && !root->right)
    {
        cout << root->data << " ";
        return;
    }
 
    // if left child exists, check for leaf
    // recursively
    if (root->left)
       printLeafNodes(root->left);
         
    // if right child exists, check for leaf
    // recursively
    if (root->right)
       printLeafNodes(root->right);
}
 
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
  
// Driver program to test above functions
int main()
{
    // Let us create binary tree shown in
    // above diagram
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(8);
    root->right->left->left = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->left = newNode(9);
    root->right->right->right = newNode(10);
  
    // print leaf nodes of the given tree
    printLeafNodes(root);
     
    return 0;
}

Java

// Java program to print leaf nodes
// from left to right
import java.util.*;
   
class GFG{
      
// A Binary Tree Node
static class Node
{
    public int data;
    public Node left, right;
};
  
// Function to print leaf
// nodes from left to right
static void printLeafNodes(Node root)
{
      
    // If node is null, return
    if (root == null)
        return;
      
    // If node is leaf node, print its data    
    if (root.left == null &&
        root.right == null)
    {
        System.out.print(root.data + " ");
        return;
    }
      
    // If left child exists, check for leaf
    // recursively
    if (root.left != null)
        printLeafNodes(root.left);
          
    // If right child exists, check for leaf
    // recursively
    if (root.right != null)
        printLeafNodes(root.right);
}
  
// Utility function to create a new tree node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
  
// Driver code
public static void main(String []args)
{
      
    // Let us create binary tree shown in
    // above diagram
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.right.left = newNode(5);
    root.right.right = newNode(8);
    root.right.left.left = newNode(6);
    root.right.left.right = newNode(7);
    root.right.right.left = newNode(9);
    root.right.right.right = newNode(10);
  
    // Print leaf nodes of the given tree
    printLeafNodes(root);
}
}
 
// This code is contributed by pratham76

Python3

# Python3 program to print
# leaf nodes from left to right
 
# Binary tree node
class Node:
   
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to print leaf
# nodes from left to right
def printLeafNodes(root: Node) -> None:
 
    # If node is null, return
    if (not root):
        return
 
    # If node is leaf node,
    # print its data
    if (not root.left and
        not root.right):
        print(root.data,
              end = " ")
        return
 
    # If left child exists,
    # check for leaf recursively
    if root.left:
        printLeafNodes(root.left)
 
    # If right child exists,
    # check for leaf recursively
    if root.right:
        printLeafNodes(root.right)
 
# Driver Code
if __name__ == "__main__":
 
    # Let us create binary tree shown in
    # above diagram
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(8)
    root.right.left.left = Node(6)
    root.right.left.right = Node(7)
    root.right.right.left = Node(9)
    root.right.right.right = Node(10)
 
    # print leaf nodes of the given tree
    printLeafNodes(root)
 
# This code is contributed by sanjeev2552

C#

// C# program to print leaf nodes
// from left to right
using System;
  
class GFG{
     
// A Binary Tree Node
class Node
{
    public int data;
    public Node left, right;
};
 
// Function to print leaf
// nodes from left to right
static void printLeafNodes(Node root)
{
     
    // If node is null, return
    if (root == null)
        return;
     
    // If node is leaf node, print its data    
    if (root.left == null &&
        root.right == null)
    {
        Console.Write(root.data + " ");
        return;
    }
     
    // If left child exists, check for leaf
    // recursively
    if (root.left != null)
        printLeafNodes(root.left);
         
    // If right child exists, check for leaf
    // recursively
    if (root.right != null)
        printLeafNodes(root.right);
}
 
// Utility function to create a new tree node
static Node newNode(int data)
{
    Node temp = new Node();
    temp.data = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Driver code
public static void Main()
{
     
    // Let us create binary tree shown in
    // above diagram
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.right.left = newNode(5);
    root.right.right = newNode(8);
    root.right.left.left = newNode(6);
    root.right.left.right = newNode(7);
    root.right.right.left = newNode(9);
    root.right.right.right = newNode(10);
 
    // Print leaf nodes of the given tree
    printLeafNodes(root);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program to print leaf nodes
// from left to right
 
// A Binary Tree Node
class Node
{
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Function to print leaf
// nodes from left to right
function printLeafNodes(root)
{
     
    // If node is null, return
    if (root == null)
        return;
     
    // If node is leaf node, print its data    
    if (root.left == null &&
        root.right == null)
    {
        document.write(root.data + " ");
        return;
    }
     
    // If left child exists, check for leaf
    // recursively
    if (root.left != null)
        printLeafNodes(root.left);
         
    // If right child exists, check for leaf
    // recursively
    if (root.right != null)
        printLeafNodes(root.right);
}
 
// Utility function to create a new tree node
function newNode(data)
{
    var temp = new Node();
    temp.data = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Driver code
 
// Let us create binary tree shown in
// above diagram
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.right.left = newNode(5);
root.right.right = newNode(8);
root.right.left.left = newNode(6);
root.right.left.right = newNode(7);
root.right.right.left = newNode(9);
root.right.right.right = newNode(10);
 
// Print leaf nodes of the given tree
printLeafNodes(root);
 
// This code is contributed by rrrtnx
 
</script>
Producción

4 6 7 9 10 

Complejidad de tiempo: O( n ) , donde n es el número de Nodes en el árbol binario. 

Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *