• 在一棵二叉树中,度为0的节点个数
千次阅读
2021-04-06 18:32:56

首先我们要在结点类里加一个bool类型的函数用于判断该结点度是否为1👇

	//判断结点度是否为1
bool isAlone() {
if (leftchild == NULL && rightchild != NULL) {
return true;
}
else if(leftchild != NULL && rightchild == NULL){
return true;
}
else {
return false;
}
}

随后我们再到二叉树类里编写我们的算法

递归算法和上一篇blog里的求二叉树深度（递归+非递归）非常类似👇

//递归统计二叉树度为1的节点个数
int CaculateAlone1(BinaryTreeNode<T>* treeNode) {
int count = 0;
if (treeNode != NULL) {
if (treeNode->isAlone()) {
count++;
}
count += CaculateAlone1(treeNode->getLeft());
count += CaculateAlone1(treeNode->getRight());
}
return count;
}

非递归也和求深度差不多，核心也是借助队列先进先出的特点进行操作👇

//非递归统计二叉树度为1的节点个数
int CaculateAlone2(BinaryTreeNode<T>* treeNode) {
int count = 0;
if (treeNode != NULL) {
queue<BinaryTreeNode<T>*> q;
q.push(treeNode);
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
BinaryTreeNode<T>* p = q.front();
q.pop();
if (p->isAlone()) {
count++;
}
if (p->getLeft()) {
q.push(p->getLeft());
}
if (p->getRight()) {
q.push(p->getRight());
}
}
}
}
return count;
}

最后附上完整代码👇

#include<iostream>
#include<queue>
using namespace std;

//结点类
template<class T>
class BinaryTreeNode {
//友元类声明
template<class T>
friend class BinaryTree;
private:
T data;
BinaryTreeNode<T>* leftchild;
BinaryTreeNode<T>* rightchild;
public:
//构造函数
BinaryTreeNode() {
leftchild = NULL;
rightchild = NULL;
}
BinaryTreeNode(const T& dataValue) {
data = dataValue;
leftchild = NULL;
rightchild = NULL;
}
BinaryTreeNode(const T& dataValue, BinaryTreeNode<T>* leftchildValue, BinaryTreeNode<T>* rightchildValue) {
data = dataValue;
leftchild = leftchildValue;
rightchild = rightchildValue;
}
//析构函数
~BinaryTreeNode() {
leftchild = NULL;
rightchild = NULL;
}
//取左结点
BinaryTreeNode<T>* getLeft() {
return leftchild;
}
//取右结点
BinaryTreeNode<T>* getRight() {
return rightchild;
}
//判断结点度是否为1
bool isAlone() {
if (leftchild == NULL && rightchild != NULL) {
return true;
}
else if(leftchild != NULL && rightchild == NULL){
return true;
}
else {
return false;
}
}
};

//二叉树类
template<class T>
class BinaryTree {
private:
BinaryTreeNode<T>* root;
public:
//构造函数
BinaryTree() {
root = NULL;
cout << "Now start to construct the BinaryTree" << endl;
CreateNode(root);
}
//析构函数
~BinaryTree() {
root = NULL;
}
//前序构建二叉树
void CreateNode(BinaryTreeNode<T>* &treeNode) {
cout << "Please enter a value or '#' to stop:";
T dataValue;
cin >> dataValue;
treeNode = new BinaryTreeNode<T>(dataValue);
if (treeNode->data == '#') {
delete treeNode;
treeNode = NULL;
}
else {
CreateNode(treeNode->leftchild);
CreateNode(treeNode->rightchild);
}
}
//取根节点
BinaryTreeNode<T>* getRoot() {
return root;
}
//递归统计二叉树度为1的节点个数
int CaculateAlone1(BinaryTreeNode<T>* treeNode) {
int count = 0;
if (treeNode != NULL) {
if (treeNode->isAlone()) {
count++;
}
count += CaculateAlone1(treeNode->getLeft());
count += CaculateAlone1(treeNode->getRight());
}
return count;
}
//非递归统计二叉树度为1的节点个数
int CaculateAlone2(BinaryTreeNode<T>* treeNode) {
int count = 0;
if (treeNode != NULL) {
queue<BinaryTreeNode<T>*> q;
q.push(treeNode);
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
BinaryTreeNode<T>* p = q.front();
q.pop();
if (p->isAlone()) {
count++;
}
if (p->getLeft()) {
q.push(p->getLeft());
}
if (p->getRight()) {
q.push(p->getRight());
}
}
}
}
return count;
}
};
int main() {
//前序构建二叉树
BinaryTree<char> test;
//统计二叉树度为1的节点个数
cout << endl << "递归求得度为1的节点个数：";
cout << test.CaculateAlone1(test.getRoot());
cout << endl << "非递归求得度为1的节点个数：";
cout << test.CaculateAlone2(test.getRoot());
}

