题目描述
二叉搜索树(BST)递归定义为具有以下属性的二叉树:
节点的左子树只包含键值小于或等于节点键值的节点。
节点的右子树只包含键值大于节点键值的节点。
左子树和右子树都必须是二叉搜索树。
在初始为空的二叉搜索树中插入一个数字序列。计算树的最低2层中的节点总数。
输入描述：
每个输入包含一个测试用例。对于每种情况，第一行给出一个正整数N(N
≤
≤ 1000)，这是输入序列的大小。然后在下一行给出[-1000 1000]中的N个整数，把这些数插入到一个初始为空的二叉搜索树中。
输出描述：
对于每种情况，在一行中打印结果树的最低2层的节点数，格式为
n1 + n2 = n
其中n1为最低层的节点数，n2为上一层的节点数，n为和。
输入数据 1
9
25 30 42 16 20 20 35 -5 28
输出数据 1
2 + 4 = 6
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
if(n==2||n==3)
{
cout<<"是素数";
}
else if(n%6!=1&&n%6!=5)
{
cout<<"不是素数";
}
else
{
for(int i=2;i*i<=n;i++)
{
if(!(n%i))
{
cout<<"不是素数" ;
return 0;
}
}
cout<<"是素数";
}
}
首先，我们需要建立一个二叉搜索树，并将给定的数字序列依次插入树中。在插入过程中，我们需要确定树的层级，以便计算最低2层的节点总数。
在建立二叉搜索树的过程中，我们可以使用递归的方法。首先，我们需要定义一个节点结构，包含值和左右子节点。然后，我们可以定义一个函数，用于插入节点到树中。
# 定义节点结构
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 插入节点的函数
def insert(root, value):
if root is None:
root = Node(value)
elif value < root.value:
if root.left is None:
root.left = Node(value)
else:
insert(root.left, value)
else:
if root.right is None:
root.right = Node(value)
else:
insert(root.right, value)
接下来，我们可以根据给定的数字序列插入节点到树中，并同时记录插入的层级。在插入过程中，我们可以使用一个队列来保存每个节点和对应的层级。每次插入一个节点时，我们将当前层级加1，并将左右子节点和对应的层级入队。
# 构建二叉搜索树，并记录最低两层的节点数
def build_bst(nums):
root = None
level = 0
queue = [(root, level)] # 初始化队列，保存节点和层级
for num in nums:
node, level = queue.pop(0) # 出队队首节点和层级
if node is None:
root = Node(num)
queue.append((root, level)) # 入队根节点和层级
else:
insert(node, num)
queue.append((node.left, level + 1)) # 入队左子节点和层级
queue.append((node.right, level + 1)) # 入队右子节点和层级
return root, level
最后，我们可以计算最低两层的节点总数，并返回结果。我们可以利用递归的方法计算每个层级的节点数量，然后将最低两层的节点数量相加。
# 计算最低两层的节点总数
def calculate_nodes(root, level):
if root is None:
return 0
if level == 1 or level == 2:
return 1
return calculate_nodes(root.left, level - 1) + calculate_nodes(root.right, level - 1)
# 主函数
def main():
n = int(input()) # 获取输入序列的大小
nums = list(map(int, input().split())) # 获取输入序列
root, level = build_bst(nums) # 构建二叉搜索树
n1 = calculate_nodes(root, level) # 计算最低层的节点数
n2 = calculate_nodes(root, level-1) # 计算上一层的节点数
total_nodes = n1 + n2 # 两层的节点总数
print(f"{n1} + {n2} = {total_nodes}")
if __name__ == "__main__":
main()
请注意，以上代码为Python代码，可以在Python环境中运行。如果您使用的是其他编程语言，您可以根据相应语言的语法和特性对代码进行修改和适配。
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int key;
Node* left;
Node* right;
};
Node* createNode(int key) {
Node* newNode = new Node();
if (newNode) {
newNode->key = key;
newNode->left = newNode->right = nullptr;
}
return newNode;
}
Node* insertNode(Node* root, int key) {
if (root == nullptr) {
return createNode(key);
}
if (key < root->key) {
root->left = insertNode(root->left, key);
} else if (key > root->key) {
root->right = insertNode(root->right, key);
}
return root;
}
int countNodes(Node* root) {
if (root == nullptr) {
return 0;
}
int count = 0;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
count += size;
while (size--) {
Node* node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
return count;
}
int main() {
int N;
cin >> N;
Node* root = nullptr;
for (int i = 0; i < N; i++) {
int key;
cin >> key;
root = insertNode(root, key);
}
int level1 = countNodes(root->left);
int level2 = countNodes(root->right);
int total = level1 + level2;
cout << level1 << " + " << level2 << " = " << total << endl;
return 0;
}
代码说明：
createNode 函数用于创建一个新的节点，并将键值初始化为给定的值。insertNode 函数使用递归来插入节点到二叉搜索树中。如果树为空，则创建一个新节点。如果给定的键值小于当前节点的键值，则递归地插入到左子树中。如果键值大于当前节点的键值，则递归地插入到右子树中。countNodes 函数用于计算二叉树最低两层的节点总数。它使用广度优先搜索（BFS）算法遍历二叉树，并在遍历过程中计数节点数量。main 函数读取输入数据并构建二叉搜索树。然后，它调用 countNodes 函数计算最低两层节点的总数，并将结果输出到标准输出。