下载文档原格式
实验报告二叉树求叶子结点数目实验目的：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 页共4 页
五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）
这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。
通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。
在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。
如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。
例如进行二叉树的遍历的时候，要先理解各种遍历的特点。
先序遍历是先遍历根节点，再依次先序遍历左右子树。
中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。
而后序遍历则是先依次后续遍历左右子树，再访问根节点。
掌握了这些，在实验中我们就可以融会贯通，举一反三。
其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。
第 3 页共4 页
第 4 页共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）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。
A
B
C D
E F
G
主程序模块
结点单元模块构建先序二叉树模块
二叉树遍历模块
main
CreatBTree Preorder Inorder Postorde
程序的功能设计、数据结构设计及整体结构
设计合理； 程序运行情况良好， 算法说明清 晰，理论分析与计算正确，实验数据无误 熟练使用开辟工具， 能够迅速准确的进行调
试、纠错和运行
良好的编程风格(缩进，注释，变量名、函
数名见名知意等，程序运行界面友好)
提交的电子文档及打印文档的书写、存放符
合规范化要求
能简明扼要地阐述设计的主要内容， 能准确
流利地回答各种问题
端正的学习态度及认真刻苦程度等
30
20
10
10
20
10。
《数据结构》实验报告四实验内容：建一个二叉树并对其进行遍历，并求出该树的叶子数和深度学号： 20105101256 姓名：肖丽芳一、上机实验的问题和要求（需求分析）：[ 题目]1从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
2 求该二叉数的深度、并统计叶子结点的个数。
二、程序设计的基本思想，原理和算法描述：根据先序遍历的性质，先建立头结点，再建立左右子树，利用递归算法，先序建立二叉树。
对树进行遍历时，根据先序、中序、后序不同的算法，将输出不同的序列。
求树的叶子数和深度是要判断树是否为空，然后依据算法看左右孩子。
三、调试和运行程序过程中产生的问题及采取的措施：写主函数时注意不要抄写错误，尤其是大小写，注意函数的调用四、源程序及注释[ 源程序] 程序名：二叉树#include<stdio.h>#include<process.h>#include<malloc.h>#define ERROR 0#define OK 1#define OVERFLOW -1#define NULL 0typedef int Status;typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;//二叉树的二叉链表存储表示BiTree CreatBiTree(BiTree T){//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空数//构造二叉连表表示的二叉树Tchar ch;scanf("%c",&ch);if(ch=='#') T=NULL;//用#表示空指针else{T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;//生成根结店T->lchild=CreatBiTree(T->lchild); //生成左子树T->rchild=CreatBiTree(T->rchild);//生成右子树}return T;}//createbitreevoid Preorder(BiTree T){if(T!=NULL){//树非空printf("%c",T->data);//访问根结点Preorder(T->lchild);//先序遍历左子树Preorder(T->rchild);//先序遍历右子树}}//先序遍历二叉树void Inorder(BiTree T){if(T!=NULL){//树非空Inorder(T->lchild);//中序遍历左子树printf("%c",T->data);//访问根结点Inorder(T->rchild);//中序遍历右子树}}//中序遍历二叉树void Postorder(BiTree T){if(T!=NULL){//树非空Postorder(T->lchild);//后序遍历左子树Postorder(T->rchild);//后序遍历右子树printf("%c",T->data);//访问根结点}}//后序遍历二叉树int Leaf_Count(BiTree T){//求二叉树中叶子结点的数目if(!T) return 0;//空树没有叶子else if(!T->lchild &&!T->rchild ) return 1;//叶子节点else returnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}int Height(BiTree T){int m,n;if(T==NULL) return 0;//空数深度为0else {m=Height(T->rchild);//m为右孩子的深度n=Height(T->lchild);//n为左孩子的深度if(m>n)return(m+1);//如果右孩子的深度大于左孩子的深度则右孩子m+1else return(n+1);//否则左孩子n+1}}void main(){BiTree T=NULL;T=CreatBiTree(T);int depth;int Leaf;printf("先序遍历的顺序是");Preorder(T); printf("\n");printf("中序遍历的顺序是");Inorder(T);printf("\n");printf("后序遍历的顺序是");Postorder(T);printf("\n");Leaf=Leaf_Count(T);printf("此二叉树的叶子数为：%d\n",Leaf);depth=Height(T);printf("此二叉树的深度为：%d\n",depth); }五、运行结果ABC##DE#G##F###先序遍历的顺序是：ABCDEGF中序遍历的顺序是：CBEGDFA后序遍历的顺序是：CGEFDBA此二叉树的叶子数为：3此二叉树的深度为：5Press any key to conntinue。
二叉树递归遍历数据结构实验报告一、引言二叉树是一种简单而重要的树形结构，在计算机科学领域中被广泛应用。
它具有良好的动态性能和数据组织能力，递归遍历是二叉树最基本的操作之一、本次实验旨在通过编程实现二叉树的递归遍历算法，并对实验结果进行分析和总结。
二、实验目的1.掌握二叉树的基本概念和操作方法；2.熟悉递归算法的实现过程；3.实践二叉树的递归遍历算法。
三、实验原理1.二叉树的概念二叉树是一种树形结构，其中每个节点最多有两个子节点，被分为左子树和右子树。
树中每个节点最多有一个父节点，除了根节点没有父节点。
二叉树的递归定义：（1）空树是一个二叉树；（2）一棵非空二叉树由根节点和左子树、右子树组成。
2.二叉树的递归遍历二叉树的遍历方式分为三种：前序遍历、中序遍历和后序遍历。
其定义如下：（1）前序遍历：根节点->左子树->右子树；（2）中序遍历：左子树->根节点->右子树；（3）后序遍历：左子树->右子树->根节点。
四、实验过程1.定义二叉树的数据结构和相关操作方法首先，我们需要定义二叉树的节点结构，包含数据域和左右子节点指针域。
然后，可定义插入节点、删除节点等操作方法。
2.实现递归遍历算法（1）前序遍历前序遍历的流程为：先访问根节点，再前序遍历左子树，最后前序遍历右子树。
通过递归调用即可实现。
伪代码如下：```void preOrder(Node* root)if (root != NULL)cout << root->data;preOrder(root->left);preOrder(root->right);}（2）中序遍历和后序遍历与前序遍历类似，中序遍历的流程为：先中序遍历左子树，再访问根节点，最后中序遍历右子树。
后序遍历的流程为：先后序遍历左子树，再后序遍历右子树，最后访问根节点。
也可以通过递归调用实现。
伪代码如下：```void inOrder(Node* root)if (root != NULL)inOrder(root->left);cout << root->data;inOrder(root->right);}void postOrder(Node* root)if (root != NULL)postOrder(root->left);postOrder(root->right);cout << root->data;}五、实验结果与分析我们通过编写测试数据并调用递归遍历算法进行遍历，得到以下结果：（1）前序遍历结果：ABDECFG（2）中序遍历结果：DBEAFCG（3）后序遍历结果：DEBFGCA实验结果与预期相符，表明递归遍历算法编写正确。
数据结构实验报告1. 实验目的和内容：掌握二叉树基本操作的实现方法2. 程序分析2.1存储结构链式存储2．程序流程2.3关键算法分析算法一：Create(BiNode<T>* &R,T data[],int i,int n)【1】算法功能：创建二叉树【2】算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树【3】算法空间时间复杂度分析：O(n)【4】代码逻辑：如果位置小于数组的长度则{ 创建根结点将数组的值赋给刚才创建的结点的数据域创建左子树，如果当前结点位置为i,则左孩子位置为2i创建右子树，如果当前结点位置为i,则右孩子位置为2i+1}否则R为空算法二：CopyTree(BiNode<T>*sR,BiNode<T>* &dR)）【1】算法功能：复制构造函数【2】算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。
【3】算法空间时间复杂度分析：O（n)【4】代码逻辑:如果源二叉树根结点不为空则{创建根结点调用函数自身，创建左子树调用函数自身，创建右子树}将该函数放在复制构造函数中调用，就可以实现复制构造函数算法三：PreOrder(BiNode<T>*R)【1】算法功能：二叉树的前序遍历【2】算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。
【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）如果当前结点为非空，则{访问当前结点当前结点入栈将当前结点的左孩子作为当前结点}如果为空{则栈顶结点出栈则将该结点的右孩子作为当前结点}反复执行这两个过程，直到结点为空并且栈空算法四：InOrder(BiNode<T>*R)【1】算法功能：二叉树的中序遍历【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R为非空：则调用函数自身遍历左孩子访问该结点再调用自身访问该结点的右孩子算法五：LevelOrder(BiNode<T>*R)【1】算法功能：二叉树的层序遍历【2】算法基本思想：【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）：如果队列不空{对头元素出队访问该元素若该结点的左孩子为非空，则左孩子入队；若该结点的右孩子为非空，则右孩子入队；}算法六：Count(BiNode<T>*R)【1】算法功能：计算结点的个数【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R不为空的话{调用函数自身计算左孩子的结点数调用函数自身计算右孩子的结点数}template<class T>int BiTree<T>::Count(BiNode<T>*R){if(R==NULL)return 0;else{int m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;}}算法七：Release(BiNode<T>*R)【1】算法功能：释放动态内存【2】算法基本思想：左右子树全部释放完毕后再释放该结点【3】算法空间时间复杂度分析：未知【4】代码逻辑：调用函数自身，释放左子树调用函数自身，释放右子树释放根结点释放二叉树template<class T>void BiTree<T>::Release(BiNode<T>*R) {if(R!=NULL){Release(R->lchild);Release(R->rchild);delete R;}}template<class T>BiTree<T>::~BiTree(){Release(root);}int main(){BiTree<int> BTree(a,10);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root);cout<<endl;Tree.PreOrder(Tree.root);cout<<endl;BTree.InOrder(BTree.root);cout<<endl;Tree.InOrder(Tree.root);cout<<endl;BTree.PostOrder(BTree.root);cout<<endl;Tree.PostOrder(Tree.root);cout<<endl;BTree.LevelOrder(BTree.root);cout<<endl;Tree.LevelOrder(Tree.root);cout<<endl;int m=BTree.Count(BTree.root);cout<<m<<endl;return 0;}3.测试数据：int a[10]={1,2,3,4,5};1 2 4 5 31 2 4 5 34 25 1 34 5 2 3 11 2 3 4 554.总结：4.1:这次实验大多用了递归的算法，比较好理解。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。
齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入）14-1 实验地点学生姓名高晨悦学号201403071007 同组人无实验项目名称二叉树的递归算法一、实验目的和要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。
2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。
二、实验环境微型计算机vc 6.0三、实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。
2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。
四、实验步骤一．实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。
2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。
二．程序的设计思想1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。
先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。
（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。
（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历：（a）访问根结点；（b）先序遍历左子树；（c）先序遍历右子树。
中序遍历：（a）中序遍历左子树；（b）访问根结点；（c）中序遍历右子树后序遍历：（a）后序遍历左子树；（b）后序遍历右子树；（c）访问根结点。
2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。
（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。
（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。
（3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。
否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。
（4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。
三．编程过程中遇到的问题及解决办法（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。
（2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。
四．程序的闪光点(自我评价)1.程序模块化，各个函数分开描述，方便观察2.关键处有注释3.建立二叉树时，用先序提示输入，比较人性化。
五．程序源代码(以文件为单位提供)#include<iostream.h>#include<malloc.h>#define Maxsize 100typedef struct TREE{struct TREE *lTree;struct TREE *rTree;char data;}Tree;void InitTree(Tree*);//初始化树void CreatTree(Tree*);//创建二叉树void PreTraverse(Tree*);//先序遍历递归void PreOrderTraverse(Tree*);//先序遍历非递归void InTraverse(Tree *tree);//中序遍历递归void InOrderTraverse(Tree *tree);//中序遍历非递归void PostTraverse(Tree *tree);//后序遍历递归void LastOrderTraverse(Tree *tree);//后序遍历非递归int DepthTree(Tree *tree);//计算树的深度int LeafsTree(Tree *tree);//计算叶子结点个数int NodesTree(Tree *tree);//计算结点个数int Twochild(Tree*tree);//计算度为二的结点个数void main(){int H,L;Tree tree;// Tree m;InitTree(&tree);CreatTree(&tree);cout<<"先序遍历递归为:";PreTraverse(&tree);//先序遍历递归cout<<"先序遍历非递归:";PreOrderTraverse(&tree);//先序遍历非递归cout<<endl;cout<<"中序遍历递归为:";InTraverse(&tree);//中序遍历递归cout<<"中序遍历非递归:";InOrderTraverse(&tree);//中序遍历非递归cout<<endl;cout<<"后序遍历递归为:";PostTraverse(&tree);//后序遍历递归cout<<"后序遍历非递归:";LastOrderTraverse(&tree);//后序遍历非递归cout<<endl;cout<<"树的深度为:";H=DepthTree(&tree);.cout<<H<<endl;cout<<"叶子结点个数:";L=LeafsTree(&tree);cout<<L<<endl;cout<<"结点个数：";cout<<NodesTree(&tree)<<endl;cout<<"度为二的结点个数";L=Twochild(&tree);cout<<L<<endl;}void InitTree(Tree *tree)//初始化树{tree->lTree=NULL;tree->rTree=NULL;tree->data='0';}void CreatTree(Tree *tree)//创建树{int n=0,m=0,i=0;if(tree->data=='0'){cout<<"请输入该节点的数据：";cin>>tree->data;}cout<<"节点"<<tree->data<<"是否有左子树（0：没有1：有）：";cin>>n;if(n==1){Tree *lTree=(Tree*)malloc(sizeof(Tree));tree->lTree=lTree;lTree->lTree=NULL;lTree->rTree=NULL;lTree->data='0';CreatTree(tree->lTree);cout<<"节点"<<tree->data<<"是否有右子树（0：没有1：有）：";cin>>i;if(i==0);else if(i==1){Tree *rTree=(Tree*)malloc(sizeof(Tree));tree->rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0';CreatTree(tree->rTree);}}else if(n==0){cout<<"节点"<<tree->data<<"是否有右子树（0：没有1：有）：";cin>>m;if(m==0);else if(m==1){Tree *rTree=(Tree*)malloc(sizeof(Tree));tree->rTree=rTree;rTree->lTree=NULL;rTree->rTree=NULL;rTree->data='0';CreatTree(tree->rTree);}}}void PreTraverse(Tree*tree)//先序遍历递归{if(tree!=NULL){cout<<tree->data<<" ";if(tree->lTree!=NULL){PreTraverse(tree->lTree);PreTraverse(tree->rTree);}else if(tree->rTree!=NULL){PreTraverse(tree->rTree);}else;}}void PreOrderTraverse(Tree *tree)//先序遍历非递归{Tree *S[80]={NULL};int top =0;while ((tree!=NULL)||(top)){if (tree!=NULL){cout<<tree->data<<" ";top++;S[top] = tree;tree = tree->lTree;}else{tree = S[top];top--;tree = tree->rTree;}}}void InTraverse(Tree *tree)//中序遍历递归{if(tree!=NULL){if(tree->lTree!=NULL){InTraverse(tree->lTree);cout<<tree->data<<" ";InTraverse(tree->rTree);}else if(tree->rTree!=NULL){cout<<tree->data<<" ";InTraverse(tree->rTree);}elsecout<<tree->data<<" ";}}void InOrderTraverse(Tree *tree)//中序遍历非递归{Tree *D[80]={NULL};.int top =0;while ((tree!=NULL)||(top)){if (tree!=NULL){top++;D[top] = tree;tree = tree->lTree;}else{tree = D[top];top--;cout<<tree->data<<" ";tree = tree->rTree;}}}void PostTraverse(Tree *tree)//后序遍历递归{if(tree!=NULL){if(tree->lTree!=NULL){PostTraverse(tree->lTree);PostTraverse(tree->rTree);cout<<tree->data<<" ";}else if(tree->rTree!=NULL){PostTraverse(tree->rTree);cout<<tree->data<<" ";}elsecout<<tree->data<<" ";}}void LastOrderTraverse(Tree *tree)//后序遍历非递归{Tree *stack[Maxsize]={NULL},*p;p=tree;int top=0,tag=1,i=0,k=0;while(p!=NULL || top){i=1;while(p!=NULL){stack[++top]=p;p=p->lTree;}if(top!=0)p=stack[top]->rTree;if(p==NULL){cout<<stack[top--]->data<<" ";if(stack[top]!=NULL){while(i){if(stack[top]!=NULL){if(stack[top]->rTree!=NULL){if(stack[top]->rTree->data==stack[top+1]->data)cout<<stack[top--]->data<<" ";elsei=0;}elsei=0;}else.i=0;}}if(top!=0)p=stack[top]->rTree;elsep=NULL;}}}int DepthTree(Tree *tree) //深度函数{int u,v;if (tree==NULL) return 0;u=DepthTree(tree->lTree);v=DepthTree(tree->rTree);if (u>v)return (u+1);return (v+1);}int LeafsTree(Tree *tree)//子叶个数函数{int num1,num2;if(tree==NULL)return 0;else if(tree->lTree==NULL&&tree->rTree==NULL) return 1;else{num1=LeafsTree(tree->lTree);num2=LeafsTree(tree->rTree);return(num1+num2);}}int NodesTree(Tree *tree)//结点个数函数{int num1,num2;if(tree==NULL)return 0;if(tree->lTree==NULL&&tree->rTree==NULL) return 1;else{num1=NodesTree(tree->lTree);num2=NodesTree(tree->rTree);return(num1+num2+1);}}int Twochild(Tree*tree)//度为2的{int n=0;if(tree==NULL)return(0);if(tree->lTree!=NULL&&tree->rTree!=NULL)n=1;return(Twochild(tree->lTree)+Twochild(tree->rTree)+n);}五、讨论、心得通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
