北邮22信通：二叉树 书上重要知识点补充 例4.3 统计结点总数 深度和叶子结点数

2023-11-10 11:40
文章标签 二叉树 统计 知识点 深度 补充 22 重要 总数 叶子 结点 信通 4.3 北邮 书上

本文主要是介绍北邮22信通：二叉树 书上重要知识点补充 例4.3 统计结点总数 深度和叶子结点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

获取更多文章  请访问专栏：

北邮22信通_青山如墨雨如画的博客-CSDN博客

目录

一.统计结点总个数

二.统计二叉树深度

三.统计叶子结点总数

四.完整代码

4.1测试int存储类型：

代码部分：

运行结果： 

4.2测试class储存类型：

代码部分：

运行结果： 

***说明***

书上例4.3的代码和思考题~

对上一篇文章的功能有了新补充~

函数主要思想：递归调用。

***说明完毕***

一.统计结点总个数

思路：二叉树结点总数等于其左子树的节点总数+右子树的结点总数+根结点。

代码部分：

template<class temp>
int bintree<temp>::nodecount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = nodecount(r->leftchild);int n = nodecount(r->rightchild);return m + n + 1;}
}

二.统计二叉树深度

代码部分：

思路：保存现场截止。

template<class temp>
int bintree<temp>::height(binnode<temp>* r)
{if (r == NULL)return 0;else{int m = height(r->leftchild);int n = height(r->rightchild);return m > n ? m + 1 : n + 1;}
}

三.统计叶子结点总数

        思路：判断某一处的结点是不是叶子结点，判断条件就是看它左右孩子是否没有。如果都没有，那就是叶子结点。然后调用函数递归来实现整体。

代码部分：

template<class temp>
int bintree<temp>::leafcount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = leafcount(r->leftchild);int n = leafcount(r->rightchild);return m + n;}
}

四.完整代码

4.1测试int存储类型：

代码部分：

#include<iostream>
#define MAXSIZE 100000
//注意：不能将上面这行宏定义写成
//#define MAXSIZE 1e5
//上面这样写会报错！！
using namespace std;template<class temp>
struct binnode
{temp data;binnode<temp>* leftchild;binnode<temp>* rightchild;
};template<class temp>
class bintree
{
private:void create(binnode<temp>*& r, temp data[], int i, int n);void release(binnode<temp>* r);
public:binnode<temp>* root;bintree(temp data[], int n);void preorder(binnode<temp>* r);void inorder(binnode<temp>* r);void postorder(binnode<temp>* r);void levelorder(binnode<temp>* r);int nodecount(binnode<temp>* r);int height(binnode<temp>* r);int leafcount(binnode<temp>* r);~bintree();
};template<class temp>
void bintree<temp>::create(binnode<temp>*& r, temp data[], int i, int n)
{if (i <= n && data[i - 1] != 0){r = new binnode<temp>;r->data = data[i - 1];r->leftchild = r->rightchild = NULL;create(r->leftchild, data, 2 * i, n);/*书上代码错误1：向函数传入实参时少传入一个n*/create(r->rightchild, data, 2 * i + 1, n);/*书上代码错误同上*/}
}template<class temp>
bintree<temp>::bintree(temp data[], int n)
/*书上代码错误2：构造函数不能有返回值类型，但是书上多加了一个void*/
/*如果构造函数的声明语句写成
void bintree<temp>::bintree(temp data[], int n)，
程序会报错：不能在构造函数上指定返回值类型*/
{create(this->root, data, 1, n);
}template<class temp>
void bintree<temp>::preorder(binnode<temp>* r)
{if (r != NULL){cout << r->data;//访问结点；preorder(r->leftchild);//遍历左子树preorder(r->rightchild);//遍历右子树}
}template<class temp>
void bintree<temp>::inorder(binnode<temp>* r)
{if (r != NULL){inorder(r->leftchild);cout << r->data;inorder(r->rightchild);}
}template<class temp>
void bintree<temp>::postorder(binnode<temp>* r)
{if (r != NULL){postorder(r->leftchild);postorder(r->rightchild);cout << r->data;}
}template<class temp>
void bintree<temp>::levelorder(binnode<temp>* R)
{binnode<temp>* queue[MAXSIZE];int f = 0, r = 0;if (R != NULL)queue[++r] = R;//根节点入队while (f != r){binnode<temp>* p = queue[++f];//队头元素入队cout << p->data;//出队打印if (p->leftchild != NULL)queue[++r] = p->leftchild;//左孩子入队if (p->rightchild != NULL)queue[++r] = p->rightchild;//右孩子入队}
}template <class temp>
void bintree<temp>::release(binnode<temp>* r)
{if (r != NULL){release(r->leftchild);release(r->rightchild);delete r;}
}/*书上代码错误3：不能在析构函数上指定返回值类型，但是书上代码多了一个void*/
template<class temp>
bintree<temp>::~bintree()
{release(this->root);
}template<class temp>
int bintree<temp>::nodecount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = nodecount(r->leftchild);int n = nodecount(r->rightchild);return m + n + 1;}
}template<class temp>
int bintree<temp>::height(binnode<temp>* r)
{if (r == NULL)return 0;else{int m = height(r->leftchild);int n = height(r->rightchild);return m > n ? m + 1 : n + 1;}
}template<class temp>
int bintree<temp>::leafcount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = leafcount(r->leftchild);int n = leafcount(r->rightchild);return m + n;}
}int main()
{system("color 0A");int a[5] = { 1,2,3,4,5 };bintree<int>bintreee(a, 5);cout << "前序遍历:" << endl;bintreee.preorder(bintreee.root);cout << endl << "中序遍历:" << endl;bintreee.inorder(bintreee.root);cout << endl << "后序遍历:" << endl;bintreee.postorder(bintreee.root);cout << endl << "层序遍历:" << endl;bintreee.levelorder(bintreee.root);cout << endl << "二叉树中的节点总数为:";cout << bintreee.nodecount(bintreee.root);cout << endl << "二叉树的深度为:";cout << bintreee.height(bintreee.root);cout << endl << "二叉树的叶子结点数为:";cout << bintreee.leafcount(bintreee.root);cout << endl;
}

