数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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) 则将 count 加 1
检查 IF (temp->left != NULL) 则执行 qu.push(temp->left)
返回计数
打印结果。
示例
// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
// If tree is empty
if (!node)
return 0;
int result = 0; // Initialize count of half nodes
// Do level order traversal starting from root
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;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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) 则将 count 加 1
设置 count = count + 递归调用此函数(root->left) + 递归调用此函数(root->right)
返回计数
打印结果。
示例
// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
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;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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
367 次浏览
