数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究打印二叉树的所有素数层
在这个问题中，我们将打印给定二叉树的所有素数层。
我们将使用层序遍历技术遍历每个二叉树层，并检查特定层的所有节点是否包含素数。
问题陈述 - 我们给定一个二叉树，需要打印二叉树的所有素数层。如果二叉树的任何一层的所有节点都包含素数，则可以称该层为素数层。
示例
输入
23
/ \
12 13
/ \ \
17 19 23
/ \ \ /
3 7 19 11
输出
23 17 19 23 3 7 19 11
解释 - 我们打印了给定二叉树的所有素数层。
输入
5
/ \
7 2
/ \ / \
3 5 74 76
/ \
23 1 7
输出
5 7 2 23 17
解释 -第一、第二和第四层是素数层。
方法 1
在这种方法中，我们将遍历每一层。之后，我们将检查特定层的所有数字是否为素数。如果是，则打印该层。
算法
步骤 1- 定义树的结构。
步骤 2- 定义 createNewNode() 函数以使用给定值创建一个新节点。
步骤 3- 创建一个二叉树。
步骤 4- 执行 getSize() 函数以获取树中层数的数量。
步骤 4.1- 在 getSize() 函数中，如果头节点为 NULL，则返回 0。
步骤 4.2- 否则，对左节点和右节点进行递归调用，并将 1 加到其结果值中。
步骤 5- 创建一个长度等于树大小的队列，并将头节点插入队列中。
步骤 6- 执行 getPrimeLevels() 函数以打印素数层。
步骤 6.1- 在 getPrimeLevels() 函数中，执行 checkForPrime() 函数以检查根元素是否为素数。
步骤 6.1.1- 在 checkForPrime() 函数中，如果数字为 1，则返回 false。
步骤 6.1.2- 使用 for 循环进行迭代，直到 p*p <= num。在循环中，如果 num 可以被 p 整除，则返回 false。
步骤 6.1.3- 最后返回 false。
步骤 6.2- 现在，使用 while 循环遍历每一层。
步骤 6.3- 使用嵌套的 while 循环遍历特定层。
步骤 6.3.1- 在嵌套循环中，从队列中取出第一个节点。
步骤 6.3.2- 如果当前节点的左子节点存在，则将其插入队列中。
步骤 6.3.3- 如果当前节点的右节点存在，则将其插入队列中。
步骤 6.3.4- 将 'ind' 值增加 1。
步骤 6.4- 执行 checkForPrimeLevel() 函数以检查当前层是否为素数层。
步骤 6.4.1- 在 checkForPrimeLKevel() 函数中，我们检查每个数字是否为素数。如果是，则返回 true。否则，返回 false。
步骤 6.5- 如果 checkForPrimeLevel() 函数返回 true，则执行 showLevel() 函数以显示当前层。其中，我们遍历包含当前层节点的队列并打印其值。
示例
#include <bits/stdc++.h>
using namespace std;
// Tree structure
struct TreeNode {
int val;
struct TreeNode *left, *right;
};
// Function for creating a new node
TreeNode *createNewNode(int val) {
TreeNode *tmp = new TreeNode;
tmp->val = val;
tmp->left = NULL;
tmp->right = NULL;
return (tmp);
}
// Check if a number is Prime or not
bool checkForPrime(int num) {
if (num == 1)
return false;
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
return false;
}
}
return true;
}
// Print the particular level of a given
void showLevel(struct TreeNode *que[], int ind, int sz) {
// Traverse the queue and print all values
for (int p = ind; p < sz; p++) {
cout << que[p]->val << " ";
}
cout << endl;
}
// Check if a particular level is Prime
bool checkForPrimeLevel(struct TreeNode *que[], int ind, int sz) {
for (int p = ind; p < sz; p++) {
if (!checkForPrime(que[ind++]->val)) {
return false;
}
}
// When all node values are Prime
return true;
}
void getPrimeLevels(struct TreeNode *head, struct TreeNode *que[], int ind, int sz) {
// Print head node
if (checkForPrime(que[ind]->val)) {
cout << que[ind]->val << endl;
}
while (ind < sz) {
int temp_size = sz;
while (ind < temp_size) {
struct TreeNode *temp = que[ind];
// Insert left child to queue
if (temp->left != NULL)
que[sz++] = temp->left;
// Insert right child to queue
if (temp->right != NULL)
que[sz++] = temp->right;
ind++;
}
// Check for prime level
if (checkForPrimeLevel(que, ind, sz - 1)) {
showLevel(que, ind, sz);
}
}
}
// Get the size of the tree
int getSize(struct TreeNode *head) {
// Base condition
if (head == NULL)
return 0;
return 1 + getSize(head->left) + getSize(head->right);
}
void ShowAllPrimeLevels(struct TreeNode *head) {
int treeSize = getSize(head);
struct TreeNode *queue[treeSize];
// Insert head node in queue
queue[0] = head;
// FInd prime levels
getPrimeLevels(head, queue, 0, 1);
}
int main() {
TreeNode *head = createNewNode(5);
head->left = createNewNode(7);
head->right = createNewNode(2);
head->left->left = createNewNode(3);
head->left->right = createNewNode(5);
head->right->left = createNewNode(76);
head->right->right = createNewNode(54);
head->left->left->left = createNewNode(23);
head->left->left->right = createNewNode(17);
ShowAllPrimeLevels(head);
return 0;
}
输出
5 7 2 23 17
时间复杂度 - O(n * sqrt(max_val))，其中 O(n) 用于遍历二叉树，O(sqrt(max_val)) 用于检查数字是否为素数。
空间复杂度 - O(M)，其中 M 是特定层中节点的最大数量。
在这里，我们使用层序遍历打印了所有素数层。程序员可以打印非素数层。他们可以在特定层的所有节点都包含非素数时打印该层。
87 次浏览