运行结果： 

4.2测试class储存类型：

代码部分：

#include<iostream>
#define MAXSIZE 100000
//注意：不能将上面这行宏定义写成
//#define MAXSIZE 1e5
//上面这样写会报错！！
using namespace std;
class student
{
private:int ID;string name;
public:int existence;student(){this->ID = 0;this->name = "unknown name";this->existence = 0;}student(int ID, string name){this->ID = ID;this->name = name;this->existence = 1;}friend ostream& operator<<(ostream& output, student& s){output << s.ID << " " << s.name << endl;return output;}
};template<class temp>
struct binnode
{temp data;binnode<temp>* leftchild;binnode<temp>* rightchild;
};template<class temp>
class bintree
{
private:void create(binnode<temp>*& r, temp data[], int i, int n);void release(binnode<temp>* r);
public:binnode<temp>* root;bintree(temp data[], int n);void preorder(binnode<temp>* r);void inorder(binnode<temp>* r);void postorder(binnode<temp>* r);void levelorder(binnode<temp>* r);int nodecount(binnode<temp>* r);int height(binnode<temp>* r);int leafcount(binnode<temp>* r);~bintree();
};template<class temp>
void bintree<temp>::create(binnode<temp>*& r, temp data[], int i, int n)
{/*书上代码的一个问题：data[i-1]!=0会报错，这是因为data的数据类型是temp，没法实现！=的运算*///书上原代码//if (i <= n && data[i - 1] != 0)if (i <= n && data[i - 1].existence != 0){r = new binnode<temp>;r->data = data[i - 1];r->leftchild = r->rightchild = NULL;create(r->leftchild, data, 2 * i, n);/*书上代码错误1：向函数传入实参时少传入一个n*/create(r->rightchild, data, 2 * i + 1, n);/*书上代码错误同上*/}
}template<class temp>
bintree<temp>::bintree(temp data[], int n)
/*书上代码错误2：构造函数不能有返回值类型，但是书上多加了一个void*/
/*如果构造函数的声明语句写成
void bintree<temp>::bintree(temp data[], int n)，
程序会报错：不能在构造函数上指定返回值类型*/
{create(this->root, data, 1, n);
}template<class temp>
void bintree<temp>::preorder(binnode<temp>* r)
{if (r != NULL){cout << r->data;//访问结点；preorder(r->leftchild);//遍历左子树preorder(r->rightchild);//遍历右子树}
}template<class temp>
void bintree<temp>::inorder(binnode<temp>* r)
{if (r != NULL){inorder(r->leftchild);cout << r->data;inorder(r->rightchild);}
}template<class temp>
void bintree<temp>::postorder(binnode<temp>* r)
{if (r != NULL){postorder(r->leftchild);postorder(r->rightchild);cout << r->data;}
}template<class temp>
void bintree<temp>::levelorder(binnode<temp>* R)
{binnode<temp>* queue[MAXSIZE];int f = 0, r = 0;if (R != NULL)queue[++r] = R;//根节点入队while (f != r){binnode<temp>* p = queue[++f];//队头元素入队cout << p->data;//出队打印if (p->leftchild != NULL)queue[++r] = p->leftchild;//左孩子入队if (p->rightchild != NULL)queue[++r] = p->rightchild;//右孩子入队}
}template <class temp>
void bintree<temp>::release(binnode<temp>* r)
{if (r != NULL){release(r->leftchild);release(r->rightchild);delete r;}
}/*书上代码错误3：不能在析构函数上指定返回值类型，但是书上代码多了一个void*/
template<class temp>
bintree<temp>::~bintree()
{release(this->root);
}template<class temp>
int bintree<temp>::nodecount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = nodecount(r->leftchild);int n = nodecount(r->rightchild);return m + n + 1;}
}template<class temp>
int bintree<temp>::height(binnode<temp>* r)
{if (r == NULL)return 0;else{int m = height(r->leftchild);int n = height(r->rightchild);return m > n ? m + 1 : n + 1;}
}template<class temp>
int bintree<temp>::leafcount(binnode<temp>* r)
{if (r == NULL)return 0;if (r->leftchild == NULL && r->rightchild == NULL)return 1;else{int m = leafcount(r->leftchild);int n = leafcount(r->rightchild);return m + n;}
}int main()
{system("color 0A");student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };bintree<student>bintreee(stu, 5);cout << "前序遍历:" << endl;bintreee.preorder(bintreee.root);/*说明：这里体现了将根节点定义为public类型的好处，不然需要通过一个成员函数来实现这个功能，从数据保密性来看，这样做也是可以的：外部如果不通过调用成员函数，就只能访问根节点一个节点内的数据，但是其他任意节点内的数据都无法访问，安全性也相对较高。*/cout << endl << "中序遍历:" << endl;bintreee.inorder(bintreee.root);cout << endl << "后序遍历:" << endl;bintreee.postorder(bintreee.root);cout << endl << "层序遍历:" << endl;bintreee.levelorder(bintreee.root);cout << endl << "二叉树中的节点总数为:";cout << bintreee.nodecount(bintreee.root);cout << endl << "二叉树的深度为:";cout << bintreee.height(bintreee.root);cout << endl << "二叉树的叶子结点数为:";cout << bintreee.leafcount(bintreee.root);cout << endl;return 0;
}

