Dado un árbol binario y un Node, imprime todos los primos del Node dado. Tenga en cuenta que los hermanos no deben imprimirse.
Ejemplos:
Input : root of below tree
1
/ \
2 3
/ \ / \
4 5 6 7
and pointer to a node say 5.
Output : 6, 7
Tenga en cuenta que es el mismo problema que se da en Imprimir primos de un Node dado en Binary Tree , que consta de dos recorridos recursivamente. En esta publicación, se analiza un enfoque transversal de un solo nivel.
La idea es realizar un recorrido por orden de niveles del árbol, ya que los primos y hermanos de un Node se pueden encontrar en su recorrido por orden de niveles. Ejecute el recorrido hasta que no se encuentre el nivel que contiene el Node y, si lo encuentra, imprima el nivel dado.
¿Cómo imprimir los Nodes primos en lugar de hermanos y cómo poner los Nodes de ese nivel en la cola? Durante el orden de nivel, cuando para el Node padre, si padre->izquierda == Node_a_buscar, o padre->derecha == Node_a_buscar, entonces los hijos de este padre no deben ser empujados a la cola (ya que uno es el Node y el otro será su hermano). Empuje los Nodes restantes al mismo nivel en la cola y luego salga del bucle. La cola actual tendrá los Nodes en el siguiente nivel (el nivel del Node que se busca, excepto el Node y su hermano). Ahora, imprima la cola.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to print cousins of a node
#include <iostream>
#include <queue>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
Node *left, *right;
};
// A utility function to create a new Binary
// Tree Node
Node* newNode(int item)
{
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
// function to print cousins of the node
void printCousins(Node* root, Node* node_to_find)
{
// if the given node is the root itself,
// then no nodes would be printed
if (root == node_to_find) {
cout << "Cousin Nodes : None" << endl;
return;
}
queue<Node*> q;
bool found = false;
int size_;
Node* p;
q.push(root);
// the following loop runs until found is
// not true, or q is not empty.
// if found has become true => we have found
// the level in which the node is present
// and the present queue will contain all the
// cousins of that node
while (!q.empty() && !found) {
size_ = q.size();
while (size_) {
p = q.front();
q.pop();
// if current node's left or right child
// is the same as the node to find,
// then make found = true, and don't push
// any of them into the queue, as
// we don't have to print the siblings
if ((p->left == node_to_find ||
p->right == node_to_find)) {
found = true;
}
else {
if (p->left)
q.push(p->left);
if (p->right)
q.push(p->right);
}
size_--;
}
}
// if found == true then the queue will contain the
// cousins of the given node
if (found) {
cout << "Cousin Nodes : ";
size_ = q.size();
// size_ will be 0 when the node was at the
// level just below the root node.
if (size_ == 0)
cout << "None";
for (int i = 0; i < size_; i++) {
p = q.front();
q.pop();
cout << p->data << " ";
}
}
else {
cout << "Node not found";
}
cout << endl;
return;
}
// Driver Program to test above function
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(15);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
Node* x = newNode(43);
printCousins(root, x);
printCousins(root, root);
printCousins(root, root->right);
printCousins(root, root->left);
printCousins(root, root->left->right);
return 0;
}
Java
// Java program to print
// cousins of a node
import java.io.*;
import java.util.*;
import java.lang.*;
// A Binary Tree Node
class Node
{
int data;
Node left, right;
Node(int key)
{
data = key;
left = right = null;
}
}
class GFG
{
// function to print
// cousins of the node
static void printCousins(Node root,
Node node_to_find)
{
// if the given node
// is the root itself,
// then no nodes would
// be printed
if (root == node_to_find)
{
System.out.print("Cousin Nodes :" +
" None" + "\n");
return;
}
Queue<Node> q = new LinkedList<Node>();
boolean found = false;
int size_ = 0;
Node p = null;
q.add(root);
// the following loop runs
// until found is not true,
// or q is not empty. if
// found has become true => we
// have found the level in
// which the node is present
// and the present queue will
// contain all the cousins of
// that node
while (q.isEmpty() == false &&
found == false)
{
size_ = q.size();
while (size_ -- > 0)
{
p = q.peek();
q.remove();
// if current node's left
// or right child is the
// same as the node to find,
// then make found = true,
// and don't push any of them
// into the queue, as we don't
// have to print the siblings
if ((p.left == node_to_find ||
p.right == node_to_find))
{
found = true;
}
else
{
if (p.left != null)
q.add(p.left);
if (p.right!= null)
q.add(p.right);
}
}
}
// if found == true then the
// queue will contain the
// cousins of the given node
if (found == true)
{
System.out.print("Cousin Nodes : ");
size_ = q.size();
// size_ will be 0 when
// the node was at the
// level just below the
// root node.
if (size_ == 0)
System.out.print("None");
for (int i = 0; i < size_; i++)
{
p = q.peek();
q.poll();
System.out.print(p.data + " ");
}
}
else
{
System.out.print("Node not found");
}
System.out.println("");
return;
}
// 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.left.right = new Node(5);
root.left.right.right = new Node(15);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.right = new Node(8);
Node x = new Node(43);
printCousins(root, x);
printCousins(root, root);
printCousins(root, root.right);
printCousins(root, root.left);
printCousins(root, root.left.right);
}
}
Python3
# Python3 program to print cousins of a node
# A Binary Tree Node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A utility function to create a new Binary
# Tree Node
def newNode(item):
temp = Node(item)
return temp
# function to print cousins of the node
def printCousins(root, node_to_find):
# if the given node is the root itself,
# then no nodes would be printed
if (root == node_to_find):
print("Cousin Nodes : None")
return;
q = []
found = False;
size_ = 0
p = None
q.append(root);
# the following loop runs until found is
# not true, or q is not empty.
# if found has become true => we have found
# the level in which the node is present
# and the present queue will contain all the
# cousins of that node
while (len(q) != 0 and not found):
size_ = len(q)
while (size_ != 0):
p = q[0]
q.pop(0);
# if current node's left or right child
# is the same as the node to find,
# then make found = true, and don't append
# any of them into the queue, as
# we don't have to print the siblings
if ((p.left == node_to_find or p.right == node_to_find)):
found = True;
else:
if (p.left):
q.append(p.left);
if (p.right):
q.append(p.right);
size_-=1
# if found == true then the queue will contain the
# cousins of the given node
if (found):
print("Cousin Nodes : ", end='')
size_ = len(q)
# size_ will be 0 when the node was at the
# level just below the root node.
if (size_ == 0):
print("None", end='')
for i in range(0, size_):
p = q[0]
q.pop(0);
print(p.data, end=' ')
else:
print("Node not found", end='')
print()
return;
# Driver Program to test above function
if __name__=='__main__':
root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.left.right.right = newNode(15);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.left.right = newNode(8);
x = newNode(43);
printCousins(root, x);
printCousins(root, root);
printCousins(root, root.right);
printCousins(root, root.left);
printCousins(root, root.left.right);
# This code is contributed by rutvik_56
C#
// C# program to print
// cousins of a node
using System;
using System.Collections.Generic;
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
public Node(int key)
{
data = key;
left = right = null;
}
}
public class GFG
{
// function to print
// cousins of the node
static void printCousins(Node root,
Node node_to_find)
{
// if the given node
// is the root itself,
// then no nodes would
// be printed
if (root == node_to_find)
{
Console.Write("Cousin Nodes :" +
" None" + "\n");
return;
}
Queue<Node> q = new Queue<Node>();
bool found = false;
int size_ = 0;
Node p = null;
q.Enqueue(root);
// the following loop runs
// until found is not true,
// or q is not empty. if
// found has become true => we
// have found the level in
// which the node is present
// and the present queue will
// contain all the cousins of
// that node
while (q.Count!=0 &&
found == false)
{
size_ = q.Count;
while (size_ -- > 0)
{
p = q.Peek();
q.Dequeue();
// if current node's left
// or right child is the
// same as the node to find,
// then make found = true,
// and don't push any of them
// into the queue, as we don't
// have to print the siblings
if ((p.left == node_to_find ||
p.right == node_to_find))
{
found = true;
}
else
{
if (p.left != null)
q.Enqueue(p.left);
if (p.right!= null)
q.Enqueue(p.right);
}
}
}
// if found == true then the
// queue will contain the
// cousins of the given node
if (found == true)
{
Console.Write("Cousin Nodes : ");
size_ = q.Count;
// size_ will be 0 when
// the node was at the
// level just below the
// root node.
if (size_ == 0)
Console.Write("None");
for (int i = 0; i < size_; i++)
{
p = q.Peek();
q.Dequeue();
Console.Write(p.data + " ");
}
}
else
{
Console.Write("Node not found");
}
Console.WriteLine("");
return;
}
// 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.left.right = new Node(5);
root.left.right.right = new Node(15);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.right = new Node(8);
Node x = new Node(43);
printCousins(root, x);
printCousins(root, root);
printCousins(root, root.right);
printCousins(root, root.left);
printCousins(root, root.left.right);
}
}
// This code is contributed Rajput-Ji
Javascript
<script>
// Javascript program to print
// cousins of a node
// A Binary Tree Node
class Node
{
constructor(key)
{
this.data = key;
this.left = null;
this.right = null;
}
}
// Function to print
// cousins of the node
function printCousins(root, node_to_find)
{
// If the given node
// is the root itself,
// then no nodes would
// be printed
if (root == node_to_find)
{
document.write("Cousin Nodes :" +
" None" + "<br>");
return;
}
var q = [];
var found = false;
var size_ = 0;
var p = null;
q.push(root);
// The following loop runs
// until found is not true,
// or q is not empty. if
// found has become true => we
// have found the level in
// which the node is present
// and the present queue will
// contain all the cousins of
// that node
while (q.length != 0 &&
found == false)
{
size_ = q.length;
while (size_ -- > 0)
{
p = q[0];
q.shift();
// If current node's left
// or right child is the
// same as the node to find,
// then make found = true,
// and don't push any of them
// into the queue, as we don't
// have to print the siblings
if ((p.left == node_to_find ||
p.right == node_to_find))
{
found = true;
}
else
{
if (p.left != null)
q.push(p.left);
if (p.right!= null)
q.push(p.right);
}
}
}
// If found == true then the
// queue will contain the
// cousins of the given node
if (found == true)
{
document.write("Cousin Nodes : ");
size_ = q.length;
// size_ will be 0 when
// the node was at the
// level just below the
// root node.
if (size_ == 0)
document.write("None");
for(var i = 0; i < size_; i++)
{
p = q[0];
q.shift();
document.write(p.data + " ");
}
}
else
{
document.write("Node not found");
}
document.write("<br>");
return;
}
// Driver code
var root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.right.right = new Node(15);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.right = new Node(8);
var x = new Node(43);
printCousins(root, x);
printCousins(root, root);
printCousins(root, root.right);
printCousins(root, root.left);
printCousins(root, root.left.right);
// This code is contributed by famously
</script>
Producción:
Node not found Cousin Nodes : None Cousin Nodes : None Cousin Nodes : None Cousin Nodes : 6 7
Complejidad de tiempo: este es un recorrido de orden de un solo nivel, por lo tanto, complejidad de tiempo = O (n) y espacio auxiliar = O (n) (ver esto ).
Publicación traducida automáticamente
Artículo escrito por nth_underdog y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA