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