运行结果： 

这篇关于北邮22信通：二叉树 书上重要知识点补充 例4.3 统计结点总数 深度和叶子结点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/382451。

相关文章

Python中文件读取操作漏洞深度解析与防护指南

Python中文件读取操作漏洞深度解析与防护指南

《Python中文件读取操作漏洞深度解析与防护指南》在Web应用开发中,文件操作是最基础也最危险的功能之一,这篇文章将全面剖析Python环境中常见的文件读取漏洞类型,成因及防护方案,感兴趣的小伙伴可... 目录引言一、静态资源处理中的路径穿越漏洞1.1 典型漏洞场景1.2 os.path.join()的陷
阅读更多...
详解如何使用Python从零开始构建文本统计模型

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可
阅读更多...
Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

Spring Boot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)

《SpringBoot拦截器Interceptor与过滤器Filter深度解析(区别、实现与实战指南)》：本文主要介绍SpringBoot拦截器Interceptor与过滤器Filter深度解析... 目录Spring Boot拦截器（Interceptor）与过滤器（Filter）深度解析：区别、实现与实
阅读更多...
MyBatis分页插件PageHelper深度解析与实践指南

MyBatis分页插件PageHelper深度解析与实践指南

《MyBatis分页插件PageHelper深度解析与实践指南》在数据库操作中,分页查询是最常见的需求之一,传统的分页方式通常有两种内存分页和SQL分页,MyBatis作为优秀的ORM框架,本身并未提... 目录1. 为什么需要分页插件？2. PageHelper简介3. PageHelper集成与配置3.
阅读更多...
Maven 插件配置分层架构深度解析

Maven 插件配置分层架构深度解析

《Maven插件配置分层架构深度解析》：本文主要介绍Maven插件配置分层架构深度解析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Maven 插件配置分层架构深度解析引言：当构建逻辑遇上复杂配置第一章 Maven插件配置的三重境界1.1 插件配置的拓扑
阅读更多...
Pandas中统计汇总可视化函数plot()的使用

Pandas中统计汇总可视化函数plot()的使用

《Pandas中统计汇总可视化函数plot()的使用》Pandas提供了许多强大的数据处理和分析功能,其中plot()函数就是其可视化功能的一个重要组成部分,本文主要介绍了Pandas中统计汇总可视化... 目录一、plot()函数简介二、plot()函数的基本用法三、plot()函数的参数详解四、使用pl
阅读更多...
Pandas统计每行数据中的空值的方法示例

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据（NaN值）是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值？为什么要统计空值？准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处
阅读更多...
Python中__init__方法使用的深度解析

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程（OOP）体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认
阅读更多...
Mysql如何将数据按照年月分组的统计

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》：本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA
阅读更多...
SpringCloud动态配置注解@RefreshScope与@Component的深度解析

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2