使用 C++ 计算二叉树中的完整节点数(迭代和递归)
给定一个二叉树，任务是使用迭代和递归方法计算二叉树中可用的完整节点数。完整节点是那些同时具有子节点且没有子节点为空的节点。请注意，在完整节点中，我们考虑恰好具有两个子节点的节点。
二叉树是一种用于数据存储目的的特殊数据结构。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树兼具有序数组和链表的优点，因为搜索速度与排序数组一样快，插入或删除操作速度与链表一样快。非叶节点也称为父节点，因为它们有超过 0 个子节点和少于 2 个子节点。
二叉树的结构如下所示 −
例如
输入−
输出 −计数为 2
解释 −在给定的树中有 2 个节点，即 10 和 20，它们恰好有两个子节点或完整节点，其他节点要么有一个子节点，要么没有子节点。
迭代
以下程序中使用的方法如下
创建一个包含数据部分、左指针和右指针的节点结构。
创建一个函数将节点插入二叉树。
创建一个函数来计算完整节点的数量。
在函数内部，检查 IF !node，然后返回，因为树中没有节点。
声明一个临时变量 count 来存储完整节点的数量
创建一个队列类型变量，假设为 qu
将节点推送到队列中qu.push(node)
循环 while !qu.empty()
创建一个临时变量，假设为 Node 类型的 temp，并使用 queue.front() 初始化它
使用 qu.pop() 弹出元素
检查 IF (!temp-> left AND temp-> right)，然后将计数加 1
检查 IF (temp->left != NULL)，然后执行 qu.push(temp->left)
检查 IF (temp->right != NULL)，然后执行 qu.push(temp->right)
返回 count
打印结果。
示例
// 迭代程序计数完整节点
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// 函数用于计算二叉树中的完整节点
int fullcount(struct Node* node){
// 检查树是否为空
if (!node){
return 0;
}
queue<Node *> myqueue;
// 使用级别顺序遍历
int result = 0;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}
输出
如果运行上述代码，我们将得到以下输出 −
count is: 2
递归
以下程序中使用的方法如下
创建一个包含数据部分、左指针和右指针的节点结构。
创建一个函数将节点插入二叉树。
创建一个函数来计算完整节点。
在函数内部，检查 IF !node，然后返回，因为树中没有节点。
声明一个临时变量 count 来存储半节点的数量
检查 IF (root -> left AND root->right)，然后将计数增加 1
设置 count = count + recursive_call_to_this_function(root->left) + recursive_call_to_this_function(root->right)
返回 count
打印结果。
示例
// 递归程序计数完整节点
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// 获取完整节点计数的函数
int fullcount(struct Node* root){
if (root == NULL){
return 0;
}
int result = 0;
if (root->left && root->right){
result++;
}
result += (fullcount(root->left) +
fullcount(root->right));
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
}
输出
如果运行上述代码，我们将得到以下输出 −
count is: 2
