原文:
给定一个二叉树，任务是打印该树的所有质数。
如果二叉树的任何一级的所有节点都是素数，则称该级为素数级。
示例:
input:
1
/ \
15 13
/ / \
11 7 29
\ /
2 3
output: 11 7 29
2 3
explanation:
third and fourth levels are prime levels.
input:
7
/ \
23 41
/ \ \
31 16 3
/ \ \ /
2 5 17 11
/
23
output: 7
23 41
2 5 17 11
23
explanation:
first, second, fourth and
fifth levels are prime levels.
方法:为了检查一个级别是否是 prime 级别，
- 我们首先需要对二叉树进行
- 这里一个用于存储树的级别，同时进行级别顺序遍历。
- 然后对于每一级，级。
下面是上述方法的实现:
c
// c program for printing a prime
// levels of binary tree
#include
using namespace std;
// a tree node
struct node {
int key;
struct node *left, *right;
};
// utility function to create a new node
node* newnode(int key)
{
node* temp = new node;
temp->key = key;
temp->left = temp->right = null;
return (temp);
}
// function to check whether node
// value is prime or not
bool isprime(int n)
{
if (n == 1)
return false;
// iterate from 2 to sqrt(n)
for (int i = 2; i * i <= n; i ) {
// if it has a factor
if (n % i == 0) {
return false;
}
}
return true;
}
// function to print a prime level
void printlevel(struct node* queue[],
int index, int size)
{
for (int i = index; i < size; i ) {
cout << queue[i]->key << " ";
}
cout << endl;
}
// function to check whether given level is
// prime level or not
bool islevelprime(struct node* queue[],
int index, int size)
{
for (int i = index; i < size; i ) {
// check value of node is
// pprime or not
if (!isprime(queue[index ]->key)) {
return false;
}
}
// return true if for loop
// iiterate completely
return true;
}
// utility function to get prime
// level of a given binary tree
void findprimelevels(struct node* node,
struct node* queue[],
int index, int size)
{
// print root node value, if prime
if (isprime(queue[index]->key)) {
cout << queue[index]->key << endl;
}
// run while loop
while (index < size) {
int curr_size = size;
// run inner while loop
while (index < curr_size) {
struct node* temp = queue[index];
// push left child in a queue
if (temp->left != null)
queue[size ] = temp->left;
// push right child in a queue
if (temp->right != null)
queue[size ] = temp->right;
// increment index
index ;
}
// if condition to check, level is
// prime or not
if (islevelprime(
queue, index, size - 1)) {
// function call to print
// prime level
printlevel(queue, index, size);
}
}
}
// function to find total no of nodes
// in a given binary tree
int findsize(struct node* node)
{
// base condition
if (node == null)
return 0;
return 1
findsize(node->left)
findsize(node->right);
}
// function to find prime levels
// in a given binary tree
void printprimelevels(struct node* node)
{
int t_size = findsize(node);
// create queue
struct node* queue[t_size];
// push root node in a queue
queue[0] = node;
// function call
findprimelevels(node, queue, 0, 1);
}
// driver code
int main()
{
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// create binary tree as shown
node* root = newnode(10);
root->left = newnode(13);
root->right = newnode(11);
root->right->left = newnode(19);
root->right->right = newnode(23);
root->right->left->left = newnode(21);
root->right->left->right = newnode(29);
root->right->right->left = newnode(43);
root->right->right->right = newnode(15);
root->right->right->right->left = newnode(7);
// print prime levels
printprimelevels(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for the above approach
public class main
{
// a tree node
static class node {
public int key;
public node left, right;
public node(int key)
{
this.key = key;
left = right = null;
}
}
// utility function to create a new node
static node newnode(int key)
{
node temp = new node(key);
return temp;
}
// function to check whether node
// value is prime or not
static boolean isprime(int n)
{
if (n == 1)
return false;
// iterate from 2 to sqrt(n)
for(int i = 2; i * i <= n; i )
{
// if it has a factor
if (n % i == 0)
{
return false;
}
}
return true;
}
// function to print a prime level
static void printlevel(node[] queue, int index, int size)
{
for(int i = index; i < size; i )
{
system.out.print(queue[i].key " ");
}
system.out.println();
}
// function to check whether given level is
// prime level or not
static boolean islevelprime(node[] queue, int index, int size)
{
for(int i = index; i < size; i )
{
// check value of node is
// pprime or not
if (!isprime(queue[index ].key))
{
return false;
}
}
// return true if for loop
// iiterate completely
return true;
}
// utility function to get prime
// level of a given binary tree
static void findprimelevels(node node, node[] queue, int index, int size)
{
// print root node value, if prime
if (isprime(queue[index].key))
{
system.out.println(queue[index].key);
}
// run while loop
while (index < size)
{
int curr_size = size;
// run inner while loop
while (index < curr_size)
{
node temp = queue[index];
// push left child in a queue
if (temp.left != null)
queue[size ] = temp.left;
// push right child in a queue
if (temp.right != null)
queue[size ] = temp.right;
// increment index
index ;
}
// if condition to check, level is
// prime or not
if (islevelprime(queue, index, size - 1))
{
// function call to print
// prime level
printlevel(queue, index, size);
}
}
}
// function to find total no of nodes
// in a given binary tree
static int findsize(node node)
{
// base condition
if (node == null)
return 0;
return 1 findsize(node.left)
findsize(node.right);
}
// function to find prime levels
// in a given binary tree
static void printprimelevels(node node)
{
int t_size = findsize(node);
// create queue
node[] queue = new node[t_size];
for(int i = 0; i < t_size; i )
{
queue[i] = new node(0);
}
// push root node in a queue
queue[0] = node;
// function call
findprimelevels(node, queue, 0, 1);
}
public static void main(string[] args) {
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// create binary tree as shown
node root = newnode(10);
root.left = newnode(13);
root.right = newnode(11);
root.right.left = newnode(19);
root.right.right = newnode(23);
root.right.left.left = newnode(21);
root.right.left.right = newnode(29);
root.right.right.left = newnode(43);
root.right.right.right = newnode(15);
root.right.right.right.left = newnode(7);
// print prime levels
printprimelevels(root);
}
}
// this code is contributed by suresh07.
python 3
# python3 program for printing a prime
# levels of binary tree
# a tree node
class node:
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to create a
# new node
def newnode(key):
temp = node(key);
return temp;
# function to check whether
# node value is prime or not
def isprime(n):
if (n == 1):
return false;
i = 2
# iterate from 2
# to sqrt(n)
while(i * i <= n):
# if it has a factor
if (n % i == 0):
return false;
i = 1
return true;
# function to print a
# prime level
def printlevel(queue,
index, size):
for i in range(index, size):
print(queue[i].key, end = ' ')
print()
# function to check whether
# given level is prime level
# or not
def islevelprime(queue,
index, size):
for i in range(index, size):
# check value of node is
# pprime or not
if (not isprime(queue[index].key)):
index = 1
return false;
# return true if for loop
# iiterate completely
return true;
# utility function to get prime
# level of a given binary tree
def findprimelevels(node, queue,
index, size):
# print root node value, if prime
if (isprime(queue[index].key)):
print(queue[index].key)
# run while loop
while (index < size):
curr_size = size;
# run inner while loop
while (index < curr_size):
temp = queue[index];
# push left child in a queue
if (temp.left != none):
queue[size] = temp.left;
size =1
# push right child in a queue
if (temp.right != none):
queue[size] = temp.right;
size =1
# increment index
index =1;
# if condition to check, level
# is prime or not
if (islevelprime(queue, index,
size - 1)):
# function call to print
# prime level
printlevel(queue,
index, size);
# function to find total no
# of nodes in a given binary
# tree
def findsize(node):
# base condition
if (node == none):
return 0;
return (1 findsize(node.left)
findsize(node.right));
# function to find prime levels
# in a given binary tree
def printprimelevels(node):
t_size = findsize(node);
# create queue
queue=[0 for i in range(t_size)]
# push root node in a queue
queue[0] = node;
# function call
findprimelevels(node, queue,
0, 1);
# driver code
if __name__ == "__main__":
''' 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 '''
# create binary tree as shown
root = newnode(10);
root.left = newnode(13);
root.right = newnode(11);
root.right.left = newnode(19);
root.right.right = newnode(23);
root.right.left.left = newnode(21);
root.right.left.right = newnode(29);
root.right.right.left = newnode(43);
root.right.right.right = newnode(15);
root.right.right.right.left = newnode(7);
# print prime levels
printprimelevels(root);
# this code is contributed by rutvik_56
c
// c# program for printing a prime
// levels of binary tree
using system;
using system.collections.generic;
class gfg {
// a tree node
class node {
public int key;
public node left, right;
public node(int key)
{
this.key = key;
left = right = null;
}
}
// utility function to create a new node
static node newnode(int key)
{
node temp = new node(key);
return temp;
}
// function to check whether node
// value is prime or not
static bool isprime(int n)
{
if (n == 1)
return false;
// iterate from 2 to sqrt(n)
for(int i = 2; i * i <= n; i )
{
// if it has a factor
if (n % i == 0)
{
return false;
}
}
return true;
}
// function to print a prime level
static void printlevel(node[] queue, int index, int size)
{
for(int i = index; i < size; i )
{
console.write(queue[i].key " ");
}
console.writeline();
}
// function to check whether given level is
// prime level or not
static bool islevelprime(node[] queue, int index, int size)
{
for(int i = index; i < size; i )
{
// check value of node is
// pprime or not
if (!isprime(queue[index ].key))
{
return false;
}
}
// return true if for loop
// iiterate completely
return true;
}
// utility function to get prime
// level of a given binary tree
static void findprimelevels(node node, node[] queue, int index, int size)
{
// print root node value, if prime
if (isprime(queue[index].key))
{
console.writeline(queue[index].key);
}
// run while loop
while (index < size)
{
int curr_size = size;
// run inner while loop
while (index < curr_size)
{
node temp = queue[index];
// push left child in a queue
if (temp.left != null)
queue[size ] = temp.left;
// push right child in a queue
if (temp.right != null)
queue[size ] = temp.right;
// increment index
index ;
}
// if condition to check, level is
// prime or not
if (islevelprime(queue, index, size - 1))
{
// function call to print
// prime level
printlevel(queue, index, size);
}
}
}
// function to find total no of nodes
// in a given binary tree
static int findsize(node node)
{
// base condition
if (node == null)
return 0;
return 1 findsize(node.left)
findsize(node.right);
}
// function to find prime levels
// in a given binary tree
static void printprimelevels(node node)
{
int t_size = findsize(node);
// create queue
node[] queue = new node[t_size];
for(int i = 0; i < t_size; i )
{
queue[i] = new node(0);
}
// push root node in a queue
queue[0] = node;
// function call
findprimelevels(node, queue, 0, 1);
}
static void main() {
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// create binary tree as shown
node root = newnode(10);
root.left = newnode(13);
root.right = newnode(11);
root.right.left = newnode(19);
root.right.right = newnode(23);
root.right.left.left = newnode(21);
root.right.left.right = newnode(29);
root.right.right.left = newnode(43);
root.right.right.right = newnode(15);
root.right.right.right.left = newnode(7);
// print prime levels
printprimelevels(root);
}
}
// this code is contributed by mukesh07.
java 描述语言
output:
13 11
19 23
7
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