更多相关内容
• 在二叉树中查找度为2的节点个数返回，可供参考
• 建立一棵二叉树，利用递归求二叉树节点个数 2.实现代码 class BinaryTreeNode(object): # 创建二叉树结点的函数 def __init__(self): self.data = '#' self.LChild = None self.RChild = None class BinaryTree...
• // // queue_.cpp // LinkQueue // // Created by ljpc on 2018/5/30. ...// #include "queue_.h" ...void creatLinkQueue(LinkQueue*...// 创建一个循环队列指针que { que->front = (Node*)malloc(sizeof(Node)); que.
//
//  binary_tree.cpp
//  BinaryTreeApp
//
//  Created by ljpc on 2018/5/3.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include "binary_tree.h"

int GetTreeDepth(BiTreeNode* root)
// 计算该二叉树的深度
// 参数：二叉树根节点root
// 返回：二叉树的深度
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int a,b;
if(root==NULL)
{
return 0;
}
else
{
a=GetTreeDepth(root->right);
b=GetTreeDepth(root->left);
if(a>b)
{
return a+1;
}
else
{
return b+1;
}
}
/********** End **********/
}

int GetNodeNumber(BiTreeNode* root)
// 计算该二叉树的总节点个数
// 参数：二叉树根节点root
// 返回：二叉树的总节点个数
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
if(root!=NULL)
{
return GetNodeNumber(root->left)+GetNodeNumber(root->right)+1;
}
else
{
return 0;
}
/********** End **********/
}

int GetLeafNodeNumber(BiTreeNode* root)
// 计算该二叉树的叶子节点个数
// 参数：二叉树根节点root
// 返回：二叉树的叶子节点个数
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
if(root==NULL)
{
return 0;
}
else if(root->left==NULL&&root->right==NULL)
{
return 1;
}
else
{
return GetLeafNodeNumber(root->left)+GetLeafNodeNumber(root->right);
}
/********** End **********/
}

任务描述

本关任务：给定一棵二叉树，计算该二叉树的深度、总节点个数和叶子节点个数。

相关知识

为了完成本关任务，你需要掌握：1.二叉树深度概念，2.二叉树节点，3.二叉树叶子节点概念。

二叉树深度概念

二叉树的深度指的是二叉树中最大的结点层数。例如：图1所示的二叉树最大的节点层数为3，所以该二叉树深度为3

二叉树节点

二叉树的节点包含一个数据元素及两个指向子树的分支，例如：图1所示的二叉树的总节点个数为6

二叉树叶子节点概念

叶子节点是度为0的节点，二叉树节点的度为子树的个数。例如：图1所示的二叉树叶子节点为CDF，个数为3

编程要求

本关的编程任务是补全右侧代码片段GetTreeDepthGetNodeNumberGetLeafNodeNumberBeginEnd中间的代码，具体要求如下：

• GetTreeDepth中计算该二叉树的深度，返回深度值。
• GetNodeNumber中计算该二叉树的总的节点个数，返回节点个数。
• GetLeafNodeNumber中计算该二叉树的叶子节点个数，返回叶子节点个数。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：ABC##D##EF###
预期输出：
3
6
3

测试输入：ABCD###E#F##G##
预期输出：
4
7
3

展开全文
• 度为0节点个数：n0 度为1节点个数：n1 度为2的节点个数：n2 即：n0 + n1 + n2 = n 该二叉树包含的边总数：n-1 度为0节点的边的条0 度为1节点的边的条1 度为2的节点的边的条：2 即：n - 1 = n1 +...

