实验三二叉树的基本操作
一、实验目的
1、进一步掌握树的结构及非线性特点，递归特点和动态性。
2、掌握二叉树的建立算法。
3、掌握二叉树的三种遍历方法以及基于遍历的几种基本操作。
二、实验内容
1、二叉树的链式存储结构的建立；
2、二叉树的三种遍历算法以及基于遍历的几种操作的实现。
三、实验要求
1、学生用C++/C完成算法设计和程序设计并上机调试通过；
2、撰写实验报告，提供实验测试数据和实验结果；
3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、实验准备
1、了解树的结构特点及概念、二叉树的概念及结构特点。
2、了解树和二叉树的基本概念和术语。
3、二叉树的三种遍历方法（先序、中序、后序遍历）
先序遍历：若二叉树为空，则空操作，否则
①访问根结点；
②先序遍历左子树；
③先序遍历右子树。
中序遍历：若二叉树为空，则空操作，否则
①中序遍历左子树；
②访问根结点；
③中序遍历右子树。
后序遍历：若二叉树为空，则空操作，否则
①后序遍历左子树；
②后序遍历右子树；
③访问根结点。
4、二叉树的各种存储结构及其适用范围，特别是链式存储结构。
五、实验步骤
1、编程实现二叉树的建立、遍历以及基于遍历的几种基本操作。
(1)采用二叉链表存储结构创建一个二叉树；
(2)用递归方法实现二叉树的三种遍历算法
(3)求二叉树中叶子结点的个数,度为1 的结点个数和度为2 的结点个数；
(4)求二叉树的深度。
六、实验参考代码
#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef char TElemType; //限定元素的数据类型
typedef int Status;
typedef struct BiTNode // 定义二叉树结点结构
{
TElemType data;
BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
//按扩展的前序序列建立二叉树存储结构的算法
Status CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else
{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree
// 先序遍历二叉树
void PreOrder (BiTree T)
{
if (T) {
printf("%4c",T->data); // 访问结点
PreOrder(T->lchild); // 遍历左子树
PreOrder(T->rchild) ; // 遍历右子树
}
}
// 中序遍历二叉树
void InOrder (BiTree T)
{
if (T)
{
InOrder(T->lchild); // 遍历左子树
printf("%4c",T->data); // 访问结点
InOrder(T->rchild);// 遍历右子树
}
}
// 后序遍历二叉树
void PostOrder (BiTree T)
{
if (T) {
PostOrder (T->lchild); // 遍历左子树
PostOrder (T->rchild);// 遍历右子树
printf("%4c",T->data); // 访问结点
}
}
//求二叉树的叶子结点数
void CountLeaf (BiTree T, int& count)
{
if(T)
{
if((!T->lchild)&&(!T->rchild)) count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}
//求二叉树中度为1的结点和度为2 的结点的数
void CountBT(BiTree T,int &m,int &n)
{
if(T)
{
if((T->lchild!=0)&&(T->rchild!=0))
n++; //度为2的结点
else if(((T->lchild!=0)&&(T->rchild==0))||((T->lchild==0)&&(T->rchild!=0)))
m++; //度为1 的结点
CountBT (T->lchild,m,n);
CountBT (T->rchild,m,n);
}
}
//以下是求二叉树的深度
int Depth (BiTree T )
{
int m,n;
if(!T) return 0;
else{
m = Depth(T->lchild);
n = Depth(T->rchild);
return (m>n?m:n)+1;
}
}
//主函数
void main()
{
BiTree T;
int s=0,m=0,n=0,d=0;
T=NULL;
int select;
while(1) {
printf("\n 请选择要执行的操作:\n");
printf("1.创建二叉树\n");
printf("2.二叉树的递归遍历算法（前、中、后）\n");
printf("3.求二叉树的叶子结点数\n");
printf("4.求二叉树的深度\n");
printf("0.退出\n");
scanf("%d",&select);
getchar();
switch(select) {
case 0:return;
case 1:
printf("\n 请按先序次序输入各结点的值，以#表示空树:\n");
CreateBiTree(T);
printf("二叉树已建立完毕！\n");
break;
case 2:
if(!T) printf("\n 未建立树，请先建树！\n");
else {
printf("\n 先序遍历:");
PreOrder(T);
printf("\n 中序遍历:");
InOrder(T);
printf("\n 后序遍历:");
PostOrder(T);
printf("\n");
}
break;
case 3:
if(!T) printf("\n 未建立树，请先建树！\n");
else{
CountLeaf(T,s);
printf("\n 叶子结点数为：%d\n",s);
CountBT(T,m,n);
printf("度为1的结点数为：%d\n",m);
printf("度为2 的结点数为：%d\n",n);
}
break;
case 4:
if(!T) printf("\n 未建立树，请先建树！\n");
else{
d=Depth(T);
printf("\n 二叉树的深度为：%d\n",d);
}
break;
default:
printf("请确认选择项:\n");
}//end switch
}//end while
}
七、测试数据
教材138 页，图7-10所示的二叉树
按展的前序序列输入序列为：A B D # G # # # C E # # F H # # #
二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。
3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。
昆明理工大学信息工程与自动化学院学生实验报告 （2014—2015学年第二学期） 课程名称：图形图像基础开课实验室：444 2014年 6月 4 日年级、专业、班计科111 学号201110405138 姓名成绩实验项目名称图像分割指导教师刘辉教 师 评语 教师签名： 年月日 一、实验目的及内容 目的：掌握和熟悉Matlab编程环境及语言；掌握数学形态学和图像分割的基本原理及 应用。 内容： 1.通过数学形态学实现边界提取。 2.通过全局阈值及局部阈值实现灰度图像二值化； 3.分别用Sobel算子和Canny算子对图像进行边缘检测；通过Hough检测图像中的直 线。 二、要求 1.描述腐蚀、膨胀、开运算、闭运算的原理。 膨胀：将与物体接触的所有背景点合并到该物体中，使边界向外部扩张的过程。 利用它可以填补物体中的空洞。B对X膨胀所产生的二值图像D是满足以下条件的点（x,y）的集合:如果B的原点平移到点（x,y），那么它与X的交集非空。 数学表达式：B=A⊕C 腐蚀：一种消除边界点，使边界向内部收缩的过程。利用它可以消除小而且无意义的物体。B对X腐蚀所产生的二值图像E是满足以下条件的点（x,y)的集合：如果B的原点平移到点（x,y），那么B将完全包含于X中。 数学表达式：B=AΘC 腐蚀：是一种消除边界点，使边界向内部收缩的过程。可以用来消除小且无意义的
物体。 膨胀：是将与物体接触的所有背景点合并到该物体中，使边界向外部扩张的过程。 可以用来填补物体中的空洞。 开运算：先腐蚀后膨胀的过程开运算。用来消除小物体、在纤细点处分离物体、平滑较大物体的边界的同时并不明显改变其面积。开运算通常是在需要去除小颗粒噪声，以及断开目标物之间粘连时使用。其主要作用与腐蚀相似，与腐蚀操作相比，具有可以基本保持目标原有大小不变的优点。 闭运算：先膨胀后腐蚀的过程称为闭运算。用来填充物体内细小空洞、连接邻近物体、平滑其边界的同时并不明显改变其面积。 2.编写程序，使用数学形态学方法实现边界提取。 3.描述全局阈值、局部阈值对图像进行二值化的原理。 数学形态学中二值图像的形态变换是一种针对集合的处理过程。其形态算子的实质是表达物体或形状的集合与结构元素间的相互作用，结构元素的形状就决定了这种运算所提取的信号的形状信息。形态学图像处理是在图像中移动一个结构元素，然后将结构元素与下面的二值图像进行交、并等集合运算。 阈值分割法分为全局阈值法和局部阈值分割法。所谓局部阈值分割法是将原始图像划分成较小的图像，并对每个子图像选取相应的阈值。在阈值分割后， 相邻子图像之间的边界处可能产生灰度级的不连续性，因此需用平滑技术进行 排除。局部阈值法常用的方法有灰度差直方图法、微分直方图法。局部阈值分 割法虽然能改善分割效果，但存在几个缺点： （1）每幅子图像的尺寸不能太小，否则统计出的结果无意义。 （2）每幅图像的分割是任意的，如果有一幅子图像正好落在目标区域或背景区域，而根据统计结果对其进行分割，也许会产生更差的结果。 （3）局部阈值法对每一幅子图像都要进行统计，速度慢，难以适应实时性的要求。
#include
实验二 图像灰度变换实验一、 实验目的熟悉亮度变换函数的使用熟悉灰度图像的直方图的表示；掌握图像增强的基本方法：灰度变换、直方图均衡；二、实验内容灰度线性变换、灰度直方图、直方图均衡处理；灰度变换是图像增强的一种重要手段，使图像对比度扩展，图像更加清晰，特征更加明显。灰度级的直方图给出了一幅图像概貌的描述，通过修改灰度直方图来得到图像增强。三、实验原理1.函数imadjust 函数imadjust 是对灰度图像进行亮度变换的基本命令，语法为： g = imadjust(f, [low_in high_in], [low_out high_out], gamma) 将图像f 中的亮度值（灰度值）映射到新图像g 中，即将low_in 至high_in 之间的值映射到low_out 至high_out 之间的值。low_in 以下的灰度值映射为low_out ，high_in 以上的灰度值映射为high_out ，函数imadjust 的矩阵[ ]内参数均指定在0和1之间，[low_in high_in]和[low_out high_out]使用空矩阵[ ]会得到默认值[0 1]。若high_out 小于low_out ，则输出图像会反转。 参数gamma 指定了曲线（变换函数）的形状，若gamma 小于1，则映射被加权至更高（更亮）的输出值；若gamma 大于1，则映射被加权至更低（更暗）的输出值。若省略了函数的参量gamma ，则gamma 默认为1——即线性映 射。 >>f = imread(‘filename’)>>imshow(f)>>g1 = imadjust(f, [0 1], [1 0]); %图像反转>>figure, imshow(g1) %figure 命令表示同时显示多个窗口 >>g2 = imadjust(f, [0.5 0.75], [0 1]); %将0.5至0.75之间的灰度级扩展到范围0和1之间 >>figure, imshow(g2) >>g3 = imadjust(f, [ ], [ ], 2) %使用gamma 值 >>figure, imshow(g3)
二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"<
实验二图像的基本操作 实验目的 1．熟悉Photoshop CS的基本操作 2．掌握常用工具的使用 3．掌握图层的简单应用 实验内容 1．立体相框的制作 2．移花接木 3．制作圆柱体等图案 4．修补照片 5．制作彩色文字 6．制作心形图案 1．立体相框的制作，请把结果文件保存为sy2-1.psd。 ①打开图片“牡丹花.jpg”，单击菜单“图像|图像大小”，观察图像现在的像素大小是多少MB？然后用计算器计算2048*1536*3/（1024*1024）是不是正好等于图像的像素大小，为什么？ 将图片大小改为1024*768，分辨率为72pps（像素/英寸），观察现在的文档大小是多少？ 请计算1024/（72/2.54）和768/（72/2.54）是否就是文档大小？（1英寸=2.54厘米），下面请将分辨率改为300pps，如果保持文档大小不变，请观察像素大小的变化，继续将像素大小改为1024*768，请观察文档大小是多少？ 通过本实验请大家了解像素大小、文档大小和分辨率之间的关系。 ②打开“t1.jpg”图片，图像大小改为100*72，选取该照片定义为图案。 ③继续将“牡丹花.jpg”图片的画布四周扩大2厘米，然后将自己定义的图案填充到扩充的画布区域内。 ④在图层面板中双击背景图层将其转换为普通图层，然后添加斜面与浮雕的立体效果，样式自己定义。效果如图2-1所示。 图2-1 立体相框图2-2 一串红 2．移花接木，请把结果文件保存为sy2-2.psd。 ①打开“一串红.jpg”，将图像的大小改成800*600，图像顺时针旋转90度，如图2-2所示。 ②打开图像文件“蝴蝶.jpg”，将图像放大显示到300%，用钢笔工具描绘出蝴蝶的路径（注意工具选项栏中按下路径按钮），如图2-3所示，然后在如图2-4所示的路径面板中
数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号：
目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12)
一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。
实验二图像的增强 一、实验目的 1)掌握在计算机上进行直方图统计，以及直方图均衡化、线性变换的图像增强的方法 2)掌握在计算机上进行图象平滑、图象锐化特别是中值滤波平滑及拉普拉斯算子锐化 的方法 二、实验要求 1)显示图像（cameraman.tif）及灰度直方图。 2)对指定图像（cameraman.tif）进行直方图均衡化和线性变换，将原始图像及增强 后的图像都显示于屏幕上，比较增强的效果。 3)对指定图像（lena.bmp）加入椒盐噪声，然后进行邻域平滑、中值滤波，将原始图 像及平滑后的图像都显示于屏幕上，比较效果。 4)对指定图像（lena.bmp）进行锐化（简单梯度算法、ROBERT算子，Prewitt边缘算 子和拉普拉斯算子），将原始图像及锐化后的图像都显示于屏幕上，比较锐化的效果。 三、实验仪器设备及软件 HP D538、MATLAB 四、实验原理 以自己的语言结合课堂笔记进行总结，要求过程推导清晰明了。 五、实验步骤及程序 实验步骤、程序流程、实验源程序和注释齐全 实验源程序： (1). 显示图像（cameraman.tif）及灰度直方图: I=imread('cameraman.tif'); subplot(121); imshow(I); title('原始图象'); subplot(122); imhist(I); title('灰度直方图')实验结果与分析
(2)对指定图像（cameraman.tif）进行直方图均衡化和线性变换，将原始图像及增强后的图像都显示于屏幕上，比较增强的效果。 I=imread('cameraman.tif'); subplot(221); imshow(I); title('原始图象'); I1=histeq(I); subplot(222); imshow(I1); title('原始图象均衡化'); subplot(223); imshow(I); title('原始图象'); I2=imadjust(I); subplot(224); imshow(I1); title('原始图象线性变化'); (3)对指定图像（lena.bmp）加入椒盐噪声，然后进行邻域平滑、中值滤波，将原始图像及平滑后的图像都显示于屏幕上，比较效果。
实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现
1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include
实习2 Idrisi图像处理软件的基本操作 实验目的：初步认识Idrisi的界面、功能和软件的基本操作方法 实习内容： 1.设置工作环境 2.察看各类图件的属性 3.显示各类栅格图、矢量图及叠加显示 4.了解调色板及符号库的使用 5.学习制作图例 6.DEM的立体显示 7.图像的直方图分析 实验步骤： 基本知识 1 Environ / list / describe 2 文件系统（img / doc, vec / dvc, val, smp / sm0 / sm1 / sm2） 3 display (Brazilfc 图像/ color composit 调色版) 注：TM432合成图 4 display (awrajas 矢量图/ idrpoly) 调色板及图例 5 overlay(dec88c图像/NDVI16调色板+ country矢量图) 6 显示dec88c（ndvi16及grey256） 7 显示etdem + etprov 并变换其调色板（idrisi256和grey256） 8 显示affaosol 图像（qual256） 9 显示dec88c(gray16)和affaosol图的图例（了解*.doc文件的图例标注） 10 图例设计（调色板/ 符号库/ 图例文字） 矢量图件的叠加显示 11 显示矢量图clarkblk / idrpoly 12 在图上叠加clarkbld / idr16 和clarkbd2 / idrpoly dem的三维显示及其与影像的叠加 13 ortho显示relief 14 ortho叠加显示njolodem和njolofc / grey256 （务必选中use drape image） 15 显示afsurf图像/grey16 16 histogram显示直方图（h87tm1/ h87tm2/ h87tm4） 思考题: 1 工作环境如何设定 2 调色板有何重要作用 3 矢量栅格的叠加显示方法 4 直方图\ 图例\ 1
数据结构程序设计报告 学院： 班级： 学号： 姓名：
实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include
int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p;
实验二MATLAB图像运算一、实验目的 1．了解图像的算术运算在数字图像处理中的初步应用。 2．体会图像算术运算处理的过程和处理前后图像的变化。 二、实验步骤 1．图像的加法运算-imadd 对于两个图像f x,y和 (x,y)的均值有： g x,y=1 f x,y+ 1 (x,y) 推广这个公式为： g x,y=αf x,y+β (x,y) 其中，α+β=1。这样就可以得到各种图像合成的效果，也可以用于两张图像的衔接。说明：两个示例图像保存在默认路径下，文件名分别为'rice.png'和'cameraman.tif'，要求实现下图所示结果。 代码： I1 = imread('rice.png'); I2 = imread('cameraman.tif'); I3 = imadd(I1, I2,'uint8'); I4 = imadd(I1, I2,'uint16'); subplot(2, 2, 1), imshow(I1), title('?-ê?í???1'); subplot(2, 2, 2), imshow(I2), title('?-ê?í???2'); subplot(2, 2, 3), imshow(I3), title('8??í?????ê?'); subplot(2, 2, 4), imshow(I4), title('16??í?????ê?'); 结果截图：
2．图像的减法运算-imsubtract 说明： 背景图像可通过膨胀算法得到background = imopen(I,strel('disk',15));，要求实现下图所示结果。 示例代码如下： I1 = imread('rice.png'); background = imerode(I1, strel('disk', 15)); rice2 = imsubtract(I1, background); subplot(2, 2, 1), imshow(I1), title('?-ê?í???'); subplot(2, 2, 2), imshow(background), title('±3?°í???'); subplot(2, 2, 3), imshow(rice2), title('′|àíoóμ?í???'); 结果截图： 3.图像的乘法运算-immultiply
第1次实验基于MATLAB的图像基本操作 二、实验内容和要求： 1．实现图像Baboon.bmp（MATLAB自带）的读入（可使用imread）和显示（可使用imshow）操作，代码加上足够的注释，需要建立一个M文件实现。 I=imread('F:\标准图像\Baboon.bmp');//读入图像 imshow(I);//显示图像 2．编程实现将一幅RGB图像转换为二值图像，并在一个窗口同时显示处理过程中得到的每一个图像和原图像，同时需要给图像加上标题。（原始数据可以是任意的RGB图像）。需要新建一个M文件实现。 figure,subplot(1,3,1),imshow(I(:,:,1)),title('R'); subplot(1,3,2),imshow(I(:,:,2)),title('G'); subplot(1,3,3),imshow(I(:,:,3)),title('B'); 3.计算图象统计参数： 读取图像（文件名为‘cameraman.tif’）; 最大值 最小值 均值 K=imread('cameraman.tif'); d_max=max(K(:)) d_min=min(K(:)) d_mean=mean(K(:)) 4.利用帮助系统了解im2double,imresize,image函数的作用和语法，并利用这些函数处理已知图像pout.tif（MATLAB自带）并显示处理前后效果。 J=imread('pout.tif'); J1=im2double(J); figure,subplot(1,2,1),imshow(J),title('Before') subplot(1,2,2),imshow(J1),title('After') J2=imresize(J,0.3); figure,subplot(1,2,1),imshow(J),title('Before') subplot(1,2,2),imshow(J2),title('After') figure,subplot(1,2,1),imshow(J),title('Before') subplot(1,2,2),image(J);title('After') 1
实验报告 实验课程名称：数字图像处理 班级：学号：姓名： 注：1、每个实验中各项成绩按照10分制评定，每个实验成绩为两项总和20分。 2、平均成绩取三个实验平均成绩。
2016年 4 月18日 实验一 图像的二维离散傅立叶变换 一、实验目的 掌握图像的二维离散傅立叶变换以及性质 二、实验要求 1) 建立输入图像，在64?64的黑色图像矩阵的中心建立16?16的白色矩形图像点阵， 形成图像文件。对输入图像进行二维傅立叶变换，将原始图像及变换图像（三维、中心化）都显示于屏幕上。 2) 调整输入图像中白色矩形的位置，再进行变换，将原始图像及变换图像（三维、中 心化）都显示于屏幕上，比较变换结果。 3) 调整输入图像中白色矩形的尺寸（40?40，4?4），再进行变换，将原始图像及变 换图像（三维、中心化）都显示于屏幕上，比较变换结果。 三、实验仪器设备及软件 HP D538、MATLAB 四、实验原理 傅里叶变换作为分析数字图像的有利工具，因其可分离性、平移性、周期性和共轭对称性可以定量地方分析数字化系统，并且变换后的图像使得时间域和频域间的联系能够方便直观地解决许多问题。实验通过MATLAB 实验该项技能。 设),(y x f 是在空间域上等间隔采样得到的M ×N 的二维离散信号，x 和y 是离散实变量，u 和v 为离散频率变量，则二维离散傅里叶变换对一般地定义为 ∑∑ -=-=+-= 101 )],( 2ex p[),(1),(M x N y N yu M xu j y x f MN v u F π,1,0=u …，M-1；y=0，1，…N-1 ∑∑-=-=+=101 )],( 2ex p[),(),(M x N y N uy M ux j v u F y x f π ,1,0=x …，M-1；y=0，1，…N-1
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);
正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
实验一图像处理基本操作 一、 实验目的 1、熟悉并掌握在MATLAB中进行图像类型转换及图像处理的基本操作。 2、熟练掌握图像处理中的常用数学变换。 二、实验设备 1、计算机1台 2、MATLAB软件1套 3、实验图片 三、实验原理 1、数字图像的表示和类别 一幅图像可以被定义为一个二维函数f(x,y)，其中x和y是空间(平面)坐标，f在坐标(x,y)处的幅度称为图像在该点的亮度。灰度是用来表示黑白图像亮度的一个术语，而彩色图像是由若干个二维图像组合形成的。例如，在RGB彩色系统中，一幅彩色图像是由三幅独立的分量图像(红、绿、蓝)组成的。因此，许多为黑白图像处理开发的技术也适用于彩色图像处理，方法是分别处理三幅独立的分量图像即可。 图像关于x和y坐标以及幅度连续。要将这样的一幅图像转化为数字形式，就要求数字化坐标和幅度。将坐标值数字化称为取样，将幅度数字化称为量化。采样和量化的过程如图1所示。因此，当f的x、y分量和幅度都是有限且离散的量时，称该图像为数字图像。 作为MATLAB基本数据类型的数组十分适于表达图像，矩阵的元素和图像的像素之间有着十分自然的对应关系。 图1 图像的采样和量化 图1 采样和量化的过程 根据图像数据矩阵解释方法的不同，MATLAB把其处理为4类： ?亮度图像(Intensity images) ?二值图像(Binary images) ?索引图像(Indexed images) ? RGB图像(RGB images) (1) 亮度图像 一幅亮度图像是一个数据矩阵，其归一化的取值表示亮度。若亮度图像的像素都是uint8类型或uint16类型，则它们的整数值范围分别是[0，255]和[0，65536]。若图像是double 类型，则像素取值就是浮点数。规定双精度double型归一化亮度图像的取值范围是[0 1]。 (2) 二值图像 一幅二值图像是一个取值只有0和1的逻辑数组。而一幅取值只包含0和1的uint8
长春建筑学院《数据结构》课程设计（论文） 基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation 年级: 学号: 姓名: 专业: 指导老师: 二零一三年十二月
摘要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。 二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。 本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。 关键词：二叉树；左子树；右子树
实验二灰度直方图及直方图均衡化 一、 实验目的： 1、直方图显示 2、计算并绘制图像直方图 3、直方图均衡化二、实验内容 学习使用函数 imhist(, histeq(, bar(, stem(, plot(, imadjust(，及 title, axis, set 等描述图像工具。 1、直方图显示 显示图 Fig0354(a(einstein_orig.tif，标注图的题目为：EINSTEIN ，作出其直方图，调整参数如下图所示： EINSTEIN
4 2、分别用 bar 和 stem 函数显示直方图 由 h=imhist( 获得直方图；分别用 bar 和 stem 显示直方图 h ，并通过参数调整，改变直方图的显示方式。用 axis 设置轴的最大、最小值（例如：axis([0 255 0 15000];），用 set 设置显示坐标的间隔（例如：set(gca,’xtick ’, 0:50:255）。作出如下的直方图： 00 50
100 150 200 250 3、用 plot 函数显示直方图要求同 2. 12000 1000080006000400020000 0 50 100 150 200 250 300 4、用 imadjust( 函数调整图像对比度，并用 imhist( 查看调整前后直方图的变化。 3 . 2 . 1 . 0 . 4
5、用 histeq( 进行直方图均衡化，并用 imhist( 查看均衡化前后直方图的变化。
4 三、实验要求 将本实验的 10 个图用 MATLAB 显示到屏幕上。程序： i=imread('Fig0354(a(einstein_orig.tif'; imshow(i; title('EINSTEIN'; figure; imhist(i; title('直方图';
实验二、PhotoShop的基本操作 【实验主要内容】 掌握PhotoShop图像大小的修改和图像的裁切,掌握标尺、参考线、网格等视图辅助工具的使用。 【本实验主要知识点】 修改图像；裁切图像；使用辅助工具。 【主要实验步骤】 一、修改图像 1、修改图像大小 （1）从菜单中选择【图像】│【图像大小】命令，会弹出“图像大小”对话框，如图2-1所示。练习在其中改变图像大小。 图2-1 “图像大小”对话框 （2）像素大小：可以通过修改图像的宽度和高度像素值和百分比来改变图像的 大小，并可随时看出图像改变前后的大小变化。 （3）文档大小：可以通过修改图像的宽度和高度厘米、英寸、点等以及图像的 分辨率来改变图像的大小。 （4）缩放样式：该选项用于在调整图像大小时是否按比例缩放。 （5）约束比例：该选项用于在设置图像宽度和高度时进行等比例调整。 （6）重定图像像素：该选项用于在调整图像大小时像素数目是否随图像大小协 调变化。 （7）设置完毕后单击“好”按钮即可确定图像大小的改变。 2、修改画布大小 （1）从菜单中选【图像】│【画布大小】，打开“画布大小”对话框，如图2-2 所示，练习在其中改变画布大小。 图2-2 “画布大小”对话框
（2）当前大小：其中显示了当前图像画布的实际大小。 （3）新大小：可以通过修改宽度和高度厘米、像素、英寸、百分比来改变图像画布的大小，其中“相对”选项可以改变以上是绝对值还是相对值，“定位”选项区可以调整画布修改后图像位于画布的新具体位置。 （4）画布扩展颜色：设置画布多余部分的色彩。 二、裁切图像 1、在工具箱中使用裁切工具。 2、移动鼠标指针到图像窗口中，按下左键并进行拖曳，释放左键后，会出现一个四周有8个控制点的裁切范围。如图2-3所示。 图2-3 选择裁切范围 3、选定裁切范围后，使用控制点对裁切区域进行平移、缩放、旋转等操作。如图2-4所示。 图2-4 变换裁切范围 4、最后在裁切区内双击鼠标左键，或在工具栏中单击按钮，即可完成裁切工作。 三、使用辅助工具 1、标尺 （1）从菜单中选择【视图】│【标尺】命令，可以在图像窗口的顶部和左 边显示标尺，如图2-5所示。