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:
- Compruebe si el Node dado es nulo. Si es nulo, vuelve de la función.
- Compruebe si es un Node hoja. Si el Node es un Node hoja, imprima sus datos.
- 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>
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