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

相关文章

嵌入式软件工程师应聘知识点

嵌入式软件工程师应聘知识点

嵌入式软件工程师应聘 修改浏览权限 | 删除 数据结构（C语言）部分常考的知识点： 1、局部变量能、全局变量和静态变量 2、堆和栈 3、Const、volatile、define、typedef的用途 4、链表（比如链表的插入、删除和排序） 5、排序（考查冒泡法的较多） 6、可重入函数 、malloc函数 7、指针（常考函数指针，函数指针，数组指针，指针数组和
阅读更多...
找完工作该补充的东西

找完工作该补充的东西

首先： 锻炼身体，包括乒乓球，羽毛球，都必须练习，学习，锻炼身体等是一个很重要的与人交际沟通的方式； 打牌，娱乐：会玩是一个人很重要的交际沟通的法宝； 摄影：这个是一个兴趣爱好，也是提高自己的审美，生活品质，当然也是与人沟通的重要途径； 做饭：这个的话就是对自己，对朋友非常有益的一件事情；
阅读更多...
22.手绘Spring DI运行时序图

22.手绘Spring DI运行时序图

1.依赖注入发生的时间 当Spring loC容器完成了 Bean定义资源的定位、载入和解析注册以后,loC容器中已经管理类Bean 定义的相关数据，但是此时loC容器还没有对所管理的Bean进行依赖注入，依赖注入在以下两种情况 发生： 、用户第一次调用getBean()方法时，loC容器触发依赖注入。 、当用户在配置文件中将＜bean＞元素配置了 lazy-init二false属性,即让
阅读更多...
数据库期末复习知识点

数据库期末复习知识点

A卷 1. 选择题(30') 2. 判断范式(10') 判断到第三范式 3. 程序填空(20') 4. 分析填空(15') 5. 写SQL(25') 5'一题 恶性 B卷 1. 单选(30') 2. 填空 (20') 3. 程序填空(20') 4. 写SQL(30') 知识点 第一章 数据库管理系统(DBMS)  主要功能 数据定义功能 (DDL, 数据定义语
阅读更多...
SQL Server中，查询数据库中有多少个表，以及数据库其余类型数据统计查询

SQL Server中，查询数据库中有多少个表，以及数据库其余类型数据统计查询

sqlserver查询数据库中有多少个表 sql server 数表:select count(1) from sysobjects where xtype='U'数视图:select count(1) from sysobjects where xtype='V'数存储过程select count(1) from sysobjects where xtype='P' SE
阅读更多...
剑指offer（C++）--平衡二叉树

剑指offer（C++）--平衡二叉树

题目 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 class Solution {public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot==NULL)return true;int left_depth = getdepth(pRoot->left);int right_depth = getdepth(pRoot->rig
阅读更多...
剑指offer（C++）--两个链表的第一个公共结点

剑指offer（C++）--两个链表的第一个公共结点

题目 输入两个链表，找出它们的第一个公共结点。 解法一 两个链表一定有交点的话，方法是指向短链表指针先走完，然后指向长链表，指向长链表指针后走完，指向短链表。所以，第二次走过，一定会在交点相遇。 class Solution {public:ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {ListN
阅读更多...
二叉树三种遍历方式及其实现

二叉树三种遍历方式及其实现

一、基本概念 每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。 性质： 1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 3、对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。 满二叉树：所有终端都在同一层次，且非终端结点的度数为2。 在满二叉树中若其深度为h，则其所包含
阅读更多...
好书推荐《深度学习入门 基于Python的理论与实现》

好书推荐《深度学习入门 基于Python的理论与实现》

如果你对Python有一定的了解，想对深度学习的基本概念和工作原理有一个透彻的理解，想利用Python编写出简单的深度学习程序，那么这本书绝对是最佳的入门教程，理由如下：     （1）撰写者是一名日本普通的AI工作者，主要记录了他在深度学习中的笔记，这本书站在学习者的角度考虑，秉承“解剖”深度学习的底层技术，不使用任何现有的深度学习框架、尽可能仅使用基本的数学知识和Python库。从零创建一个
阅读更多...
LeetCode 算法：二叉树的中序遍历 c++

LeetCode 算法：二叉树的中序遍历 c++

原题链接🔗：二叉树的中序遍历 难度：简单⭐️ 题目 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 示例 1： 输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [1] 输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2