《二叉树的应用研究.doc》由会员分享，可在线阅读，更多相关《二叉树的应用研究.doc（6页珍藏版）》请在三一办公上搜索。
1、二叉树的应用研究苏雨洁（盐城工学院 优集学院 江苏盐城 224001）摘 要：课堂上学习可以知道，二叉树可以简单明了的表示很多繁琐的信息数据。同时，二叉树在有很多方面有具体的应用。通过搜集各方面的资料发现，越来越多的领域开始选择使用二叉树模型来进行设计投资决策，并以此为平台，实现了很多的功能，本文结合了多领域的知识，给出了在生活方面，学习方面，以及理财投资方面的多种实例，并且加以概括和介绍。关键词：二叉树；数据结构；结点；数组；期权Study on the application of the binary tree SU Yujie(UGS College, Yancheng Institu
2、te of Technology, Yancheng, Jiangsu 224001)Abstract: Through learning in the classroom we can know, binary tree can be simple and clear to show many complicated data.At the same time,binary tree have specific applications in many aspects.Through the collection of information in many aspects,we can f
3、ind that more and more fields start to use the binomial tree model to design,invest and making descisions. Use it as a platform ,achieving a lot of functions. This article incorporates knowledge from many fields and show a variety of examples in the aspects of living, learning, and financial investm
4、ent.And summarize and introduce.Key words: Binary tree;Data structure; Node; Array; Option0引言在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。逻辑上二叉树有五种基本形态：空二叉树，只有一个根结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，完全二叉树；本文根据二叉树
5、的性质形态，研究了二叉树在各个领域的应用实例，并且展望了二叉树在更多领域的应用。1二叉树在学习上的应用1.1二叉树平面坐标网及其应用平面坐标系是把平面上的点映射为一对有序实数，坐标系是形数结合的桥梁。在图形，图像处理中，要处理的点数很多，能都有效的表示点就成为能否有效地处理图形图像的基本问题。数学上普遍使用切分方法，把一个复杂的几何对象近似表示成简单的几何对象的几何，集合中简单的几何对象位置就由其特征点（或点集）的坐标决定。把复杂的几何对象近似的表示成一些矩形或者正方形，然后我们可以用二叉树来表示切分得到的一系列矩形或者正方形的位置关系，从而更简单的研究一个复杂的几何对象。设正方形A的边长为a
6、，以A的左下角为原点建立直角坐标系。左边界为y轴，向上为正方向，下边界为x轴，向右为正向，单位长度为a。坐标系原点（0,0）可以用二叉树表 X0Y0X0Y0X11X12图1 平面坐标系原点相应的二叉树图2 切分Y0结点得到的二叉树示，如图1所示。设2个结点X0，Y0的坐标分布为x=0，y=0。X0的层号为1，Y0的层号为2，如此类推，每一层关联着层步长。1,2层的层步长为1，每一个结点关联着该结点所在层的层步长，称为该结点的步长。例如X0，Y0的步长都是1.结点Y0相应的正方形边长为1，即结点Y0的步长。经过正方形A的中心，平行于y轴的直线把正方形左右切分，为了叙述简便，可称为切分Y0结点。相
7、应的，图1中的二叉树变成图2中的二叉树，X11结点的坐标与X0结点的坐标相同；而X12的坐标等于X0的坐标加上X0结点的步长的一半。X11，X12及第三层的步长都是1/2。左面部分长方形左下角的坐标由结点X11，Y0的坐标决定，即（0,0）。右面部分长方形左下角的坐标可由结点X12，Y0的坐标决定，即（1/2,0）。如果用过这两个长方形的中心，平行于X轴的直线分别把这两个长方形上下切分，就得到4个正方形。把正方形切分得到长方形，把长方形切分得到正方形等等。由于正方形属于长方形，所以为研究方便，以下采用长方形来研究。该长方形左下角坐标由该节点及其父节点的坐标的决定，该长方形的边长分别是上述二个结
8、点的步长。X11，X12的坐标可以统一表示为x=1/2x1。从第一层开始，每增加2层，层步长为原来的一半。按上述方法不断切分，直到生成一棵高为2（n+1）而以y0为根的子树为满二叉树为止。该二叉树的每一个叶节点相应的正方形的边长为1/2n。这些正方形构成平面坐标网，所以这样的二叉树成为平面坐标网二叉树。2二叉树在生活实际上的应用2.1二叉树法在通风除尘风网设计中的应用目前，绝大部分工厂和仓库的通风除尘网设计计算仍采用人工手算进行，由于其中阻力计算部分工作量很大，这样在计算过程中不可避免的产生了误差，从而降低了工作效率，采用二叉树，连表，队列等多种数据结构，则可以准确快速地实现阻力平衡和有关的计
9、算。因此，利用二叉树法来解决通风除尘风网的设计计算问题，不仅能准确迅速地进行阻力计算，而且对于优化设计和风网的调试安装是十分有利的。利用二叉树，在计算过程中就不可避免地产生误差,从而降低了工作效率，通风除尘风网设计计算系统是根据二叉树、连表、队列等多种数据结构,利用计算机来准确快速地实现阻力平衡和有关的计算。主要功能包括风网组合的数据录入,数据修改,设计计算和计算结果打印。这些功能具有如下特点：数据的录入和修改都采用“菜单”提示工作方式。在运行时,根据用户的选择,进入不同的层次,调用不同的子模块。当较低层模块执行完时,自动返回调用层,继续等待用户新的请求。本系统所用全部基本设计参考数据均以随机
10、结构存入软盘,从而大大加快了数据查找的速度,提高了计算机资源的利用率和计算机的运行速度。此系统总体结构如图3。图3 总体结构初始化模块主控制模块录入模块风网数据打印模块原始数据插入删除模块数据查询修改平衡计算模块输出打印模块结束处理模块3二叉树在网络中的应用3.1二叉树多类SVM在网络入侵检测中的应用1入侵检测作为网络安全领域的关键技术，如何迅速，有效地发现各种攻击企图，攻击行为或者攻击结果，对保证网络系统资源的安全起到了至关重要的作用。支持向量机（SVM）是一种建立在统计学习理论基础上发展起来的机器学习方法。传统的SVM算法仅仅对两类问题进行分割，但在实际应用中分类问题可能会多于两类样本，如
11、何有效地将两类问题推广到多类问题，目前已有一些卓有成效的方法，但是在解决了多类问题分类之后如何消除不可分区域并提高测试分类的精度成为一个新的研究问题，于是有人提出了一种基于二叉树结构的多分类器融合方案，融合过程尽可能考虑到类别之前的区分度，从而建立一颗相对优化的二叉树SVM的多类分类算法，并把改进后的多类SVM应用于入侵检测中以提高系统性能。二叉树多类SVM 用于入侵检测的步骤：设计一个二叉树需要选择一个合适的树结构, 即合理安排；树的结点和分支,必须在决策结点,以近似最优的方法将多类样本分为两组,使两组样本的聚类中心距离最大,且每组样本数据分歧最小(即“误差累积”,现象减少到最小),使上层中
12、两个子类之间的可分性尽可能强。各类之间可分性越好,则分类器的分类性能越好。可见,结点分类器的类划分方案在很大程度上影响着二叉树SVM分类器的分类性能。我们用类中心之间的距离来度量类与类之间可分性与先聚类再分类法结合进行,具体改进的算法设计如下。给定具有k类c1,c2,ck的数据集D,假定为训练集中ci类的所有样本,表示集合的样本数,二叉树多类SVM模型的构造算法如下：Step1:计算每个类的类中心,i=1,2,k和任意两个类i,j之间的距离；Step2：计算类i与其他类的距离最小值,i=1,2,k；Step3： 计算与其它类别距离最远的类编号,最远距离为；Step4：根据Step2中计算出的l
13、i,合并li中最小的两个类为一类,直到聚为两类为止,用Step1中的公式计算这两类之间的类距离；Step5：如果则转入Step6，否则转入Step8；Step6：分割出类别p为叶节点, 并把类别p的数据赋予标号+1,剩余的所有类别数据赋予标号-1,训练一个SVM作为二义树结构的一个中间节点；Step7：在分割出p类数据后余下的训练集中,重复计算和,并进行下一次比较,直到余下数据集只有一个类别则转入Step10；Step8：把聚为两类的数据分割为c1和c2两个子集,并对c1赋予标号+1,c2赋予标号-1,训练一个SVM作为中间节点；Step9：对子集c1和c2分别重复计算和,直到两个子集中的数据
14、类别数都只有一类,则设该类标号为叶节点并转入Step10；Step10：训练终止,所有叶节点和中间节点组合构成优二叉树结构。4二叉树在投资决策上的应用4.1二叉树模型在项目投资决策中的应用5传统的项目投资方法主要有DCF法，敏感分析法，决策树法，蒙特卡洛模拟法等，但是往往这些方法没有充分反映实际客观的情况，低估了项目真实的价值，从而导致了短期行为决策，于是，人们找寻到了一种更全面，客观地考虑项目灵活性的价值的方法。利用二叉树实物期权定价模型对项目投资过程中的不确定性问题进行定性和定量分析，研究不确定性与项目投资价值的关系，同时也考虑到投资标的净现值和不确定的机会价值，最后结合了具体案例对实物期
15、权模型分析和净现值分析进行了比较。证明了该方法的灵活性。实物期权定价的二叉树模型在项目决策中的应用案例：甲公司预计2009年开发一项目, 年初一次性投资为4500万元,根据项目当时风险大小,综合分析后确定项目风险调整贴现率k=20%,根据购买国家债券回报率,确定无风险收益率r= 8%,根据传统现金流折现方法, 项目各年净现金折现到2007年年初得现值S=4300万元,则Vn, p=-200万元,故项目应予以取消,对于项目的不确定性,考虑期权的价值, a时间后如果项目产品市场更加明朗,上涨因子u=18,则项目寿命期内各期现金流贴现到2008年初的价值为5800万元;如果项目产品市场低迷,下降因子
16、d=0.58,则现金流价值只有2500万元,市场明朗和市场低迷的概率均为05.根据上述,可得数据如下:I=4500万元,a时间后投资I=I(1+r)=4500(1+0.08)=4860万元，S=4300万元,Su=7800万元,Sd=2500万元,u=1.8,d=0.58,r=0.08.当市场有利时，项目目价值Cu=max (Su-I,0)=max(5800-4860,0)=940万元;当市场不利时,项目价值Cd=max(Sd-I,0)=max (2500-4860,0)=0万元;风险中性概率P=(1+r-d)/(u-d)=(1+0.08-0.58)/(1.8-0.58) =0.4,含有推迟期
17、权灵活性价值的项目价值C=PCu+(1-P)Cd/(1+r)=0.4*940+(1-0.4)*0/(1+0.08)=348.1万元; 所以,含有推迟期权灵活性价值的项目价值为348.1万元。4.2二叉树模型在股票及股票期权定价中的应用1990年哈利.马科维茨，威廉.夏普和默顿.米勒获得诺贝尔经济学奖，让整个实际都注意到新的一门学科-金融学。现代金融理论的核心问题是金融衍生物定价问题，期权和期货是两种金融衍生物。期权定价问题是金融衍生物定价问题中的重要问题之一，考克斯，罗斯和鲁宾斯坦首先建立了二叉树模型，后人又在风险中性市场中如何利用复制来化解风险，运用二叉树模型对欧式期权进行了定价，并利用MA
18、TLAB进行了二叉树的多步实现。某股票的当前价格为40美元，在今后两个3个月的时间段内，股票价格或上涨10%或下跌10%，无风险利率为每年12%（连续复利）执行价格为42美元，6个月的欧式看跌期权价格为多少？利用公式，建立双时段模型，通过Matlab5编程：%s=100;E=100;T=1;r=0.08;M=2;dt=T/M;u=1.1;d=0.9;%p=（exp(r*dt)-d）/(u-d)=0.7041;q=0.2959;s=100;E=100;T=1;r=0.08;M=2;dt=T/M;u=1.1;d=0.9;p=0.7041;q=0.2959;w=zeros(M+1，1);% Asse
19、t prices at time Tfor n=1：M+1w（n）=s*（d(M+1-n)）*（u(n-1)）；end%Option values at time T for n=1：M+1w（n）=max（w（n）-E,0）；end%re-trace to get option value at time zeroFor i=M：-1：1For n=1：i w（n）=exp(-r*dt)*(p*w(n+1)+q*w(n);endenddisp（一年期的欧式看涨期权的价格为）,disp(w(1)运行即得结果：一年期的欧式看涨期权的价格为9.6105. 每个节点上：上方数值=股票价格下方数值=期
20、权价格。5总结二叉树应用相当的广泛，学习上我们在不断的探索，生活中可以帮助我们设计通风除尘的机器，在网络中还能帮我们检测入侵的病毒，在投资决策中还能帮我们判断项目的价值，真是功能强大！也许，二叉树还可以应用于学校企业的电路网设计，也可以用来记录我们平常的消费情况等等。相信在今后的生活中，二叉树的应用还会越来越广泛！ 参考文献1陆波波，黄鸿，任雪梅，张燕.802.11无线局域网安全与应用研究J.微计算机信息，2005,2-5.2陈小玉，朱海华.一种改进的神经网络模型在故障诊断中的应J.微型电脑应用，201026（2）:55-58.3林万里，祁富燕.可编程序控制系统的故障检测与显示J.安全技术与管理，2006,5:46-47.4彭景斌，姜小奇.一种基于主成分分析的时间序列趋势预测方法J.湘潭大学学报（自然科学版）2010(6):123-125.5TAKASHI Shibata. The impacts of uncertainties in a real option model under incomplete informationJ.Eur J Oper Res，2008,187（3）：1368-1379.
