Dado un árbol binario, la tarea es imprimir todos los Nodes internos en un árbol.
Un Node interno es un Node que lleva al menos un hijo o, en otras palabras, un Node interno no es un Node hoja. Aquí tenemos la intención de imprimir todos esos Nodes internos en orden de nivel. Considere el siguiente árbol binario:
Aporte:
Salida: 15 10 20
La forma de resolver esto implica un BFS del árbol. El algoritmo es como sigue:
- Haga un recorrido de orden de nivel empujando los Nodes en la cola uno por uno.
- Extraiga los elementos de la cola uno por uno y realice un seguimiento de los siguientes casos:
- El Node solo tiene un hijo izquierdo.
- El Node solo tiene un hijo derecho.
- El Node tiene un hijo izquierdo y derecho.
- El Node no tiene hijos en absoluto.
- Excepto por el caso 4, imprima los datos en el Node para los otros 3 casos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all internal // nodes in tree #include <bits/stdc++.h> using namespace std; // A node in the Binary tree struct Node { int data; Node *left, *right; Node(int data) { left = right = NULL; this->data = data; } }; // Function to print all internal nodes // in level order from left to right void printInternalNodes(Node* root) { // Using a queue for a level order traversal queue<Node*> q; q.push(root); while (!q.empty()) { // Check and pop the element in // the front of the queue Node* curr = q.front(); q.pop(); // The variable flag keeps track of // whether a node is an internal node bool isInternal = 0; // The node has a left child if (curr->left) { isInternal = 1; q.push(curr->left); } // The node has a right child if (curr->right) { isInternal = 1; q.push(curr->right); } // In case the node has either a left // or right child or both print the data if (isInternal) cout << curr->data << " "; } } // Driver program to build a sample tree int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->right->right = new Node(10); root->right->right->left = new Node(7); root->right->left->left = new Node(8); root->right->left->right = new Node(9); // A call to the function printInternalNodes(root); return 0; }
Java
// Java program to print all internal // nodes in tree import java.util.*; class GfG { // A node in the Binary tree static class Node { int data; Node left, right; Node(int data) { left = right = null; this.data = data; } } // Function to print all internal nodes // in level order from left to right static void printInternalNodes(Node root) { // Using a queue for a level order traversal Queue<Node> q = new LinkedList<Node>(); q.add(root); while (!q.isEmpty()) { // Check and pop the element in // the front of the queue Node curr = q.peek(); q.remove(); // The variable flag keeps track of // whether a node is an internal node boolean isInternal = false; // The node has a left child if (curr.left != null) { isInternal = true; q.add(curr.left); } // The node has a right child if (curr.right != null) { isInternal = true; q.add(curr.right); } // In case the node has either a left // or right child or both print the data if (isInternal == true) System.out.print(curr.data + " "); } } // Driver code public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.right.right = new Node(10); root.right.right.left = new Node(7); root.right.left.left = new Node(8); root.right.left.right = new Node(9); // A call to the function printInternalNodes(root); } } // This code is contributed by // Prerna Saini.
Python3
# Python3 program to print all internal # nodes in tree # A node in the Binary tree class new_Node: # Constructor to create a new_Node def __init__(self, data): self.data = data self.left = None self.right = None # Function to print all internal nodes # in level order from left to right def printInternalNodes(root): # Using a queue for a level order traversal q = [] q.append(root) while (len(q)): # Check and pop the element in # the front of the queue curr = q[0] q.pop(0) # The variable flag keeps track of # whether a node is an internal node isInternal = 0 # The node has a left child if (curr.left): isInternal = 1 q.append(curr.left) # The node has a right child if (curr.right): isInternal = 1 q.append(curr.right) # In case the node has either a left # or right child or both print the data if (isInternal): print(curr.data, end = " ") # Driver Code root = new_Node(1) root.left = new_Node(2) root.right = new_Node(3) root.left.left = new_Node(4) root.right.left = new_Node(5) root.right.right = new_Node(6) root.right.right.right = new_Node(10) root.right.right.left = new_Node(7) root.right.left.left = new_Node(8) root.right.left.right = new_Node(9) # A call to the function printInternalNodes(root) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to print all internal // nodes in tree using System; using System.Collections.Generic; class GFG { // A node in the Binary tree public class Node { public int data; public Node left, right; public Node(int data) { left = right = null; this.data = data; } } // Function to print all internal nodes // in level order from left to right static void printInternalNodes(Node root) { // Using a queue for a level order traversal Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { // Check and pop the element in // the front of the queue Node curr = q.Peek(); q.Dequeue(); // The variable flag keeps track of // whether a node is an internal node Boolean isInternal = false; // The node has a left child if (curr.left != null) { isInternal = true; q.Enqueue(curr.left); } // The node has a right child if (curr.right != null) { isInternal = true; q.Enqueue(curr.right); } // In case the node has either a left // or right child or both print the data if (isInternal == true) Console.Write(curr.data + " "); } } // Driver code public static void Main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.right.right = new Node(10); root.right.right.left = new Node(7); root.right.left.left = new Node(8); root.right.left.right = new Node(9); // A call to the function printInternalNodes(root); } } // This code contributed by Rajput-Ji
Javascript
<script> // JavaScript program to print all internal nodes in tree // A node in the Binary tree class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to print all internal nodes // in level order from left to right function printInternalNodes(root) { // Using a queue for a level order traversal let q = []; q.push(root); while (q.length > 0) { // Check and pop the element in // the front of the queue let curr = q[0]; q.shift(); // The variable flag keeps track of // whether a node is an internal node let isInternal = false; // The node has a left child if (curr.left != null) { isInternal = true; q.push(curr.left); } // The node has a right child if (curr.right != null) { isInternal = true; q.push(curr.right); } // In case the node has either a left // or right child or both print the data if (isInternal == true) document.write(curr.data + " "); } } let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.right.right = new Node(10); root.right.right.left = new Node(7); root.right.left.left = new Node(8); root.right.left.right = new Node(9); // A call to the function printInternalNodes(root); </script>
Producción:
1 2 3 5 6
Publicación traducida automáticamente
Artículo escrito por code_freak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA