Imprimir todos los Nodes internos de un árbol binario

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: 
    1. El Node solo tiene un hijo izquierdo.
    2. El Node solo tiene un hijo derecho.
    3. El Node tiene un hijo izquierdo y derecho.
    4. 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

Deja una respuesta

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