北邮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。

相关文章

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.
阅读更多...
Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
Redis中高并发读写性能的深度解析与优化

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、
阅读更多...
SpringBoot整合jasypt实现重要数据加密

SpringBoot整合jasypt实现重要数据加密

《SpringBoot整合jasypt实现重要数据加密》Jasypt是一个专注于简化Java加密操作的开源工具,：本文主要介绍详细介绍了如何使用jasypt实现重要数据加密,感兴趣的小伙伴可... 目录jasypt简介 jasypt的优点SpringBoot使用jasypt创建mapper接口配置文件加密
阅读更多...
一文详解SQL Server如何跟踪自动统计信息更新

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中，我们都清楚统计信息对于优化器来说非常重要。一般情况下，我们会开启"自动更新
阅读更多...
最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言
阅读更多...
Redis 内存淘汰策略深度解析(最新推荐)

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction（不淘汰）​2.2 ​LR
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2