下载文档原格式
《数据结构》实验报告四实验内容：建一个二叉树并对其进行遍历，并求出该树的叶子数和深度学号： 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，失败。
数据结构二叉树实验报告1. 引言二叉树是一种常见的数据结构，由节点（Node）和链接（Link）构成。
每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树在计算机科学中被广泛应用，例如在搜索算法中，二叉树可以用来快速查找和插入数据。
本实验旨在通过编写二叉树的基本操作来深入理解二叉树的特性和实现方式。
2. 实验内容2.1 二叉树的定义二叉树可以用以下方式定义：class TreeNode:def__init__(self, val):self.val = valself.left =Noneself.right =None每个节点包含一个值和两个指针，分别指向左子节点和右子节点。
根据需求，可以为节点添加其他属性。
2.2 二叉树的基本操作本实验主要涉及以下二叉树的基本操作：•创建二叉树：根据给定的节点值构建二叉树。
•遍历二叉树：将二叉树的节点按照特定顺序访问。
•查找节点：在二叉树中查找特定值的节点。
•插入节点：向二叉树中插入新节点。
•删除节点：从二叉树中删除特定值的节点。
以上操作将在下面章节详细讨论。
3. 实验步骤3.1 创建二叉树二叉树可以通过递归的方式构建。
以创建一个简单的二叉树为例：def create_binary_tree():root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)return root以上代码创建了一个二叉树，根节点的值为1，左子节点值为2，右子节点值为3，左子节点的左子节点值为4，左子节点的右子节点值为5。
3.2 遍历二叉树二叉树的遍历方式有多种，包括前序遍历、中序遍历和后序遍历。
以下是三种遍历方式的代码实现：•前序遍历：def preorder_traversal(root):if root:print(root.val)preorder_traversal(root.left)preorder_traversal(root.right)•中序遍历：def inorder_traversal(root):if root:inorder_traversal(root.left)print(root.val)inorder_traversal(root.right)•后序遍历：def postorder_traversal(root):if root:postorder_traversal(root.left)postorder_traversal(root.right)print(root.val)3.3 查找节点在二叉树中查找特定值的节点可以使用递归的方式实现。
数据结构二叉树实验报告总结一、实验目的本次实验的主要目的是通过对二叉树的学习和实践，掌握二叉树的基本概念、性质和遍历方式，加深对数据结构中树形结构的理解。
二、实验内容1. 二叉树的基本概念和性质在本次实验中，我们首先学习了二叉树的基本概念和性质。
其中，二叉树是由节点组成的有限集合，并且每个节点最多有两个子节点。
同时，我们还学习了二叉树的高度、深度、层数等概念。
2. 二叉树的遍历方式在了解了二叉树的基本概念和性质之后，我们开始学习如何遍历一个二叉树。
在本次实验中，我们主要学习了三种遍历方式：前序遍历、中序遍历和后序遍历。
其中，前序遍历指先访问节点自身再访问左右子节点；中序遍历指先访问左子节点再访问自身和右子节点；后序遍历指先访问左右子节点再访问自身。
3. 二叉搜索树除了以上内容之外，在本次实验中我们还学习了一种特殊的二叉树——二叉搜索树。
二叉搜索树是一种特殊的二叉树，它的每个节点都满足左子节点小于该节点，右子节点大于该节点的性质。
由于这个性质，二叉搜索树可以被用来进行快速查找、排序等操作。
三、实验过程1. 实现二叉树的遍历方式为了更好地理解和掌握二叉树的遍历方式，我们首先在编程环境中实现了前序遍历、中序遍历和后序遍历。
在代码编写过程中，我们需要考虑如何递归地访问每个节点，并且需要注意访问顺序。
2. 实现二叉搜索树为了更好地理解和掌握二叉搜索树的特性和操作，我们在编程环境中实现了一个简单的二叉搜索树。
在代码编写过程中，我们需要考虑如何插入新节点、删除指定节点以及查找目标节点等操作。
3. 实验结果分析通过对代码运行结果进行分析，我们可以清晰地看到每个遍历方式所得到的结果以及对应的顺序。
同时，在对二叉搜索树进行操作时，我们也可以看到不同操作所产生的不同结果。
四、实验总结通过本次实验，我们进一步加深了对二叉树的理解和掌握，学习了二叉树的遍历方式以及二叉搜索树的特性和操作。
同时，在编程实践中，我们也进一步熟悉了代码编写和调试的过程。
南昌航空大学实验报告课程名称：数据结构实验名称：实验六二叉树的递归遍历及其应用班级：学生姓名：学号：指导教师评定：签名:题目：假设二叉树采用二叉链表结构。
设计并实现如下算法：先序递归建树，中序非递归遍历该树，输出各个结点的值，并求该树中单分支结点的个数。
一、需求分析1.用户可以根据自己的需求分别输入任意的一个二叉树，并且能够实现中序非递归遍历该树输出各个结点的数值。
2.通过已有的二叉树能够求出该树的单分支结点的个数。
3.程序执行的命令包括：（1）构造二叉树T （2）遍历二叉树（3）求二叉树单分支结点的个数（4）求二叉树的总结点数二、概要设计⒈为实现上述算法，需要链表的抽象数据类型：ADT Binarytree {数据对象：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，且存在Dr上的关系Hr为H的子集；H={<root，x1>,<root，Xr>,H1,Hr};(4) (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。
基本操作:Creatbitree(&S，definition)初始条件：definition给出二叉树S的定义操作结果：按definition构造二叉树Scounter(T)初始条件：二叉树T已经存在操作结果：返回二叉树的总的结点数onecount(T)初始条件：二叉树T已经存在操作结果：返回二叉树单分支的节点数Clearbintree(S)初始条件：二叉树S已经存在操作结果：将二叉树S清为空树Bitreeempty(S)初始条件：二叉树S已经存在操作结果：若S为空二叉树，则返回TRUE，否则返回FALSEBitreedepth(S,&e)初始条件：二叉树S已经存在操作结果：返回S的深度Parent(S)初始条件：二叉树S已经存在，e是S中的某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。
齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入）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;}elsei=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); }五、讨论、心得通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
