資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
