下载文档原格式
北京物资学院信息学院实验报告课程名数据结构(C++)实验实验名称二叉树算法的实现实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ _______ 学号___一、实验目的1.掌握二叉树的存储的结构；2. 掌握建立二叉树的算法；3. 掌握对二叉树的遍历算法；4. 掌握二叉搜索树的算法；5. 掌握建立哈夫曼树和哈夫曼编码的算法；二、实验内容基本部分1. 采用广义表形式建立二叉树(参考图5-11(a)和/或图5-13(a))；2. 对已建立的二叉树，进行先、中、后序和按层遍历；3. 用广义表形式输出二叉树；4. 【习题5-3】1, 2 (2题选作)【提示：参考递归遍历算法】；特殊二叉树部分1．用插入算法建立一棵二叉搜索树，原始数据为：{30,50,20,40,25,70,54,23,80,92}，并中序遍历该树、查找其中的元素；2. 构造一棵叶子结点权值分别为3，5，6，7，9，13，21的哈夫曼树；3. 对2题进行哈夫曼编码。
三、实验地点与环境3.1 实验地点(南实验楼教室)3.2实验环境(所用语言环境)四、实验步骤1.2.3.…五、实验结果与分析5.1 实验结果(原始数据，预期结果和运行结果)序号算法名称(函数名) 所在头文件名原始数据与与功能主函数所在文件名运行结果*1 函数名：功能：头文件：CPP文件：原始数据：运行结果：23* 如果不能按“原始数据”、“运行结果”列出数据则不列，必要时在“分析”部分说明5.2 分析（选择部分算法分析，包括函数参数说明、调试中所遇到的问题和解决方法、中间结果等，必要时给出函数和主函数的关键段落。
所选算法应是：重要的算法、有编程特点的算法等）六、小结（收获与心得）。
实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容1、问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：(1). 按先序序列构造一棵二叉链表表示的二叉树T；(2). 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；(3). 求二叉树的深度/结点数目/叶结点数目；(选做)(4). 将二叉树每个结点的左右子树交换位置。
（选做）2、基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。
3、测试数据如输入：abc00de0g00f000（其中ф表示空格字符）则输出结果为：先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代码#include<malloc.h>#include<iostream.h>#define OK 1#define ERROR -1typedef char TElemType;int i;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int CreateBiTree(BiTree&T) //创建二叉树{char a;cin>>a;if(a=='0') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {return ERROR;}T->data=a;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}int PreOrderTraverse(BiTree&T) //先序遍历二叉树{if(T){//cout<<"此为先序遍历"<<endl;cout<<T->data<<"->";if(PreOrderTraverse(T->lchild))if(PreOrderTraverse(T->rchild))return OK;return ERROR;}else return OK;}int InOrderTraverse(BiTree&T) //中序遍历二叉树{if(T){//cout<<"此为中序遍历"<<endl;if(InOrderTraverse(T->lchild)){cout<<T->data<<"->";if(InOrderTraverse(T->rchild))return OK;}return ERROR;}else return OK;}int PostOrderTraverse(BiTree&T) //后序遍历二叉树{if(T){//cout<<"此为后序遍历"<<endl;if (PostOrderTraverse(T->lchild))if(PostOrderTraverse(T->rchild)){cout<<T->data<<"->";i++;return (OK);}return (ERROR);}elsereturn (OK);}int CountDepth(BiTree&T) //计算二叉树的深度{if(T==NULL){return 0;}else{int depl=CountDepth(T->lchild);int depr=CountDepth(T->lchild);if(depl>depr){return depl+1;}else{return depr+1;}}}void main() //主函数{BiTree T;cout<<"请输入二叉树节点的值以创建树"<<endl;CreateBiTree(T);cout<<"此为先序遍历";PreOrderTraverse(T);cout<<"end"<<endl;cout<<"此为中序遍历";InOrderTraverse(T);cout<<"end"<<endl;cout<<"此为后序遍历";PostOrderTraverse(T);cout<<"end"<<endl<<"此树节点数是"<<i<<endl<<"此树深度是"<<CountDepth(T)<<endl;}四、调试结果及运行界面：五、实验心得通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。
数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。
具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。
二、实验原理树是一种非线性的数据结构，由结点和边组成。
树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。
树的基本操作包括插入、删除和查找。
在本次实验中，我们采用二叉树作为实现树的数据结构。
二叉树是一种特殊的树，每个结点最多只有两个子结点。
根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。
三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。
然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。
2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。
我们可以通过递归的方式实现插入操作。
具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。
如果当前结点为空，则将新的结点作为当前结点。
3. 实现删除操作删除操作是将指定的结点从树中移除的过程。
我们同样可以通过递归的方式实现删除操作。
具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。
如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。
- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。
- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。
4. 实现查找操作查找操作是在树中寻找指定值的过程。
同样可以通过递归的方式实现查找操作。
具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。
数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。
实验目的1、掌握用递归方法实现二叉树的遍历。
2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。
题目：(1)编写二叉树的遍历操作函数。
①先序遍历，递归方法re_preOrder(TREE *tree)②中序遍历，递归方法re_midOrder(TREE *tree)③后序遍历，递归方法re_postOrder(TREE *tree)(2)调用上述函数实现先序、中序和后序遍历二叉树操作。
算法设计分析（一）数据结构的定义要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。
二叉树型存储结构定义为：typedef struct TNode{ char data;//字符型数据struct TNode *lchild,*rchild;//左右孩子指针}TNode,* Tree;（二）总体设计程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。
其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能。
int main()（2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。
int CreateBiTree(Tree &T)（3）先序遍历函数：将所建立的二叉树先序遍历输出。
void PreOrder(Tree T)（4）中序遍历函数：将所建立的二叉树中序遍历输出。
void InOrder(Tree T)（5）后序遍历函数：将所建立的二叉树后序遍历输出。
void PostOrder(Tree T)（三）各函数的详细设计：（1）建立一个二叉树，按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树。
对T动态分配存储空间，生成根节点，构造左、右子树（2）编写先序遍历函数，依次访问根节点、左子结点、右子节点（3）编写中序遍历函数，依次访问左子结点、根节点、右子节点（4）编写后序遍历函数，依次访问左子结点、右子节点、根节点（5）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。
二叉树的基本操作实验报告学号姓名实验日期 2012-12-26实验室计算机软件技术实验指导教师设备编号 401实验内容二叉树的基本操作一实验题目实现二叉树的基本操作的代码实现二实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求(1)认真阅读书上给出的算法(2)编写程序并独立调试四、给出二叉树的抽象数据类型ADT BinaryTree{//数据对象D:D是具有相同特性的数据元素的集合。
//数据关系R:// 若D=Φ，则R=Φ，称BinaryTree为空二叉树;// 若D?Φ，则R={H}，H是如下二元关系;// (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1，<root,x1>?H，且存在D1上的关系H1 ?H;若Dr?Φ，则Dr中存在惟一的元素xr，<root,xr>?H，且存在上的关系Hr ?H;H={<root,x1>,<root,xr>,H1,Hr};// (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。
//基本操作:CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。
// 操作结果:按definiton构造二叉树T。
BiTreeDepth( T )// 初始条件:二叉树T存在。
// 操作结果:返回T的深度。
PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。
TextFile中。
(4) P：打印代码文件(Print)。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
(5) T：打印哈夫曼树(Tree printing)。
将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
3) 实现提示：(1) 文件CodeFile的基类型可以设为字节型。
(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。
请用户键入一个选择功能符。
此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。
(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。
每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
三、实验过程与实验结果实验3-01：以二叉链表为存储结构，实现二叉树的创建、遍历数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。
2.利用非递归实现中序遍历，需要利用栈操作，按照中序遍历规则将节点依次入栈后出栈实现。
算法描述：图1 中序遍历（非递归）实现算法的实现和测试结果（参考OJ）实验3-02：编写算法交换二叉树中所有结点的左、右子树数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。
二叉树的各种基本运算的实现实验报告
一、实验目的
实验目的为了深入学习二叉树的各种基本运算，通过操作实现二叉树的建立、存储、查找、删除、遍历等各种基本运算操作。
二、实验内容
1、构造一个二叉树。
我们首先用一定的节点来构建一棵二叉树，包括节点的左子节点和右子节点。
2、实现查找二叉树中的节点。
在查找二叉树中的节点时，我们根据二叉树的特点，从根节点开始查找，根据要查找的节点的值与根节点的值的大小的关系，来决定接下来查找的方向，直到找到要查找的节点为止。
3、实现删除二叉树中的节点。
在删除二叉树节点时，我们要做的是找到要删除节点的父节点，然后让父节点的链接指向要删除节点的子节点，有可能要删除节点有一个子节点，有可能有两个极点，有可能没有子节点，我们要根据每种情况进行处理，来保持二叉树的结构不变。
4、对二叉树进行遍历操作。
二叉树的遍历有多种方法，本实验使用的是先序遍历。
首先从根节点出发，根据先序遍历的顺序，先访问左子树，然后再访问右子树，最后访问根节点。
三、实验步骤
1、构建二叉树：
我们用一个数组代表要构建的二叉树，第一项为根节点，第二项和第三项是根节点的子节点。
二叉树基本操作实验报告实验名称二叉树基本操作实验目的1.熟悉二叉树结点的结构和二叉树的基本操作；2.掌握二叉树每种操作的具体实现；3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法；4.在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法；5.掌握构造哈夫曼树以及哈夫曼编码的方法。
实验内容编制一个演示二叉树创建、遍历、计算等操作的程序。
问题描述用数据结构相关知识，实现二叉树的定义和操作。
该程序包括二叉树结构类型以及对二叉树操作的具体的函数定义（包括：初始化二叉树、清空二叉树、检查二叉树是否为空、遍历二叉树（先序、后序、中序、层次）、求二叉树的深度、求二叉树所有节点数）。
问题分析该实验是基于C语言和数据结构知识基础的对二叉树的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。
因此，我直接按要求定义了对二叉树操作的具体函数，并于主函数中实现对应的功能调用，其中，功能选择靠switch语句实现。
实验步骤1．需求分析本演示程序用VC++编写，完成二叉树的生成、遍历、计算等基本操作。
①输入的形式和输入值的范围：以字符（其中‘#’表示虚节点）的形式输入，以创建二叉树；在输入二叉树节点前，必须先确定该序列能正确创建二叉树。
②输出的形式：在所有三种操作中都显示操作是否正确以及操作后二叉树的内容。
③程序所能达到的功能：完成二叉树的生成、遍历（包括先序、后序、中序、层次四种方式）、计算等基本操作。
④测试数据：创建操作中依次输入a,b,d,#,g,#,#,#,c,e,#,#,f,#,#生成一个二叉树。
2．概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT BitTree {数据对象：由一个根节点和两个互不相交的左右子树构成数据关系：结点具有相同的数据类型及层次结构基本操作：Void BinTreeInit(BitTree *T)初始条件：无操作结果：初始化一棵二叉树Void BinTreeCreat(BitTree *T)初始条件：二叉树T已存在操作结果：按先序次序创建一棵二叉树2）本程序包含7个函数：①主函数main() ②初始化二叉树函数BinTreeInit() ③建立一棵二叉树函数BinTreeCreat() ④先序遍历函数PreOrderTraverse() ⑤中序遍历函数InOrderTraverse()⑥后序遍历函数PostOrderTraverse()⑦层次遍历函数LevelOrderTraverse()⑧求二叉树深度函数Countlevel()⑨检验空树函数BinTreeEmpty()⑩求节点数函数 Countnode()函数说明#include<stdio.h>#include<stdlib.h>typedef char Datatype;typedef struct NodeType{Datatype data;struct NodeType *lchild;struct NodeType *rchild;}BiTNode;typedef BiTNode * BinTree;//初始化二叉树。
数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。
在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。
实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。
2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。
3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。
4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。
5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。
二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。
节点被表示为一个由数据和指向其左右子节点的指针组成的结构。
二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。
二叉树可以用链式存储结构或顺序存储结构表示。
- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。
- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。
二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。
我们可以通过手动输入或读取外部文件中的数据来创建二叉树。
对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。
对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。
一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。
2. 创建子节点，并到父节点。
3. 重复步骤2，直到创建完整个二叉树。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。
删除B 后，以广义表形式打印A （，C （F （，G ）））二、 概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。
1、设定“二叉树”的抽象数据类型定义：ADT BiTree{数据对象D ：D 是具有相同特性的数据元素的集合。
数据关系R ：若 Φ=D ，则Φ=R ，称BiTree 为空二叉树；若 Φ≠D ，则{}H R =，H 是如下二元关系：（1） 在D 中存在唯一的称为根的数据元素root ，它在关系H 下无前驱；（2） 若{} ,Φ≠-root D 则存在{}{},,r l D D root D =-且Φ=⋂r l D D ;（3） 若,Φ≠l D 则l D 中存在唯一的元素l x ,,,H x root l >∈<且存在l D 上的关系;H H l ⊂若,Φ≠r D 则r D 中存在唯一的元素r x ,,,H x root r >∈<且存在r D 上的关系{}r l r l r H H x root x root H H H ,,,,,;><><=⊂；（4） {}()l l H D ,是一棵符合本定义的二叉树，称为根的左子树，{}()r r H D ,是一棵符合本定义的二叉树，称为根的有字树基本操作：CreateBiTree&T)操作结果：按照T 的定义构造一个二叉树。
BiTreeDepth(& T)初始条件：二叉树T 已存在。
操作结果：返回T 的深度。
BiTreeWidth(&T)初始条件：二叉树T 已存在。
操作结果：返回T 的宽度。
PreOderTraverse&T)初始条件：二叉树T 已存在。
操作结果：先序遍历打印T ，InOderTraverse(&T)初始条件：二叉树T 已存在。
操作结果：中序遍历打印T 。
PostOderTraverse(&T)初始条件：二叉树T 已存在。
操作结果：后序遍历打印T 。
LevelTraverse(&T)初始条件：二叉树T 已存在。
操作结果：层次遍历T 。
DeleteXTree(&T,TElemType x)初始条件：二叉树已存在。
操作结果：删除元素为x 的结点以及其左子树和右子树。
CopyTree(&T)初始条件：二叉树T 已存在。
操作结果：以T 为模板，复制另一个二叉树。
｝ADT BiTree2、设定队列的抽象数据类型定义：ADT Queue{数据对象：D={i a },+∈∈N i BiTree a i 数据关系：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定1a 端为队列头，n a 端为队列尾。
基本操作：InitQueue(&Q)操作结果：构造一个空队列Q 。
EnQueue(&Q,&e)初始条件：队列Q 已存在。
操作结果：插入元素e 为Q 的新的队尾元素。
DeQueue(&Q)初始条件：队列Q 已存在。
操作结果：删除Q 的对头元素，并返回其值。
QueueEmpty(&Q)初始条件：队列Q 已存在。
操作结果：若Q 为空队列，则返回1，否则0。
} ADT Queue3、本程序包含四个模块1）主程序模块void main( ){初始化；先序输入二叉树各结点元素；各种遍历二叉树；对二叉树进行常见运算；复制二叉树；在复制的二叉树上进行二叉树的常见操作；｝2）二叉树模块——实现二叉树的抽象数据类型和基本操作2）队列模块——实现队列的抽象数据类型及今本操作3）广义表打印模块——以广义表形式打印二叉树4）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数三、 详细设计1、主程序中需要的全程量#define M 10 // 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度2、队列的建立与基本操作typedef struc t QNode{BiTree data; //队列中存储的元素类型struct QNode *next; //指向二叉树结点的指针}QNode,*Queueptr;typedef struct{Queueptr front; //队列的队头指针Queueptr rear; //队列的队尾指针}LinkQueue;算法描述：为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到队列。
而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。
伪码算法：void InitQueue(LinkQueue *Q){//初始化队列申请一个结点Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));if(!Q->front)exit(1);//存储分配失败处理Q->front->next=NULL;//构成带头结点里的空链队列}void EnQueue(LinkQueue *Q,BiTree e){//插入元素为e为Q的队尾元素Queueptr q;q=(Queueptr)malloc(sizeof(QNode));if(!q)exit(1);q->data=e;q->next=NULL;Q->rear->next=q; //元素e的结点入列Q->rear=q;}BiTree DeQueue(LinkQueue *Q){//从队列中删除队头元素，并直接返回给调用的主函数Queueptr p;BiTree q;if(Q->front==Q->rear){//队列为空printf("ERROR!\n");exit(1);}p=Q->front->next;q=p->data;Q->front->next=p->next; //删除该结点if(Q->rear==p)Q->rear=Q->front;free(p);return q;//返回队头元素}int QueueEmpty(LinkQueue *Q){//检查队列是否为空，若为空则返回真值，否则返回0if(Q->front==Q->rear)return 1;elsereturn 0;}3、二叉树的建立与基本操作typedef struct BiTNode{TElemType data; //二叉树结点存储的元素类型struct BiTNode *lchild,*rchild; //二叉树左右孩子指针}BiTNode,*BiTree;算法分析：二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。
1）二叉树的遍历算法描述：二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。
即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。
因此，若能依次遍历这三部分，便是遍历了整棵二叉树。
如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。
若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。
中（根）序遍历和后（根）序遍历。
基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。
先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
伪码算法：void PreOderTraverse(BiTree T){//采用二叉链表存储结构if(T){putchar(T->data);//最简单的访问结点法，输出结点元素，这里先访问根结点PreOderTraverse(T->lchild);PreOderTraverse(T->rchild);}}中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
伪码算法：void InOderTraverse(BiTree T){//采用二叉链表存储结构if(T){InOderTraverse(T->lchild);//先遍历左子树putchar(T->data);// 最简单的访问结点法，输出结点元素，这里第二访问根结点InOderTraverse(T->rchild);}}后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