二叉树：节点的度最大为2
假设一个二叉树包含的节点总数为：n
度为0的节点个数：n0
度为1的节点个数：n1
度为2的节点个数：n2
即：n0 + n1 + n2 = n
该二叉树包含的边总数为：n - 1
度为0的节点的边的条数：0
度为1的节点的边的条数：1
度为2的节点的边的条数：2
即：n - 1 = n1 + 2 n2
n0 + n1 + n2 -1 = n1 + 2 n2
得：n0 = n2 + 1

展开全文
• 主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下
• 若用二叉链表作为二叉树的存储表示，设计算法求二叉树中度为1的结点个数。 利用二叉树结构上的递归特性，用递归的方法实现。 分为4种情况： 若某结点有左子树和右子树，则以此结点根的二叉树中度为1的结点个数...

若用二叉链表作为二叉树的存储表示，设计算法求二叉树中度为1的结点个数。

利用二叉树结构上的递归特性，用递归的方法实现。

分为4种情况：

1. 若某结点有左子树和右子树，则以此结点为根的二叉树中度为1的结点个数

=左子树的度为1的结点个数+右子树的度为1的结点个数。

1. 若该结点只有左子树，则以该结点为根的二叉树中度为1的结点个数= 1+左

子树中度为1的结点个数。（+1是因为要算上以此结点为根的结点）。

1. 若该结点只有右子树，则以该结点为根的二叉树中度为1的结点个数= 1+右

子树中度为1的结点个数。（+1是因为要算上以此结点为根的结点）。

1. 若该结点没有子树，则以此结点为根的二叉树度为1的结点个数=0。

该算法使用二叉链表来存储二叉树。

算法设计了两个函数：

1. 函数CreateBiTree()用来先序创建一颗二叉树；
2. 函数Num()用来求二叉树中度为1的结点的个数；
3. 主函数main()

/********
date:2021-11-20
author:sy
version:1.0
Description:求二叉树中度为1的结点个数
*********/
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
/*定义二叉树的二叉链表结点的结构*/
typedef struct  BiTNode
{
datatype data;            //数据域
struct BiTNode *lchild;   //左孩子指针
struct BiTNode *rchild;   //右孩子指针
}BiTNode,*BiTree;
/*先序创建二叉树*/
void CreateBiTree(BiTree *T)
{
char ch;
ch=getchar();
if(ch=='#')
{
(*T)=NULL;
}
else
{
(*T)=(BiTree)malloc(sizeof(BiTNode)); //为二叉树申请结点
(*T)->data=ch;                 //生成根结点
CreateBiTree(&(*T)->lchild);   //构造左子树
CreateBiTree(&(*T)->rchild);   //构造右子树
}
}
/*求二叉树中度为1的结点个数*/
int Num(BiTree T)
{
if(T==NULL)
{
return 0;
}
if(T->lchild != NULL && T->rchild != NULL)      /*某结点有左右子树*/
{
return Num(T->lchild) + Num(T->rchild);
}
else if(T->lchild != NULL && T->rchild == NULL)  /*某结点只有左子树*/
{
return 1 + Num(T->lchild);
}
else if(T->lchild == NULL && T->rchild != NULL)   /*某结点只有右子树*/
{
return 1 + Num(T->rchild);
}
return 0;
}
int main()
{
BiTree T=NULL;
printf("\n 创建一棵二叉树：\n");
CreateBiTree(&T);
printf("\n 二叉树中度为1的结点个数为：%d\n",Num(T));
}


运行结果

