实验报告二叉树求叶子结点数目

一 、实验目的和要求(1)掌握树的相关概念，包括树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节 点、树的深度、森林等定义。

(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。

(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

(4)掌握二叉树的性质。

(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。

(6)重点掌握二叉树的基本运算和各种遍历算法的实现。

(7)掌握线索二叉树的概念和相关算法的实现。

(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码的产生方法。

(9)掌握并查集的相关概念和算法。

(10)灵活运用二叉树这种数据结构解决一些综合应用问题。

二、实验内容注：二叉树b 为如图7-123所示的一棵二叉树图7-123+实验7.1 编写一个程序algo7-1.cpp,实现二叉树的各种运算，并在此基础上设计一个程序exp7-1.cpp 完成如下功能：(1)输出二叉树b ;(2)输出H 节点的左、右孩子节点值； (3)输出二叉树b 的深度； (4)输出二叉树b 的宽度； (5)输出二叉树b 的节点个数；(6)输出二叉树b 的叶子节点个数。

实验7.2设计一个程序exp7-2.cpp,实现二叉树的先序遍历、中序遍历和后序遍历和非递归算法， 以及层次变量里的算法。

并对图7-123所示的二叉树b 给出求解结果。

b+ACF GIKL+NM+E+HdJD₄B臣1607-1.CPPif(b?-HULL)re3P4+;Qu[rear]-p-b;Qu[rear].1no=1;while(reart=front){Front++;b=Qu[front]-P;lnum-Qu[front].1no;if(b->Ichildt=NULL)rpar+t;Qu[rear]-p=b->1child;Qu[rear].Ino-lnun+1;if(D->rch11d?=NULL)1/根结点指针入队//根结点的层次编号为1 1/队列不为空1/队头出队1/左孩子入队1/右孩子入队redr+t;qu[rear]-p=b->rchild;Qu[rear].1no-lnun*1;}}nax-0;lnun-1;i-1;uhile(i<=rear){n=0;whdle(i<=rear ge Qu[1].1no==1num)n+t;it+;Inun-Qu[i].1n0;if(n>max)nax=n;}return max;田1607-1.CPPreturn max;}elsereturn o;口×int Modes(BTNode *D) //求二叉树D的结点个数int nun1,nun2;if(b==NULL)returng,else if(b->ichild==NULL&D->rchild==NULL)return 1;else{num1-Hodes(b->Ichild);num2=Nodes(b->rchild);return(num1+nun2+1);LeafNodes(BINode *D) //求二叉树p的叶子结点个数int num1,num2;1f(D==NULL)return 0;else if(b->1chi1d==NULLc& b->rch11d==NULL)return 1;else{num1-LeafModes(b->lchild);num2=LeafNodes(b->rchild);return(nun1+nun2);int程序执行结果如下：xCProrn FlslirosfViu l SudiollyPrjecslro7 LJebuglFoj7 ex<1)输出二叉树：A<B<D,E<H<J,K<L,M<,N>>>>),C<F,G<,I>>)<2)'H’结点：左孩子为J石孩子为K(3)二叉树b的深度：7<4)二叉树b的宽度：4(5)二叉树b的结点个数：14(6)二叉树b的叶子结点个数：6<?>释放二叉树bPress any key to continue实验7 . 2程序exp7-2.cpp设计如下：坠eTPT-2.EPP#include<stdio.h》winclude<malloc.h>deFn Masie 00typde chr ElemTyetypede sruct nde{ElemType data;stuc node *lclldstruct node rchild;》BTHode;extern vod reaeBNodeBTNode extrn void DispBTHode(BTNodeuoid ProrderBTNode *b)if(b?-NULL)- 回1 / 数据元素1 / 指向左孩子1 / 指向右孩子*eb car *str)xb1 / 先序遍历的递归算法1 / 访问根结点/ / 递归访问左子树1 7 递归访问右子树/ / 根结点入栈//栈不为空时循环/ / 退栈并访问该结点/ / 右孩子入栈{》v oidprintf(*c“,b->data); Preorder(b->lchild); Pre0rder(b->rchild);Preorder1(BTNode *b)BTNode xSt[Maxsize],*p;int top=-1;if(b!-HULL)top++;St[top]-b;uhle (op>-)p-St[top];top--;printf("%c“,p->data);if(p->rchild?-HULL)A约e程p7-2.CPPprintF(”后序逅历序列：\n");printf(" 递归算法=");Postorder(b);printf("\n");printf(“非递归算法：“);Postorder1(b);printf("\n");序执行结果如下：xCAPrograFleicsoftVisal SudlyrjecsProj 2Debuzlroj72ex"二叉树b:A(B(D,ECH<J,K(L,M<,N)>))),C(F,GC.I>))层次遍历序列：A B C D E F G H I J K L M N先序遍历序列：递归算法：A B D E H J K L M N C F G I非归算法：A B D E H J K L M N C F G I中序遍历序列：递归算法： D B J H L K M N E A F C G I非递归算法：D B J H L K M N E A F C G I后序遍历序列：递归算法： D J L N M K H E B F I G C A非递归算法：D J L N H K H E B F I G C APress any key to continue臼p7-3.CPP15Pp a t h[p a t h l e n]-b->d a t a;//将当前结点放入路径中p a t h l e n t+;/7路任长度培1Al1Path1(b->ichild,patn,pathlen);1/递归扫描左子树Al1Path1(b->rchild,path,pathlen); //递归扫描右子树pathlen-- ; //恢复环境uoid Longpath(BTNode *b,Elemtype path[1,int pathlen,Elemtype longpath[],int elongpatnien) int i;1f(b==NULL){if(pathlen>longpatnlen) //若当前路径更长，将路径保存在1ongpatn中for(i-pathlen-1;i>-8;i--)longpath[i]=path[1];longpathlen-pathlen;elsepath[pathlen]=b->data; pathlen4; //将当前结点放入路径中//路径长度增1iongPath(b->lchild,path₇pathlen,langpath,longpathien);//递归扫描左子树LongPath(b->rchiid,path,pathien,longpath,longpathien);//递归扫描石子树pathlen--; /7饮其环境oid DispLeaf(BTNode xb)- 口凶uoid DispLeaf(BTNode xb)iE(D!=NULL){ if(b->1child--HULL B& b->rchild--HULL)printf("3c“,b->data);elsepispLeaf(b->ichild);DispLeaf(b->rchild);oid nain()8TNodexb;ElenType patn[Maxsize],longpath[Maxsize];int i.longpathien-U;CreateBTNode(b,"A(B(D,E(H(J,K(L,H(,N))))),C(F,G(,I)))");printf("\n二灾树b:");DispBTNode(b);printf("\n\n*);printf(”b的叶子结点：");DispLeaf(b);printf("\n\n");printf("A11Path:");A11Path(b);printf("m");printf("AiiPath1:n");AliPath1(b.path.);printf("");LongPath(b,path,8,longpath,longpathlen);printf(”第一条量长路径长度=d\n”,longpathlen);printf(”"第一茶最长路径：");for(i=longpathlen;i>=0;i--)printf("c",longpatn[1]);printf("\n\n");。

实验报告二叉树求叶子结点数目实验目的：1.理解二叉树的概念和基本操作。

2.学会使用递归算法实现对二叉树的遍历和操作。

实验内容：给定一个二叉树，求其叶子结点的数目。

实验原理：二叉树是一种常用的数据结构，其所有节点的度不超过2、对于二叉树的遍历，有三种常见的方式：前序遍历、中序遍历和后序遍历。

其中，前序遍历是先访问根节点，然后依次访问左子树和右子树；中序遍历是先访问左子树，然后访问根节点，最后访问右子树；后序遍历是先访问左子树，然后访问右子树，最后访问根节点。

根据二叉树的定义，叶子结点即没有子节点的节点，可以通过递归的方式遍历二叉树来求解叶子结点的数目。

具体操作如下：1. 创建一个变量count，用于记录叶子结点的数目，初始值为0。

2.若当前节点为空，则返回0。

3. 若当前节点没有左子树和右子树，则说明当前节点是叶子结点，count加14. 若当前节点有左子树，则递归调用函数求解左子树的叶子结点数目，并将结果加到count上。

5. 若当前节点有右子树，则递归调用函数求解右子树的叶子结点数目，并将结果加到count上。

6. 返回count作为结果。

实验步骤：1.创建一个二叉树的类，包括节点类和二叉树类，定义根节点和相关操作方法。

2. 在二叉树类中定义一个递归函数countLeafNodes，用于求解叶子结点的数目。

3. 在countLeafNodes函数中实现上述的递归算法。

4.在主函数中创建一个二叉树对象，并插入一些节点。

5. 调用countLeafNodes函数，输出叶子结点的数目。

实验结果：经过测试，结果正确。

实验总结：通过本次实验，我进一步理解了二叉树的概念和基本操作，并学会了使用递归算法实现对二叉树的遍历和操作。

特别是通过实现统计叶子结点数目的功能，我对递归算法有了更深入的理解。

在实验过程中，我也遇到了一些问题，例如如何正确地进行前序遍历，并正确判断叶子结点。

通过查阅资料和与同学的讨论，我逐渐解决了这些问题。

二叉树结点计算公式二叉树结点的计算公式及解释1. 二叉树的节点个数•公式：N = 2^h - 1，其中 N 表示二叉树的节点个数，h 表示二叉树的高度。

•解释：二叉树的高度 h 可以通过树的层数来确定，根节点所在的层数为 1，依次往下递增。

每个节点都可以有两个子节点，所以二叉树的节点个数 N 可以通过计算 2 的 h 次方再减去 1 来得出。

例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算节点个数：h = 3，2^3 - 1 = 8 - 1 = 7所以，该二叉树的节点个数为 7。

2. 二叉树的叶子节点个数•公式：L = (N + 1) / 2，其中 L 表示二叉树的叶子节点个数，N 表示二叉树的节点个数。

•解释：在二叉树中，叶子节点是指没有子节点的节点。

根据二叉树的性质，每个节点最多有两个子节点，所以二叉树的叶子节点个数可以通过节点个数加 1 再除以 2 来计算。

例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算叶子节点个数：N = 7，(7 + 1) / 2 = 8 / 2 = 4所以，该二叉树的叶子节点个数为 4。

3. 二叉树的高度•公式：h = log2(N + 1)，其中 h 表示二叉树的高度，N 表示二叉树的节点个数。

•解释：由于二叉树中每个节点都可以有两个子节点，所以可以通过节点个数 N 加 1 后取对数以 2 为底的对数来计算二叉树的高度。

例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算高度：N = 7，log2(7 + 1) ≈ log2(8) ≈ 3所以，该二叉树的高度为 3。

以上就是关于二叉树结点的计算公式及解释。

通过这些公式，我们可以更方便地计算二叉树的相关属性，进而优化算法或者进行更深入的研究。

统计二叉树的结点数和叶子结点数的试验报告试验报告：统计二叉树的节点数和叶子节点数一、引言二叉树是一种常用的数据结构，它由节点构成，每个节点最多有两个孩子节点。

在实际应用中，经常需要对二叉树进行统计，比如统计其节点数和叶子节点数。

本试验的目的是通过编写算法，实现对二叉树的节点数和叶子节点数的统计，并对此进行详细的测试和分析。

二、设计思想本试验采用递归的方法来统计二叉树的节点数和叶子节点数。

具体思想如下：1.统计节点数：对于任意一个二叉树，其节点数等于左子树的节点数加上右子树的节点数加1（根节点）。

通过递归的方式，可以遍历每个节点，并进行累加。

2.统计叶子节点数：叶子节点是指没有孩子节点的节点，即左右子树均为空。

通过递归的方式，可以遍历每个节点，当遇到叶子节点时，统计数值加一三、实验过程1.设计二叉树数据结构：首先，根据设计思想，我们需要设计一个二叉树的数据结构，并提供相应的操作接口。

这里我们使用C++语言来实现。

2.编写递归算法：在设计好二叉树数据结构后，编写递归算法来统计节点数和叶子节点数。

具体实现思路参考设计思想中的描述，分别统计左子树、右子树和根节点即可。

3.编写测试代码：为了验证算法的正确性，我们需要编写相应的测试代码。

测试代码需要构建不同的二叉树，并分别统计节点数和叶子节点数，然后与预期结果进行对比。

4.运行测试并分析结果：运行测试代码，观察输出结果是否与预期结果一致。

如果不一致，需要检查代码逻辑是否有误，并进行修正。

四、实验结果与分析在设计好二叉树数据结构并编写测试代码后，我们进行了多组测试，并统计了节点数和叶子节点数。

下面以一个测试用例为例，详细分析实验结果。

测试用例：构建二叉树如下：/\23//\456/\78预期结果：节点数：8叶子节点数：4实际结果：节点数：8叶子节点数：4分析：通过对比预期结果和实际结果，可以得出结论，本算法能够正确地统计二叉树的节点数和叶子节点数。

五、总结本试验通过设计二叉树数据结构和编写递归算法，实现了对二叉树的节点数和叶子节点数的统计。

二叉树叶子节点数计算公式在计算机科学领域，二叉树是一种非常常见的数据结构，它由节点组成，每个节点最多有两个子节点。

其中，叶子节点是指没有子节点的节点，它们位于二叉树的末端。

计算二叉树的叶子节点数是一个常见且重要的问题，本文将介绍如何通过简单的方法来计算二叉树的叶子节点数。

我们需要了解二叉树的结构。

二叉树可以分为左子树和右子树，每个节点都有一个左子节点和一个右子节点（如果存在的话）。

叶子节点是指没有左子节点和右子节点的节点。

因此，计算二叉树的叶子节点数可以通过遍历整个二叉树并统计叶子节点的数量来实现。

一种简单的方法是使用递归。

通过递归地遍历二叉树的每个节点，我们可以轻松地计算出叶子节点的数量。

具体来说，我们可以按照以下步骤来计算叶子节点数：1. 从根节点开始，如果当前节点为空，则返回0。

2. 如果当前节点是叶子节点（即没有左子节点和右子节点），则返回1。

3. 否则，递归地计算左子树和右子树的叶子节点数，并将它们相加。

通过以上步骤，我们可以得到整个二叉树的叶子节点数。

这种方法简单直观，适用于大多数二叉树的情况。

除了递归方法外，我们还可以使用迭代方法来计算二叉树的叶子节点数。

迭代方法通常需要借助数据结构（如栈或队列）来辅助计算。

具体步骤如下：1. 初始化一个栈，并将根节点入栈。

2. 循环遍历栈，直到栈为空。

3. 每次弹出栈顶节点，并检查其是否为叶子节点。

如果是，则将叶子节点计数加一。

4. 如果当前节点有左子节点，则将左子节点入栈；如果有右子节点，则将右子节点入栈。

通过迭代方法，我们也可以得到二叉树的叶子节点数，这种方法在某些情况下可能更有效。

在实际应用中，计算二叉树的叶子节点数是一个常见的问题，它可以帮助我们更好地理解和分析二叉树的结构。

通过掌握递归和迭代两种方法，我们可以灵活地解决这类问题，并深入理解二叉树的特性。

通过本文介绍的方法，我们可以轻松计算二叉树的叶子节点数，这对于深入学习数据结构和算法有着重要的意义。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。