二叉树的建立实验（通用8篇）
篇1：二叉树的建立实验
实验三
实验目的：
二叉树的建立及基本操作
本次实验的主要目的是熟练掌握二叉树的定义、三序（先序、中序、后序）遍历方法，并用遍历思想求解具体二叉树应用问题。通过程序实现，体会递归算法的优缺点。
实验要求：
用C语言编程实现二叉树的基本操作，并完成下述函数功能：(1)CreateBiTree()：根据先序遍历序列生成一棵二叉树(2)Depth()：求此二叉树的深度
(3)CountLeaf()：统计该二叉树中叶子结点的个数(4)InOrderTraverse()：中序遍历二叉树(5)PostOrderTraverse()：后序遍历二叉树
在主函数main()中调用各个子函数完成单链表的基本操作。例： void main(){ BiTree T;CreateBiTree(T);int d= Depth(T);printf(“深度为%d”, d);int num= CountLeaf(T);printf(“叶子结点个数为%d”, num);InOrderTraverse(T);PostOrderTraverse(T);} //注意函数调用时，只传递参数名称，不需要传递参数类型和&符号。
[实现提示] 采用特殊符号，如*号表示空树的情况。
通过输入扩展的先序序列建立一棵二叉树，即，二叉树中结点为空时应输入*符号表示。[测试数据] 由学生自己确定，注意边界数据。
程序检查时，由老师提供用于建树的初始输入序列。
程序源码：（后付纸）程序运行结果：
实验心得体会：
有一些概念不明白，看书之后弄懂了，仔细看了二叉树遍历的知识点，问了同学有了思路。熟悉了二叉树的基本操作，掌握了二叉树实现。
篇2：二叉树的建立实验
课程名称
数据结构基础
实验项目名称
实验十
二叉树的基本操作
实验成绩
指导老师（签名）
日期
一.实验目的和要求
1、掌握二叉树的链式存储结构。
2、掌握在二叉链表上的二叉树操作的实现原理与方法。
3、进一步掌握递归算法的设计方法。
二.实验内容
1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。
二叉树二叉链表存储表示如下： struct BTreeNode {
ElemType data;
// 结点值域
BTreeNode *lchild , *rchild;// 定义左右孩子指针 };基本操作如下：
①void InitBTree(BTreeNode *&BT);
//初始化二叉树BT
②void CreateBTree(BTreeNode *&BT, char *a);
//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
③int EmptyBTree(BTreeNode *BT);
//检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree(BTreeNode *BT);//求二叉树BT的深度并返回该值
⑤int FindBTree(BTreeNode *BT, ElemType x);
//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
⑥void PreOrder(BTreeNode *BT);//先序遍历二叉树BT ⑦void InOrder(BTreeNode *BT);//中序遍历二叉树BT ⑧void PostOrder(BTreeNode *BT);
//后序遍历发二叉树BT
⑨void PrintBTree(BTreeNode *BT);
//输出二叉树BT ⑩void ClearBTree(BTreeNode *&BT);
//清除二叉树BT
2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。①void LevelOrder(BTreeNode *BT)//二叉树的层序遍历
②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度
3、填写实验报告，实验报告文件取名为report10.doc。
4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。
三.函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void InitBTree(BTreeNode *&BT)功能：初始化二叉树BT 思路：将BT指向NULL
函数：void CBTree(BTreeNode *&BT)功能：输入二叉树
思路：按先序次序输入二叉树中结点的值（一个字符）特殊字符 $ 表示空树
函数：void PBTree(BTreeNode *BT,int n)功能：横向打印二叉树
思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树
函数：void CreateBTree(BTreeNode *&BT, char *a)功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子
函数：int EmptyBTree(BTreeNode *BT)功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL
函数：int DepthBTree(BTreeNode *BT)功能：求二叉树BT的深度并返回该值
思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1
函数：int FindBTree(BTreeNode *BT, ElemType x)功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0
函数：void PreOrder(BTreeNode *BT)功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树
函数：void InOrder(BTreeNode *BT)功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树
函数：void PostOrder(BTreeNode *BT)
功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树
函数：void PrintBTree(BTreeNode *BT)
功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树（与输入时相同）
函数：void ClearBTree(BTreeNode *&BT)
功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树
函数（选作）：void LevelOrder(BTreeNode *BT)功能：二叉树的层序遍历
思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素（指针）所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列
函数（选作）：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth(BTreeNode *T , ElemType x)思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可
四.实验结果与分析
（包括运行结果截图、结果分析等）
测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。
五.心得体会
（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）
篇3：二叉树的可视化实现
树形结构在许多方面有应用,可表示层次关系、从属关系和并列关系等。在计算机科学领域中,树形结构是一种非常重要的非线形结构。计算机应用中常出现的嵌套数据,在各种算法问题中,如文件管理、数据库、编译等系统中的算法,都可用树形结构得来表示。二叉树是树形结构的另一种重要类型,许多算法问题用二叉树形式来解决简单灵活,而且树形结构都可以转换成一棵与之对应的二叉树。因此,二叉树是树形结构的关键组成部分,有关二叉树的各种算法也是学习数据结构课程的的重点和难点。数据结构及其算法的教学难点在于它们的抽象性和动态性,我们在学习二叉树的算法时就遇到了难题:首先基于结构化的程序设计思想的算法比较烦琐,同时由于传统的程序设计将数据与操作分开,是孤立地看待问题,对于记录每个顶点的状态,维持各顶点之间的联系比较麻烦。用C或Pascal描述数据结构,不能很好地实现抽象数据类型的思想,只有用C++或Java的类才能很自然地实现抽象数据类型的思想,这为改良教学内容,促进软件复用和设计良好的软件架构,打下了坚实的基础[1];其次学生上机验证二叉树的建立算法时无从知道建立的二叉树是否与所想建立的一致;另外先序、中序和后序三种遍历的动态过程也无法形象直观的得以展现。因此我们若采用面向对象方法描述二叉树,并为学生提供一些接口,能在屏幕上将学生建立的二叉树可视化的显示,并将先序、中序和后序三种遍历算法实现动态同步可视化,这将对学生的学习提供莫大的帮助,同时也可激发学生更浓厚的学习兴趣。
1 二叉树的面向对象描述
1.1 顶点类的设计
顶点类的基本成员有left、right和data,left表示结点的左子树,right表示结点的右子树,data表示结点的数据域。为将复杂的数据结构以直观易懂的形式展现在屏幕上,应设计可视数据结构。可视数据结构就是在顶点类的基本属性和操作的基础上,增加可视属性(如顶点大小,颜色,坐标值等),并提供可视化接口供程序调用[2]。因此为了实现二叉树的可视化增加三个成员id、x和y,id表示结点的完全化编号,x,y表示结点的可视化坐标。
1.2 二叉树的二叉链表实现——二叉链表类的设计
其中root成员表示二叉树的根;cursor成员表示当前结点,称光标;
方法LinkedBinaryTree()构造一棵空二叉树
方法LinkedBinaryTree(String s)构造一棵二叉树,字符串s是二叉树的广义表形式,如a(b(c,d(e,f)),i(j,k(x,y)))
方法LinkedBinaryTree(String s)构造一棵二叉树,字符串s是二叉树的先序遍历序列,如abc**de*g**f***,其中“*”表示子树为空
方法drawNode()在绘图区域绘制二叉树中的结点
方法drawEdge()在绘图区域绘制二叉树的边
方法show()在指定的窗体上可视显示二叉树,
2 二叉树的可视化实现
2.1 完全二叉树的可视化实现
由于屏幕的大小是确定的,所以要将二叉树绘制在这片弹丸之地并非易事。对于教学而言达到教学的目的就可以了,所以我们可对二叉树的高度加以限制,限制二叉树的高度最多为6层,如此二叉树的大小也就限定了,最多有26-1=63个结点,即满二叉树。
满二叉树可采用顺序结构来存储。如果对一棵有n个结点的满二叉树(其深度为log2(n+1))的结点按层次依次编号(从第一层到第log2(n+1)层,每层从左到右),则对任一结点i(1≤i≤n),有:
(1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲Parent(i)是结点[i/2]。
(2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LChild(i)是结点2i。
(3)如果2i+1>n,则结点i无右孩子;否则其右孩子RChild(i)是结点2i+1。
所以现在的问题转化为将含63个结点的满二叉树实现可视化,而可视化的关键是为63个结点设置坐标,结点坐标保存在point类型的数组p[1～63]中,point类有两个成员x和y。我们利用完全二叉树的的特点来实现,方法如下:例如在一个图形框PictureBox上绘制,可将绘图区域分成6层,每一层确定坐标的结点个数和高度为6的完全二叉树的每层结点个数相同,即第一层1个,第二层2个,第三层4个,第四层8个,第五层16个,第六层32个。先确定第六层各个结点的坐标,将绘图区域x轴平分为33份,得到32个坐标即p[32]～p[63]的x坐标为PictureBox.size.x/33*1～32。第五层各个结点的坐标用第六层各个结点的坐标计算得到,计算出第六层每两个结点横坐标的中点坐标,即Parent[i].x=⌊(LChild[2i].x+RChild[2i+1].x)/2⌋(p[i].x=(p[2i]+p[2i+1].x)/2),依此类推,各层结点的横坐标便可确定。每层的结点的纵坐标一样,需要说明的是为了保证视觉效果各层的纵坐标应拉开一定的距离,即LChild[2i].y=RChild[2i+1].y,Parent[i].y=LChild[2i].y-40=RChild[2i+1].y-40,依此类推。这一过程由createPoint()方法来实现。createPoint()方法建立63个点坐标向量,每个点有x和y两个坐标,如此一棵满二叉树的可视化坐标就建立好了。接下来就是绘制结点和边的问题了,由方法drawNode()和drawEdge()来实现。完全二叉树的可视化实现如图1所示。根据图我们可以发现任何两个同层结点都不会相交。
2.2 非完全二叉树的可视化实现
对于非完全二叉树,由于形态各异,为了实现起来简单而且对各种形态的二叉树均适用,运用非完全二叉树完全化的思想来实现,在结点类中增加了一个完全化编号成员,根结点的完全化编号为1,则LChild[2i].id=2*Parent[i].id,RChild[2i+1].id=2*Parent[i].id+1。各结点的坐标采用完全二叉树中对应结点的坐标,如为结点q设置坐标可用如下方法q.setX(p[q.getID()].x);q.setY(p[q.getID()].y,如此非完全二叉树的可视化坐标便可轻松获得,非完全二叉树的可视化就实现了。非完全二叉树的可视化实现如图2所示。
2.3 窗口刷新问题
另外在绘图的过程中,如果直接在窗口绘图,那么当发生窗口刷新(比如窗口最小化后恢复正常)或窗口被覆盖等情况时,所绘图形将被擦除。为避免这种情况发生,可先在绘图区域加载一副背景图片,在图片上进行绘制,如此便不会出现所绘图形将被擦除的情况。
2.4 二叉树可视化的应用
2.4.1 广义表形式建立二叉树
要生成二叉树实例,必须先知实例结点的结构。这必须区分一般数据和实例结点的左右子女链接信息,如指针。这里我们可利用编译技术来解决:把实例结点结构作为字符串参数传入函数,从中分离出各项目及数据类型。在文本框中输入二叉树的广义表形式,如a(b(c,d(e,f)),i(j,k(x,y))),调用LinkedBinaryTree(String s)方法建立二叉树,然后调用show方法可视化显示二叉树。所建二叉树如图3所示。
2.4.2 先序次序输入字符序列建立二叉树
在文本框中先序次序输入字符序列(如abc**de*g**f***,其中“*”表示子树为空),调用LinkedBinaryTree(String s,int pred)方法建立二叉树,然后调用show方法可视化显示二叉树。所建二叉树如图4所示。
2.4.3 动态可视遍历过程和算法的动态演示同步进行的实现
我们在设计动画时采用基于形状的动画。基于形状的动画也称为“子画面”动画,是更强大一种动画技术,在基于形状的动画中,每一个图形对象都成为子画面。并且可以随时间使位置发生变化[3]。以中序遍历为例,上面的窗口是遍历时的动态演示,利用椭圆、直线、文字、填充颜色等手段描绘出顶点,如将当前访问的结点描画成粗线条红色来体现遍历的动态过程;左下窗口是算法执行的动态演示,用字符的反显来体现算法的执行位置;上下窗口的动画演示是动态同步可视化进行的。中序遍历实现相对先序遍历较复杂,中序遍历左子树,访问根结点,然后中序遍历右子树。所以需设四个计时器timer1、timer2、timer3和timer4。遍历的同时还应体现出遍历过程中走过的路径,因此可将中序遍历递归算法中栈的变化情况捕获并加以显示。从栈的变化序列我们能够看出结点的值第一次出现表示结点进栈,该结点不被访问,第二次出现表示结点出栈,即该结点被访问。timer1控制算法的动态演示,timer2用来控制中序遍历的动态可视遍历过程,由于中序遍历的特点算法中访问结点visit(b.data)的图片显示由timer 5来控制,timer4用来控制栈的变化序列的显示,结点进栈则启动timer3,结点出栈则启动timer3。timer3显示了算法中访问结点visit(b.data)的图片后即启动timer2绘制被访问结点,如此便实现了两者的同步。算法的动态演示是通过循环图片来实现的,左右子树的图片不同;中序遍历的动态可视遍历过程是将被访问的结点用红色粗线条重新绘制,并同时在中序遍历序列文本框中显示被访问的结点值。中序遍历序列文本框中的文本变化、栈的变化序列文本框中的文本变化、中序遍历的动态可视遍历过程和算法的动态演示都是同步进行的。
3 实现二叉树可视化的意义
一方面解决了可视显示二叉树的问题,形象直观地将所建二叉树展现在用户眼前,解决了上机难的问题,“百闻不如一见”,介绍或学习抽象概念和训练抽象思维都需要自然和直观的方法。不管对“鱼”进行多么生动的描述,都不如亲眼看一看鱼的动态形象,而且后者能给人留下更深刻的印象。另一方面,实现周游二叉树算法的计算可视化,把周游的过程动态呈现了出来,数据结构及其算法的教学难点在于它们的抽象性和动态性,在课堂授课中采用图示可以在一定程度上化抽象为直观,但很难展现对象的瞬间动态特性和算法的动态执行过程,而这一点我们通过二叉树的可视化做到了。第三个方面,在数据结构中有各种各样的二叉树,如二叉排序树、平衡二叉树、Huffman树、堆、二叉判定树等等,二叉树可视化的实现为这些特殊的二叉树的可视化提供了可能。
摘要：在计算机科学领域中,二叉树是一种非常重要的非线形结构,实现其可视化具有重要意义。本文运用面向对象方法,利用完全二叉树特点实现了二叉树的可视化,实现了周游二叉树算法的计算可视化,实现了动态可视遍历过程和算法的动态演示同步进行。
关键词：二叉树,可视化,面向对象,数据结构,完全二叉树
参考文献
[1]殷人昆,邓俊辉.清华大学“数据结构”精品课程建设[J].计算机教育2006,(5).
[2]苏莹,吴伟民,数据结构可视化类库的设计与实现[J].计算机技术与发展,2006.
篇4：二叉树的遍历研究及还原研究
关键词：二叉树;二叉树的遍历;二叉排序树;还原
中图分类号：G42文献标识码：A文章编号：16723198（2007）11022101
二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：NLR，即先根结点，然后左子树、右子树；中序遍历顺序为：LNR先左子树，然后根结点、右子树；后序遍历顺序为：LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。
二叉排序树对二叉树作了进一步的限定：根结点的权值大于（或小于）左子树中所有结点的权值；根结点的权值小于（或大于）其右子树中所有结点的权值。
那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树？下面以二叉树的前序和中序遍历序列为基础，利用二叉排序树的性质，给出快速还原二叉树的方法。
1由给定前序和中序序列或中序和后序序列还原二叉树的方法
例：前序序列：ABDECFGH中序序列：DEBACGFH（后序序列：EDBGHFCA）
（1）给中序序列中的每个结点从小到大、从左到右赋以权值，如下：
D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8）
（2）还原时读入的序列为前序序列，从左到右依次读入序列中的各个结点值和相应的权值；
（3）由读入的序列，根据第1）步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点，其他结点分别为左右子树中的结点。设根结点为TT，权值为NN，当前读入结点为SS，权值为MM，若MM （4）将SS插入到TT的左子树或右子树的过程中，仍然遵循3）中的规则，直至左子树或右子树为空时止。 （5）读入序列结束时，二叉树还原成功。还原后的二叉树如下图。 （6）对于由中序序列和后序序列还原二叉树是，读入的序列为后序序列，从右向左读入，构造规则同上。还原结果与上述结果完全一致。 2还原方法的确定依据 二叉树遍历过程中，在中序序列中，根结点的左子树中的所有结点都在根结点的左侧，根结点的右子树中的所有结点都在根结点的右侧，这个特点恰好与二叉排序树具有相同的性质；在读入序列时，前序序列则从左向右读，这恰好与遍历二叉树的顺序相同；后序序列从右向左读，则按照根结点、右子树、左子树的顺序还原。 （1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1 （2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。 （3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。 （4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。 （5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。 （6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。 3总结 在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。 参考文献 /* * 4月19日 16:44:48 * 目的:用顺序存储结构来表示二叉树 * 二叉树比较难,所以更应该同过程序来好好理解二叉树的概念， 二叉树的顺序存储结构 题目名称： 二叉树的应用问题 专业班级： 计算机科学与技术 学生姓名： 学生学号： 指导教师： 目录 一、题目要求..............................................二、需求分析..............................................三、概要设计..............................................四、详细设计..............................................五、调试分析.............................................六、心得体会.............................................一、题目要求 实现二叉树，求解若干二叉树应用问题 实现二叉链表表示的二叉树，包括下列运算： 建立一棵二叉树； 按先序、中序和后序遍历二叉树； 按层次遍历； 求一棵二叉树的高度； 交换一棵二叉树的左右子树； 设计一个菜单驱动程序，测试上述算法 二、需求分析 建立一棵二叉树： int CreateBiTree(BiTree &T)按先序遍历二叉树： void PreOrder(BiTree &T)按中序遍历二叉树： void InOrder(BiTree &T)按后序遍历二叉树： void PostOrder(BiTree &T)按层次遍历： void LevelOrder(BiTree &T)求一棵二叉树的高度： int Depth(BiTree &T)交换一棵二叉树的左右子树：int PreOrderTraverse(BiTree T)菜单驱动程序： void menu() 三、概要设计 定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树。 先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。 中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点； （3）中序遍历右子树。 后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。 层次遍历二叉树的操作选用队列的存储结构。先建立一个长度为1的队列，利用while循环，将根结点放入队首，再将队列长度加一。然后依次遍历左子树和右子树，每遍历一次，2、先序遍历二叉树： void PreOrder(BiTree &T){ if(!T) return;cout< 3、中序遍历二叉树： void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout< 4、后序遍历二叉树： void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout< 5、按层次遍历： void LevelOrder(BiTree &T){ BiTree queue[100];int front,rear;if(T==NULL)return;front=-1;rear=0;queue[rear]=T;while(front!=rear){ front++;cout< cin>>a;if(a>=0||a<=7){ switch(a){ case 0: { cout<<“建立后的二叉树为：n”; Output(T); cout< } system(“pause”); break;case 1: cout<<“该树的树深为: ”< system(“pause”); break;case 2: { cout<<“该树以先序遍历输出为：n”; PreOrder(T); cout< } system(“pause”); break;case 3: { cout<<“该树以中序遍历输出为:n”; InOrder(T); cout< } system(“pause”); break;case 4: { cout<<“该树以后序遍历输出为：n”; PostOrder(T); cout< } system(“pause”); break;case 5: { cout<<“该树的层次遍历：n”; LevelOrder(T); cout< （二）详细程序代码：{ if(!T){ cout<<“空树!n”; return;} cout< int Depth(BiTree &T){ int i,j;if(!T)return 0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;} void PreOrder(BiTree &T){ if(!T) return;cout< void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout< void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout< void LevelOrder(BiTree &T) cout<<“<< 1.二叉树树深 >>”< cout<<“<< 2.二叉树的先序遍历 >>”< cout<<“<< 3.二叉树的中序遍历 >>”< cout<<“<< 4.二叉树的后序遍历 >>”< cout<<“<< 5.二叉树的层次遍历 >>”< cout<<“<< 6.左右孩子交换 >>”< cout<<“<< 7.退出 >>”< cout<<“*******************************************************************”< void main(){ int br,a;BiTree T;br=CreateBiTree(T); while(1){ menu(); cout<<“请输入选择的命令-->”; cin>>a; if(a>=0||a<=7) { switch(a) { case 0: { cout<<“建立后的二叉树为：n”; Output(T); cout< } system(“pause”); break; case 1: cout<<“该树的树深为: ”< system(“pause”); break; case 2: { cout<<“该树以先序遍历输出为：n”; PreOrder(T); cout< } system(“pause”); break; case 3: { cout<<“该树以中序遍历输出为:n”; （一）先序输入二叉树： （二）建立一棵二叉树： 1后序遍历： （四）按层次遍历： 3中序遍历交换后的二叉树： 六、心得体会 public T data; //数据域，存储数据元素 public BinaryNode //链域，分别指向左、右孩子结点 //构造结点，参数分别指定元素和左、右孩子结点 publicBinaryNode(T data, BinaryNode { this.data = data;this.left = left;this.right = right; } public BinaryNode(T data) //构造指定值的叶子结点 { this(data, null, null); } publicBinaryNode() { this(null, null, null); } //可声明以下方法 public String toString() { returnthis.data.toString(); } public boolean equals(Object obj) //比较两个结点值是否相等，覆盖Object //类的equals(obj)方法 { returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode } public booleanisLeaf() //判断是否叶子结点 { returnthis.left==null &&this.right==null; } } 二、二叉树中的遍历方法的声明.BinaryTree public BinaryNode //根结点，结点结构为二叉链表 public BinaryTree() //构造空二叉树 { this.root=null; } public booleanisEmpty() //判断二叉树是否空 { returnthis.root==null; } //二叉树的先根、中根和后根次序遍历算法 public void preOrder() //先根次序遍历二叉树 { System.out.print(“先根次序遍历二叉树： ”);preOrder(root);//调用先根次序遍历二叉树的递归方法 System.out.println(); } public void preOrder(BinaryNode //先根次序遍历以p结点为根的子二叉 //递归方法 { if(p!=null) //若二叉树不空 { System.out.print(p.data.toString()+“ ”);//访问当前结点 preOrder(p.left); //按先根次序遍历当前结点的左子树，//递归调用 preOrder(p.right); //按先根次序遍历当前结点的右子树 //递归调用 } } public String toString() //返回先根次序遍历二叉树所有结点的描述字符串 { returntoString(root); } private String toString(BinaryNode //返回先根次序遍历以p为根的子树描述字 //符串，递归算法 { if(p==null)return “"; return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//递归调用 } public void inOrder() //中根次序遍历二叉树 { System.out.print(”中根次序遍历二叉树： “);inOrder(root);System.out.println(); } public void inOrder(BinaryNode //中根次序遍历以p结点为根的子二叉 //递归方法 { if(p!=null) { inOrder(p.left); //中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+” “);inOrder(p.right); //中根次序遍历右子树，递归调用 } } public void postOrder() //后根次序遍历二叉树 { System.out.print(”后根次序遍历二叉树： “);postOrder(root);System.out.println(); } public void postOrder(BinaryNode //后根次序遍历以p结点为根的子二叉树，//递归方法 { if(p!=null) { postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “); } } public BinaryTree(T[] prelist, T[] inlist) //以先根和中根序列构造二叉树 { this.root = create(prelist, inlist, 0, 0, prelist.length); } //以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度.//返回所创建子树的根结点 privateBinaryNode { System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println(); if(n<=0)return null; T elem=prelist[preStart]; //根结点值 BinaryNode //创建叶子结点 inti=0;while(i //在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i); //创建左子树 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//创建右子树 return p; } private void print(T[] table, int start, int n) { for(inti=0;i } public BinaryTree(T[] prelist) //以标明空子树的先根序列构造二叉树 { this.root = create(prelist); } //以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 privateinti=0;privateBinaryNode { BinaryNode { T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String { p = new BinaryNode //创建叶子结点 p.left = create(prelist); //创建p的左子树 p.right = create(prelist); //创建p的右子树 } } return p; } } 三、运行程序 .BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树 public class BinaryTree_make { public static BinaryTree //构造给定的一棵二叉树 { BinaryTree BinaryNode } public static void main(String args[]) { BinaryTree //先根次序遍历二叉树 bitree.inOrder();//中根遍历 bitree.postOrder(); //后根遍历 String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根两种遍历 String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"}; //确定一颗二叉树 BinaryTree bitree1.preOrder();// 先根遍历 bitree1.inOrder();//中根遍历 bitree1.postOrder(); } } //后根遍历 四、运行结果 五、实验内容 1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历 六、附加实验内容 在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。 七、实验报告要求 1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。 期权是一种金融衍生工具, 以期货为基础。期权价值的主要内容是内在价值和时间价值。期权的内在价值是指立即执行期权所能带来的价值。期权的时间价值是指期权没有到期的时候, 所有者因为标的资产价格波动而获得的收益的可能性大小。对期权价值产生影响的因素主要有六个:1、执行价格, 2、标的资产市场价格, 3、到期期限, 4、无风险利率, 5、标的资产价格波动率, 6、预期股利。 在期权合约中, 期权价值的具体表现为期权价格。随着市场供求关系的变化, 期权的价格也会发生相应的变化, 从而会对交易买卖双方的利益造成影响。我们可以看出在期权交易中, 期权价格是一个核心问题, 因而如何使期权的定价合理化就显得非常重要。法国金融学家劳雷斯.巴舍利耶在1900年发表了第一篇有关期权定价的文章。在这之后, 很多金融专家学者也提出了各种公式和定价模型, 但是都不能得到广泛的认同。70年代至今, 期权市场的快速发展促进了期权定价的研究。1979年, 科克斯、鲁宾斯坦和罗斯发表了论文--《期权定价:一种简化方法》, 提出了二叉树定价模型, 该模型的提出使美式期权的定价问题得到了解决。本文将依据二叉树定价模型的原理对美式期权进行研究。 二、二叉树定价模型的基本理论 (一) 基本原理 在二叉树定价模型假定条件下, 股票的价格只能上涨或者下跌。而且我们假定在选取的研究时间段内, 股价每次波动的概率和幅度是相同的。模型将所选取的研究期限分为若干个相等时长的阶段, 然后画出股票价格变化的所有可能路径, 再计算在每一路径上的每一个节点处行权所带来的收益, 最后再将其贴现到研究起始的时点从而得到期权的价格。因为在美式期权情况下, 所有者不用等到交割日再决定是否行权, 他们可以提前行权, 所以计算美式期权价格的时候需要比较贴现计算得到的期权价格和期权行权获得的收益并得出较大者即为期权的理论价格。 (二) 假设条件 ⑴不支付股票红利;⑵不计交易成本与税收;⑶投资者可以运用无风险利率拆出或拆入资金;⑷市场无风险利率是常数;⑸股票的波动率是常数 (三) 二叉树模型的结构说明 当时间为0时, 证券的价格为S。时间为△t时, 证券的价格如果上涨, 则为Su, 如果下降, 则为Sd;当时间为2△t时, 证券价格有三种可能:Su^2、Su、Sd^2。依次往后类推。一般来说, 在时间为i△t时, 证券价格为Sujdi-jj=0, 1, …, i (四) u p d的数值确定: 在现实市场中, 为了描述证券价格的变化而构造二叉树定价模型时, 我们会借助选择u和d来让树形与证券价格的漂移率μ和波动率σ相一致。这时我们就会面临一个问题:是应当选择现实世界的波动率还是选择风险中性定价世界的波动率呢?事实证明选取哪个世界的结果都是一样的 (这里我们不再证明) 。对于很小的一段时间△t以及给定的u和d, 假设波动率在现实世界和风险世界是完全一样的。 首先, 我们假定市场是一个风险中性的世界, 即用无风险利率r代替股票预期收益率μ。 又因为当证券价格遵循几何布朗运动时, 在一个很小的时间段△t内, 证券格变化的方差是S2σ2△t。由方差的定义可得, 定量Q的方差为E (Q2) -[E (Q2) ], 因此 最后, 由考克斯, 鲁宾斯坦和罗斯提出的条件:u=1/d (*) 综上, 可以得出: 当△t很小时, (五) 用MATLAB软件计算股票期权的价格二叉树 因为在利用二叉树进行期权定价时, 价格的计算步骤相当繁琐。为了简化这些重复性的计算过程, 我们借助于常用MATLAB软件来计算结果。 三、二叉树定价模型的简单应用 本文运用三步二叉树模型给恒生指数期权定价并将结果与真实市场价格比较。 ⑴搜集恒生指数2005年至2015年的价格数据, 并计算出历史波动率为σ=0.016近似等于恒生指数收益率的波动率。 ⑵搜集期权的执行价格、到期日。此报告使用9月15到期的执行价格分别为20000和30000的两份合约数据和shibor利率数据。 ⑶以matlab软件为工具, 运用二叉树计算美式期权理论价格。 a.当执行价格K=20000时 看跌期权的二叉树模型如下 看涨期权的二叉树模型如下: b.当执行价格为K=30000时 看跌期权的二叉树模型为: 看涨期权的二叉树模型为: ⑷比较市场价格和模型定价如下表所示: 从上述结果中我们可以看出, 模型定价与市场真实价格大体一致, 但是也存在着一定的误差。且对于看涨期权而言, 它的执行价格越低, 买方行使期权的可能性就越大, 期权价格就会越高;反之, 期权价格则越低。而看跌期权的情况刚好相反, 它的执行价格越高, 则买方行使期权的可能性越大, 期权价格就越高;反之, 期权价格则越高。 ⑸分析定价误差产生的可能原因 a.在现实的金融市场中, 证券价格波动的异方差性广泛存在, 即实际市场中的证券波动性不是确定不变的, 而是随机的。 b.二叉树定价模型假设在整个考察期内股票不支付红利, 而且没有交易摩擦即不计成本和税收, 这些都是理想状态, 现实市场是可能会支付股票红利的, 而且交易是会存在成本和税收的。 c.在本文所研究的二叉树模型中, 我们人为设定参数u和d是一个固定的数, 在整个考察期中都保持不变, 也就是说我们假定股票的波动性是一直保持不变的。实际上, 当整个考察期的时间跨度比较大时, 股票收益率的波动性是会变化的, 不是固定的。 d.在二叉树定价模型的条件下, 我们假设p为风险中性世界里股票价格上涨的概率。一般来讲, 这一概率与现实世界里股票上涨的概率是不同的。 e.排除模型的原因, 由于我国期权市场不是很发达, 没有很健全的监督机制。误差的存在可能是因为我国证券市场中股票期权参与者的非理性炒作而造成。 4、对二叉树定价模型的评价 ⑴优点:二叉树定价模型的算法思想比较简单, 易懂, 即便是在设定步数较大的二叉树模型时, 仍然可以比较精确地得到理论价格。且最突出的优点是无解决了美式期权定价的问题。 ⑵缺点:二叉树定价模型也有一些不足的地方, 比如在步数较少时, 只能对理论价格求近似解, 不够精确;而在步数过大时, 计算步骤较复杂。而且二叉树定价模型的某些假设条件是理想化的, 不符合实际。 摘要：近年来, 随着我国经济实力地不断增强, 我国资本市场也得以迅速发展, 但市场的产品结构仍然单一。然而股票期权可以使资本市场的产品更加丰富, 交易更加活跃。在这一大背景下, 我国出现了第一个场内期权产品——50ETF期权, 该产品的推出标志着我国期权时代的到来。人们想通过期权的交易来获得收益, 所以期权的价格决定是交易中人们最关心的问题。在期权定价模型中, 由于二叉树期权定价模型的理论比较通俗易懂, 而且它所能应用的领域也比较广泛, 因此目前受到大家的追捧。本文将选取恒生指数期权, 利用二叉树期权模型对其进行定价, 做简单的分析研究。 关键词：二叉树模型,美式期权,定价 参考文献 [1]John C.Hull.OPTIONS, FUTURES AND OTHER DERIVATIVES (8 th Edition) .机械工业出版社.2011.9 【二叉树的建立实验】相关文章： 二叉树的遍历实验报告04-17 建立实验教学模式体系05-10 建立艾滋初筛实验室的相关要求05-03 微生物学实验评价体系的建立与实践01-11 实验室计量标准的建立注意事项01-21 基因工程开放实验网络平台的建立09-11 企业、电子商务网站的建立与推广实验报告05-05 浅析实验室管理体系的建立和有效控制01-24 数据库及数据库中表的建立实验报告04-11篇5：二叉树的顺序存储结构
篇6：二叉树的建立实验
篇7：第四次实验--二叉树遍历
篇8：基于二叉树的美式期权定价研究