展开全文
• int NumsDegree_0(BiTree T) { if(T) { if(T-&gt;left == NULL &amp;&amp; T-&gt;right == NULL) return 1; else return NumsDegree_0(T-&gt;left)+NumsDegree_0(T-&gt;right);...
• Description 给定先序序列，按照该序列创建对应的二叉树，并输出该...行，三整数分别代表该二叉树度为0,1和2的结点个数 Sample Input ABD^^^CE^^F^^ Sample Output 3 1 2 #include<stdio.h> #include...
• 二叉树节点数为N N=n0+n1+n2 N=n22+n11+n0*0+1 解得：n0=n2+1
• 文章目录实验五 树的应用--二叉树的遍历、实验目的：1、了解二叉树的逻辑结构和物理结构；2、掌握二叉树数据类型定义；3、熟练掌握二叉树在链式存储结构上的遍历操作；二、实验要求：三、实验任务：四、代码如下五...
• 数据结构 - 统计二叉树度为0/1/2的结点个数（递归） 文章目录数据结构 - 统计二叉树度为0/1/2的结点个数（递归）0. 变量/函数声明树的结构体函数声明1. 统计结点统计度为0的结点数统计度为1的结点数统计度2的结...
• 掌握了二叉树的先序遍历递归算法、中序遍历递归算法和后序遍历递归算法的实现流程后，我们稍微开拓一下视野，来看一下该如何求出二叉树中度为0度为1度为2的结点的个数. 设计算法之前，我们要弄清什么是...
• 编写程序统计一棵非空二叉树中每层度为1的结点的数目，二叉树结点个数不超过100。 输入格式: 输入为一个字符串，表示带空指针信息的二叉树先根序列。其中空指针信息用#表示，二叉树结点a-z, A-Z的字母。 输出格式:...
• 【问题描述】首先利用二叉树的前序遍历建立一棵二叉树，分别用3递归函数统计度为0度为1度为2的结点个数，并输出结果，这3函数可以定义为二叉树的成员函数 【输入形式】假设二叉树的结点字符型，输入“#”...
• 设：节点个数为n，叶子节点个数为n0n_0n0​，度为1节点个数为n1n_1n1​，度为2的节点个数为n2n_2n2​，边的个数b。 n = n0n_0n0​ + n1n_1n1​ + n2n_2n2​ b = n - 1 可得 b = n0n_0n0​ + n1n_1n1​ + n2n_...
• 输入的第行表示节点的个数n（1 ≤ n ≤ 1000，节点的编号为0到n-1）组成， 下面是n-1行，每行有两整数，第一个数表示父节点的编号，第二个数表示子节点的编号 输出描述: 输出树的高度，为一个整数
• int Node2(BiTree T) ... return 0; else if(T->lchild&&T->rchild) return Node2(T->lchild)+Node2(T->rchild)+1; else return Node2(T->lchild)+Node2(T->rchild); }
• c代码-求二叉树的叶子节点和高度
• 文章目录完全二叉树节点个数1.三种解法迭代法--层序遍历递归法--后序遍历递归法--完全二叉树性质2.总结 完全二叉树节点个数 leetcode链接 1.三种解法 迭代法–层序遍历 直接层序遍历遍历所有节点，然后统计个数...
• 完全二叉树节点计算基本是几类，要么是求完全二叉树中的叶子节点个数或者度为1或者2的节点的个数。 其实这些问题根本上一一类问题，求解方法也是基本相同的。 先把题列出来： 一棵完全二叉树具有1000结点，...
• 设总节点个数为n，叶子节点个数为n0度为1节点个数为n1，度为2的节点个数为n2，则必有 n0+n1+n2 = n …（①） (1) 对于二叉树有： n0 = n2+1…（②） （什么呢？下面证明一下） 【注】（1）这规律是所有...
• 本题要求实现一个函数，可统计二叉树中度为1的结点个数。 函数接口定义： int NodeCount ( BiTree T); T是二叉树树根指针，函数NodeCount返回二叉树中度为1的结点个数，若树空，返回0。 裁判测试程序样例： ...
• 参考资料 http://blog.csdn.net/u013227200/article/details/37992463
• 设叶子节点个数为n0度为1节点个数为n1，度为2的节点个数为n2，必有 n0+n1+n2 = n (1) 对于二叉树有： n0 = n2+1 (2) 由上面两式 ==&gt; n0 = (n+1-n1)/2 ，n2 = (n-1-n1)/2 (3) 由完全二叉树的性质可知：...
• Description 给定先序序列，按照该序列创建对应的...行，三整数分别代表该二叉树度为0,1和2的结点个数 Sample Input ABD^^^CE^^F^^ Sample Output 3 1 2 递归遍历寻找 理解递归的思想 就很好理解程...
• 二叉树求解节点个数、求二叉树中节点总数二、求二叉树中度为0节点个数三、求二叉树中度为1节点个数四、求二叉树中度为2的节点个数五、求二叉树第k层节点个数六、结果展示 以此树例： 、求二叉树中节点...
• 一个二叉树有100个子节点数为2的节点，100个子节点数为1节点，那么个子节点数为0节点（叶节点）的个数: A. 101 B. 100 C. 200 D. 300 E. 99 F. 1  正确答案(A) 解法： 来源：牛客网：链接：...

...