数据结构与算法 树与二叉树实验(新)

《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。

实验目的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）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。

实验报告一：预习要求预习树和二叉树的存储结构、以递归为基本思想的相应遍历操作。

二：实验目的1、通过实验，掌握二叉树的建立与存储方法。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

4、理解huffman编解码的算法三：实验内容以括号表示法输入一棵二叉树，编写算法建立二叉树的二叉链表结构；编写先序、中序、后序、层次遍历二叉树的算法；编写算法计算二叉树的结点数，叶子结点数，以及二叉树的深度。

四:实验原理及试验方法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，且存在Dr上的关系Hr包含于H；H={<root,x1>,<root,xr>,H1,Hr};（4） (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，（Dr,{Hr}）是一颗符合本定义的二叉树，称为根的右子树。

基本操作P：CreateBiTree(&T,definition);初始条件：definition给出二叉树的定义。

操作结果：按definition构造二叉树T。

PreOrderTraverse(T);初始条件：二叉树T存在。

操作结果：先序遍历T 。

InOrderTraverse(T);初始条件：二叉树T存在。

操作结果：中序遍历T。

PostOrderTraverse(T);初始条件：二叉树T存在。

《数据结构》实验报告题目: 树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式, 包括数字和用字母表示的数, 运算符号+ - * / ^ =及括号。

系统根据输入的表达式建立二叉树, 按照先括号里面的后括号外面的, 先乘后除的原则, 每个节点里放一个数字或一个字母或一个操作符, 括号不放在节点里。

分别先序遍历, 中序遍历, 后序遍历此二叉树, 并输出表达式的前缀式, 中缀式和后缀式。

（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedef struct BiNode //二叉树的存储类型{char s[20];struct BiNode *lchild,*rchild;}BiTNode,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系, 函数的调用关系图:3. 列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件: 输入表达式中的某个符号操作结果: 将输入的字符存入buf数组中去BiTree Create_RTree()初始条件: 给出二叉树的定义表达式操作结果：构造二叉树的右子树, 即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件: 给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树, 其中左子树存储‘X’, 根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：先序遍历T, 对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：中序遍历T, 对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：后序遍历T, 对每个节点调用函数Visit一次且仅一次int main()主函数, 调用各方法, 操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误, 经检查后都能及时修正。

树和二叉树的实验报告树和二叉树的实验报告一、引言树和二叉树是计算机科学中常用的数据结构，它们在各种算法和应用中都有广泛的应用。

本实验旨在通过实际操作和观察，深入了解树和二叉树的特性和操作。

二、树的构建与遍历1. 树的概念和特性树是一种非线性的数据结构，由节点和边组成。

每个节点可以有零个或多个子节点，其中一个节点没有父节点的称为根节点。

树的特点包括层次结构、唯一根节点和无环等。

2. 树的构建在本实验中，我们使用Python语言构建了一棵树。

通过定义节点类和树类，我们可以方便地创建树的实例，并添加节点和连接节点之间的边。

3. 树的遍历树的遍历是指按照一定顺序访问树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

我们在实验中实现了这三种遍历方式，并观察了它们的输出结果。

三、二叉树的实现与应用1. 二叉树的概念和特性二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的特点包括唯一根节点、每个节点最多有两个子节点和子节点的顺序等。

2. 二叉树的实现我们使用Python语言实现了二叉树的数据结构。

通过定义节点类和二叉树类，我们可以创建二叉树的实例，并实现插入节点、删除节点和查找节点等操作。

3. 二叉树的应用二叉树在实际应用中有很多用途。

例如，二叉搜索树可以用于实现快速查找和排序算法。

AVL树和红黑树等平衡二叉树可以用于高效地插入和删除操作。

我们在实验中实现了这些应用，并通过实际操作验证了它们的效果。

四、实验结果与讨论通过实验，我们成功构建了树和二叉树的数据结构，并实现了它们的基本操作。

通过观察和分析实验结果，我们发现树和二叉树在各种算法和应用中的重要性和灵活性。

树和二叉树的特性使得它们适用于解决各种问题，例如搜索、排序、图算法等。

同时，我们也发现了一些问题和挑战，例如树的平衡性和节点的插入和删除操作等。

这些问题需要进一步的研究和优化。

五、总结本实验通过实际操作和观察，深入了解了树和二叉树的特性和操作。

实验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.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

实验3树和二叉树实验3 树和二叉树实验性质：验证性实验学时：4学时一、实验目的1.掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现；2.能够利用二叉树求解一些常见问题。

二、实验预备知识1.阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作。

2.阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作。

三、实验内容1.理解并用二叉链表的操作运行下列程序：#includeusing namespace std;#include "Status.h"typedef char ElemType;#include "BiTree.h"void main(){BiTree T;CreateBiTree(T);cout<<"二叉树的深度为："<<depth(t)<<endl;< p="">cout<<"二叉树中结点个数为："<<nodecount(t)<<endl;< p="">cout<<"二叉树中叶子结点个数为："<<leavesnodecount(t)<<endl;< p="">cout<<"先序遍历：";PreOrderTraverse(T);cout<<"\n中序遍历：";InOrderTraverse(T);cout<<"\n后序遍历：";PostOrderTraverse(T);cout<<endl;< p="">}本题目说明：（1）头文件Status.h的内容同实验1。

实验3树和二叉树
实验3 树和二叉树
实验目的：
1、通过对二叉树特点的分析，掌握二叉树的主要存储结构；
2、在二叉树具体的存储结构基础上，实现二叉树的基本操作；
3、能针对二叉树的具体应用选择相应的存储结构；
4、进一步掌握递归算法的设计方法。

实验内容
一、假定二叉树采用二叉链表存储结构，编写程序实现二叉树的各种基本运算，
并在此基础上设计一个主程序完成如下功能：
（1）初始化二叉树T；
（2）输入扩展先序序列AB#DF###C#E## ，创建二叉树；
（3）输出二叉树的深度；
（4）输出二叉树的先序遍历序列；
（5）输出二叉树的中序遍历序列；
（6）输出二叉树的后序遍历序列；
（7）输出二叉树的层次遍历序列；
（8）统计二叉树中叶子结点的个数，并输出所有的叶子结点；
（9）交换二叉树的左右子树；
（10）输出二叉树的先序遍历序列；
（11）输出二叉树的中序遍历序列；
（12）输出二叉树的后序遍历序列；
（13）输出二叉树的层次遍历序列；
二、编写程序实现赫夫曼树和赫夫曼编码的各种基本运算，并在此基础上设计一
个主程序完成如下功能：
（1）输入n个字符及其权值，建立赫夫曼树；
字符 A B C D E F G H
权值 5 29 7 8 14 23 3 11
（2）输出每个字符对应的赫夫曼编码；
（3）输入正文FACE，输出其编码；（4）输入编码101101111，输出其正文；。

精品文档实习报告题目：编写一个实现基于二叉树表示的算术表达式Expression 操作程序班级：姓名：学号：完成日期//一、需求分析算术表达式 Expression 内可以含有变量（ a～ z）、常量（ 0～9）和二元算术符（ +,-,*,/, ∧（乘幂））。

实现以下操作：（1）ReadExpr(E) ――以字符序列的形式输入语法正确的前缀表达式并构造表达式 E。

（2） WriteExpr(E) ――用带括号的中缀表达式输出表达式 E。

（3） Assign(V ，c) ――实现对变量 V 的赋值（ V=c），变量的初值为 0。

（4） Value(E) ――对算术表达式 E 求值。

（5） CompoundExpr(p,E1,E2)――构造一个新的复合表达式（ E1）p（E2）。

二、概要设计1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/* 头文件以及存储结构 */#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;2、表达式的抽象数据类型定义ADT Expression {数据对象 D：D 是具有数值的常量 C 和没有数值的变量V；数据关系： R={<(V 或者 C)P(V 或者 C)>|V,C ∈D, <(V 或者 C)P(V 或者 C)> 表示由运算符 P 结合起来的表达式 E}基本操作：Status Input_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串 string ；参数 flag 表示输出的提示信息是什么，输入成功返回 OK，否则，返回 ERROR。

●实验内容：实验三树和二叉树1.编写函数,输入字符序列,建立二叉树的二叉链表。

2.编写函数,实现二叉树的中序递归遍历算法。

(最好也能实现前缀和后缀遍历算法)3.编写函数,实现二叉树的中序非递归遍历算法。

4.编写函数,借助队列实现二叉树的层次遍历算法。

5.编写函数,求二叉树的高度。

6.编写函数,求二叉树的结点个数。

7.编写函数,求二叉树的叶子个数。

8.编写函数,交换二叉树每个结点的左子树和右子树。

9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

●实验目的及要求：1.掌握二叉树的存储实现2.掌握二叉树的遍历思想3.掌握二叉树的常见算法的程序实现●实验内容、方法与步骤：（使用附页填写并附在本页后）见附页●实验结果：见附页●小结：通过本次实验，我基本掌握了二叉树的存储实现和二叉树的遍历思想，并且实现了二叉树的几种常见算法。

分数：批阅老师：200 年月日第 1 页/ 共13 页实验报告（附页）#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int status;typedef struct BiNode//二叉链表{char Data;struct BiNode* lChild;struct BiNode* rChild;}BiNode,*pBiNode;typedef struct SNode/*链栈的结点类型*/{pBiNode elem; /*栈中的元素是指向二叉链表结点的指针*/struct SNode *next;}SNode;struct link //队列链表{struct BiNode *p;struct link *next;};status CreateTree(BiNode** pTree);status PreOrderTraval(BiNode* pTree);//前序递归status InOrderTraval(BiNode* pTree);//中序递归status PostOrderTraval(BiNode* pTree);//后序递归status st_InOrderTraverse(BiNode* pTree);//中序非递归遍历void TreeLink(BiNode* pTree); //队列实现层次遍历int TreeHeight (BiNode* pTree);//二叉树的高度int Count(BiNode* pTree);//结点个数int TreeNumber(BiNode* pTree);//叶子个数void Exchange (BiNode* pTree);//交换左右子树status Visit(char Data);void Display(BiNode* pTree,int Level);BiNode *pRoot=NULL;status CreateTree(BiNode** pTree) /*Input Example: abd##e##cf##g##*/ {char ch;scanf("%c",&ch);if(ch=='#'){(*pTree)=NULL;}else{if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode)))) {exit(OVERFLOW);}(*pTree)->Data=ch;CreateTree(&((*pTree)->lChild));CreateTree(&((*pTree)->rChild));}return OK;}status PreOrderTraval(BiNode* pTree)//前序递归{if(pTree){if(Visit(pTree->Data)){if(PreOrderTraval(pTree->lChild)){if(PreOrderTraval(pTree->rChild)){return OK;}}}return ERROR;}else{return OK;}}status InOrderTraval(BiNode* pTree)//中序递归{if(pTree){if(InOrderTraval(pTree->lChild)){if(Visit(pTree->Data)){if(InOrderTraval(pTree->rChild)){return OK;}}return ERROR;}return ERROR;}else{return OK;}}status PostOrderTraval(BiNode* pTree)//后序递归{if(pTree){if(PostOrderTraval(pTree->lChild)){if(PostOrderTraval(pTree->rChild)){if(Visit(pTree->Data)){return OK;}return ERROR;}}return ERROR;}else{return OK;}}status st_InOrderTraverse(BiNode* pTree)//中序非递归遍历{BiNode *p;SNode *q,*Stop=NULL; /*用不带头结点的单链表作为栈的存储结构*/ p=pTree;while(p!=NULL||Stop!=NULL) /*不是空树*/{if(p!=NULL){q=(SNode*)malloc(sizeof(SNode));if(q==NULL)return ERROR;q->next=Stop;q->elem=p;Stop=q; /*根结点指针入栈*/p=p->lChild; /*进入根的左子树*/}else{q=Stop;Stop=Stop->next; /*栈顶元素出栈*/printf("%c ",q->elem->Data);/*访问根结点*/p=q->elem->rChild; /*进入根的右子树*/free(q); /*释放原栈顶元素的结点空间*/}}return OK;}void TreeLink(BiNode* pTree) //队列实现层次遍历{struct link *head,*rear,*temp;head=(struct link *)malloc(sizeof(struct link));head->p=pTree;head->next=NULL;rear=head;do{if(head->p->lChild!=NULL){temp=(struct link *)malloc(sizeof(struct link));temp->p=head->p->lChild;temp->next=NULL;rear->next=temp;rear=temp;}if(head->p->rChild!=NULL){temp=(struct link *)malloc(sizeof(struct link));temp->p=head->p->rChild;temp->next=NULL;rear->next=temp;rear=temp;}temp=head;printf("%c ",head->p->Data);head=head->next;free(temp);}while(head!=NULL);}int TreeHeight(BiNode* pTree)//二叉树的高度{int hl ,hr ; //左右子树的高度if (pTree == NULL)return 0 ;elsehl = TreeHeight(pTree-> lChild);hr = TreeHeight (pTree-> rChild);if (hl>hr)return (hl +1);elsereturn (hr +1);}int Count(BiNode* pTree)//结点个数{return pTree == NULL ? 0 : Count(pTree->lChild) + Count(pTree->rChild) + 1;}int TreeNumber(BiNode* pTree)//叶子个数{if (pTree==NULL)return 0;if (pTree->lChild ==NULL && pTree->rChild == NULL)return 1;return TreeNumber(pTree->lChild)+TreeNumber(pTree->rChild);//+1就可以求出结点个数}void Exchange (BiNode* pTree )//交换左右子树{BiNode* temp;if ( pTree->lChild != NULL || pTree->rChild != NULL ){temp = pTree->lChild;pTree->lChild = pTree->rChild;pTree->rChild = temp;Exchange ( pTree->lChild );Exchange ( pTree->rChild );}}status Visit(char Data){printf("%c ",Data);return OK;}void Display(BiNode* pTree,int Level)//显示整个树{int i;if(pTree==NULL) return;Display(pTree->rChild,Level+1);for(i=0;i<Level-1;i++){printf(" ");}if(Level>=1){printf("--");}printf("%c\n",pTree->Data);Display(pTree->lChild,Level+1);}void CmdList() //显示命令列表{printf("\n_____________________________________________\n");printf(" 请选择操作: \n");printf(" 1.前序递归遍历\n"); //前序递归遍历printf(" 2.中序递归遍历\n"); //中序递归遍历printf(" 3.后序递归遍历\n"); //后序递归遍历printf(" 4.中序非递归遍历\n"); //中序非递归遍历printf(" 5.层次遍历\n"); //层次遍历printf(" 6.求二叉树高度\n"); //二叉树高度printf(" 7.求结点个数\n"); //二叉树的结点个数printf(" 8.求叶子个数\n"); //二叉树的叶子个数printf(" 9.交换左右子树\n"); //交换左右子树printf(" 0.退出程序\n"); //退出printf("\n______________________________________________\n");}void init(){system ("cls");printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");printf("实验三树和二叉树\n");printf("03计本3班\n");printf("樊海军 2B0324151138\n");printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");printf("本程序实现二叉树的常见算法。

实验报告班级: 软本101 学号: 2010417133姓名: 张明宇日期: 10月20号1.实验题目2.编辑一个程序, 用来演示树和二叉树的建立、遍历等操作。

3.需求分析本演示程序在Microsoft Visual C++ 6.0环境下编写调试, 完成二叉树的建立、遍历、深度求解等。

（1）建立二叉树: 进入程序运行界面后, 提示我们输入要建立的二叉树, 并默认以先序序列输入。

若第一个输入为“#”, 则为空树。

否则按照从左子树到右子树的顺序建立该二叉树, 用#代表虚结点, 如ABD###CE##F##。

建立完二叉树后按“ENTER”键自动进入下一个功能模块的实现。

（2）实现各个遍历递归算法: 实现该二叉树的先序遍历、中序遍历和后序遍历递归算法, 逐个访问该二叉树的左右子树, 并输出各遍历序列。

（3）统计出该二叉树中叶子节点个数和高度：只要该二叉树的移动指针t 所指向的节点非空, 进一步判断其左右子树是否也都为空, 让表示节点的变量能够记录叶子节点个数和深度。

（4）实现层次遍历算法：利用队列“先进先出”的原则, 按照“根左右”的顺序前后将整棵树入队, 并输出。

概要设计（1）为了实现上述程序功能, 需要定义二叉树的数据结构。

二叉树单个元素的结构如图1.1所示。

图1.1 二叉树元素的数据结构（2）本程序包含7个函数:①主函数main()。

②树的建立函数CreatBinTree()。

③先序遍历函数Preorder()。

④中序遍历函数Inorder()。

⑤后序遍历函数Postorder()。

⑥求叶子深度和二叉树深度函数TreeDepth()。

⑦层次遍历函数Levelorder()。

各函数间的关系如图1.2所示。

图1.2 程序所包含各函数之间的关系4.详细设计（1）实现概要设计中定义的所有的数据类型, 对每个操作给出具体的算法；对主程序和其他模块也都需要写出具体算法。

数据类型。

用C语言描述如下:typedef struct BinTNode{char data;struct BinTNode *lchild,*rchild;}BinTNode,*BinTree;（2）线性表的基本操作函数的具体算法。

《数据结构〉课程实验报告实验名称树与二叉树实验序号5实验日期姓名院系班级学号指导教师成绩专业教师评语一、实验目得与要求(1)掌握树得相关概念，包括树、结点得度、树得度、分支结点、叶子结点、儿子结点、双亲结点、树得深度、森林等定义。

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

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

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

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

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

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

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

(9)掌握并查集得相关概念与算法。

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

二、实验项目摘要1编写一程序，实现二叉树得各种基本运算，并在此基础上设计一个主程序完成如下功能：(1)输出二叉树b;(2)输出H结点得左、右孩子结点值；(3)输出二叉树b得深度；(4)输出二叉树b得宽度；(5)输出二叉树b得结点个数；(6)输出二叉树b得叶子结点个数。

2编写一程序，实现二叉树得先序遍历、中序遍历与后序遍历得各种递归与非递归算法，以及层次遍历得算法。

三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）三、实验结果与分析7-1#incl u d e < s tdio、h>#incl u d e<m a1 l o c、h># d e f in e M axS i z e 100typedef cha r E l emT y p e;ty p ed e f struct n o d e｛o ElemTy p e data;。

str u c t n ode * 1 c h i 1 d ;0struct no d e * r chi l d;0}BT N ode;void Cr e a teBTNod e(BTNod e *&b,c h ar *s t r)｛o B TNod e* S t[M a x S ize] , *p=NULL;o i n t t o p=-1,k,j = 0:ch a r ch;b=N U L L;oo0ch= s tr廿］；wh i l e C ch!='\O')叶s wit c h(ch)｛o ca s e'(':to p ++; St[t o p]=p;k=l;b rea k;。

沈阳工程学院学生实验报告（课程名称：数据结构与算法）实验题目：二叉树班级学号姓名地点指导教师实验日期: 年月日一、实验目的1．掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。

2．掌握用指针类型描述、访问和处理二叉树的运算。

二、实验环境Turbo C或是Visual C++三、实验内容与要求1．输入字符序列，建立二叉链表。

2．按先序、中序和后序遍历二叉树（递归算法）。

3．按某种形式输出整棵二叉树。

4．求二叉树的高度。

5．求二叉树的叶结点个数。

6．交换二叉树的左右子树。

7．借助队列实现二叉树的层次遍历。

8．在主函数中设计一个简单的菜单，调试上述算法，要求1-3必做，4-7为选做。

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。

建立二叉树有各种不同的方法。

一种方法是利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素）。

图4.1所示二叉树的输入数据顺序应该是：（1,a），（2,b），（3,c），（4,d），（6,e），（7,f），（9,g），（13,h）。

另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。

数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。

这时，图4.1所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。

若当前数据不为“#”，则申请一个结点存入当前数据。

递归调用建立函数，建立当前结点的左右子树。

四、实验过程及结果分析五、成绩评定优良中及格不及格出勤内容格式创新效果总评指导教师：年月日。