二叉树模型（精选9篇）
二叉树模型 篇1
0 引言
项目决策是发现价值的过程，但要考虑多种不确定性引起的高风险。项目价值评估是项目的关键决策依据；科学的评估方法提供直观、便捷、准确的决策参考指标。曾经一度风靡的折现法(DCF)及其一脉相承的净现值法（NPV），因忽略“不确定性价值”而常常低估那些高风险但高回报的研发项目价值。实物期权方法考虑未来不确定和机会选择权，从不确定性中捕捉盈利机遇，是一种面向未来、更科学的决策思维[1]。
实物期权（Real Option）首先由Myers提出，是金融期权理论对实物资产期权的延伸，其标的资产为非金融资产，认为公司未来的一些投资项目因其所具有的不确定性可能有机会获得超过竞争性费率的收益，许多公司实物资产可看成是一种看涨期权。在Cox、Ross及Rubinstein推出二叉树定价模型后，实物期权理论更是得以飞速发展，现已成为一种新的财务理念和理论，其在各行业的运用成为当今金融研究的热点。
基于二叉树的实物期权法，既能保留NPV的直接外观形式，又能体现对不确定性的科学处理和管理灵活性，是对项目价值合理评估的一种有效方法，认为不确定性越大，实物期权价值就越大[2]。在投资决策中，应用实物期权理论，投资项目价值应视为是用传统方法计算的净现值与一个期权价值之和，即：项目总价值=NPV+期权价值。此时的判断准则为：项目总价值>0，项目可行，但不一定马上投资。在公司投资决策中，资本投资的机会往往取决于项目未来发展状况，未来发展虽存在风险，但风险也伴随着机会。风险越大，期权就越有价值。因为如果项目顺向发展，行使期权，扩大投资，就会增加公司盈利的可能性;如果项目逆向发展，期权不会被执行，限制了公司的亏损[3]。
1 实物期权的种类
企业考虑投资一个项目时须掌握投资时机，有权利选择马上投资还是延缓投资或者不投资：如果市场情况不明朗，可以等待明朗后延迟至适当时机再投资，这是延迟期权；如果投资开始后发现市场状况不景气，投资方案达不到预期效果，可以选择缩减生产规模或暂停投资，这是收缩期权；如果市场状况趋好，消费者需求增加，则可以选择扩大投资规模以适应市场变化，这是扩张期权；如果市场状况相当恶化，投资方案的实施将给投资者带来巨大损失，则可以选择放弃投资，这就是放弃期权;最后，投资者面对多变的市场亦可灵活地采取改变生产的投人与产出方式互相转移使用，以符合消费者需求，这就是转换期权[4]。
2 实物期权定价模型
实物期权定价模式种类较多，理论界和实务界尚未形成通用定价模型，主要估值方法有两种：一是以考克斯、罗斯、罗宾斯坦等1979年相继提出的二叉树定价模型；二是费雪·布莱克和梅隆·舒尔斯创立的布莱克-舒尔斯模型。前者提出的二叉树模型是一个重要的概率模型定价理论，它同B-S模型在很多方面都十分相似，这两个模型对期权定价的结果基本上一致。从逻辑来看，二叉树定价模型可以说是B-S模型的逻辑基础，虽然B-模型是提出较早。但B-S模型过于抽象，且假设项目未来受益的不确定性服从几何布朗运动，导致模型复杂、求解困难，成为应用的障碍。而二叉树定价模型直观易懂，优点是：(1)适用范围广；(2)应用方便，仍保留NPV法分析的外观形式；(3)易于理解，易列出不确定性和决策的各种结果。为提高模型可操作性，假设不同阶段收益服从二叉树过程且相互独立。
下面介绍二叉树定价模型[5]。该模型由J·Cox、S·Ross和M·Rubinstein于1979年提出。假设在期权有效期内，股票价格变动在很短的时间间隔Δt内是二值的。假设有一种不支付红利的股票，现在价格是S，以该股票为标的资产，有效期为T的期权价格为f。在未来T时刻，股票价格或者从S上升到一个新价格Su，或者从S下降到一个新价格Sd。股票价格增加的比率和减少的比率分别为u-1和1-d，对应的期权价格分别为fu和fd。如图1所示。
我们用股票和期权合约构造一份无风险证券组合。假定该组合是M份的股票多头和一份期权合约的空头。当股票由S上升到Su时，该组合价值是m Su-fu；当股票由S下降到Sd时，该组合价值是mSd-fd。该证券组合是无风险证券组合，所以无论股票价格上升还是下降，两个值应相等，故mSu-fu=msd-fd，得m=；将组合贴现到现值，有（msu-fu)e-r T或（msd-fd)e-r T而该组合初始值为m S-f，故（mSu-fu)e-r T=mS-f=（mSd-fd)e-r T，将m=代入可得f=，其中p=。
以上是单期二叉树模型，还有多期定价模型。以下给出两期二叉树模型。同样假设股票开始价格为S，期权价格为f。在第一阶段，股票价格可能上升到Su，相应的期权价格为fu；也可能降到Sd，相应的期权价格为fd。在第二阶段，股票的价格Su可能上升到Su2，对应的期权的价格为fuu；也可能降到Sud，对应的期权价格为f ud。另一方面，股票的价格Sd可能上升到Sud，对应的期权价格为fud；也可能降到Sd2，对应的期权价格为f。如图2所示。
在图2中，其求导如同单期二叉树模型：
由fuu和fud可得到fu=
由fud和fdd可得到fd=
再由fd和fu可得到f=
将前两式代入后式，可得：
3 案例分析
设一家制造企业决定采取战略性期权规避风险。具体有三种战略可供选择：在未来5年内的任何时间，可以选择扩大当前生产规模，或者收缩当前生产规模，或者完全放弃当前生产业务。假设根据未来现金流模型（即以一个合适的市场风险修正贴现率将未来现金流贴现到当前价值），发现公司当前机制下的未来收益的静态价值是100百万美元，应用蒙特卡洛模拟法，得出未来现金流的对数收益率的隐含波动率是15%，未来5年的无风险利率是5%。假设公司拥有这样一份期权，即在未来5年内任何时间，都可以将公司规模收缩10%，从而获得25百万美元的节约，或者以20百万美元成本将公司规模扩大30%，还可以放弃当前的项目，以100百万美元售出其知识产权。
现应用图3标的资产演变图中的值来计算期权估值，网络图如图4所示。
在图4中，我们看到J点的值是255.2百万美元，可以通过在收缩、扩展和完全放弃之间权衡取最大值得到。在第5年末，公司将根据具体情况决定。显然，公司管理层肯定会采用能使公司利润最大化的方案，放弃的价值是100百万美元，扩张的价值是1.3*211.7-20=255.2百万美元，而收缩10%的价值是0.9*211.7+25=215.5百万美元；维持现有规模的价值是211.7百万美元，这可以从图3的标的资产演变二叉树图相同位置节点（Su5）上得到。因此，要使利润最大化，当然选择扩大现有规模，此时J点最大价值为255.2百万美元。类似地，K点可以得到此时收缩现有规模的价值，即此点最大价值为102.5百万美元。
在直觉上也可以看到，如果在当前市场状况下公司的标的资产价值较高（如J点），则这时扩大公司规模是明智的；而如果下降的市场环境迫使公司价值下降到一个很低水平（如K点）,那么此时无疑应将公司规模收缩10%，在水平K以下任何时间———比如M点，放弃当前的项目是最有价值的。
而中间的点，在L点的价值是158.8百万美元，在这个特殊时点，公司面临四个选择：或收缩规模，或完全放弃，或扩大规模，或不执行任何期权而保留在未来执行。在这一点上，选择收缩的价值是0.9*134.9+25=146.5百万美元，放弃的价值是100百万美元，扩张的价值是1.3*134.99-20=155.4百万美元。而选择维持现状是根据风险中性概率得出的未来期权价值加权平均值的贴现。由于风险根据未来期权现金流概率来调整，所以可使用无风险利率贴现，也就是如果继续持有该期权，此时是最大价值：
其中假设无风险利率5%，一期是1,p值0.633。利用后退技术，从网络图终点往前计算得到始值是119.03百万美元，由于标的资产当前价值是100百万美元，故实物期权价值是19.03百万美元；如果对这个项目单独分析，会得到如下完全不同的误导性结果：
只有放弃期权为6.32百万美元，只有收缩期权为15.00百万美元，只有扩展期权为14.49百万美元；这些个别期权之和为35.81百万美元。
显然，分别计算单个期权价值然后相加计算组合期权价值，会与实际有较大差别并导致误判。单个期权价值之和不等于这些期权相互作用的价值，原因在于这些期权互斥性及相互独立性，即这家公司不可能同时在同一时点既扩张又收缩公司规模，或既扩张又放弃该项目，等等。用选择性期权互斥性，在网络图中某一特殊时点对各种期权进行单独分析，就可能导致扩展期权分析认为选择扩展期权是最优的，而收缩期权分析则认为选择收缩期权是最优的等等，从而产生一个更高的总价值；然而，对于一份选择期权而言，三种期权之间的相互作用排除了这种情况出现的可能性，从而避免了价值被高估。这是因为在本例中，同一状态下是不可能同时执行多种期权的。
4 结论
上述案例的实物期权为选择期权，实物投资期权因能使企业避免损失而增值，实物放弃期权因能使企业在有利时机出现时维持投资而增值。由于期权有时间价值，企业在承担初始投资或放弃前会采取观望态度。在其他实物期权案例中，同样可用上述分析方法帮助投资者作出合理决策，实现投资价值最大化。
参考文献
[1]Perlitz M,Peske T,Schrank R.Real options valuation:The new frontier in R&D project evaluation[J];R&D Management,1999,29(3):255-269.
[2]杨春鹏:《实物期权及其运用》[M];复旦大学出版社,2003:5-10。
[3]郁洪良:《金融期权与实物期权———比较和研究》[M];上海财经大学出版社,2003:151-155。
[4]倪亚飞:《基于二叉树的实物期权法在新药研发中的应用研究》[J];《技术创新管理》2009(1):80-83。
[5]刘成华、黄本笑:《风险投资决策中二叉树风险定价模型研究》[J];《科学管理研究》2005(10):161-163。
二叉树模型 篇2
实 验 报 告 册
课程名称：算法与数据结构
实验项目名称： 实验5.二叉树 实验学时： 4 学生学号与姓名： 实验地点： 数计楼四楼 实验日期： 年 月 日 指导老师：
实验5 二叉树
一、实验目的和要求
（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。
二、实验仪器和设备
Visual C++ 6.0
三、实验内容与过程
1.建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。
2.在第一题基础上，求二叉树中叶结点的个数。3.在第一题基础上，求二叉树的深度。
程序清单： 1.2.3.赣南师范大学数学与计算机科学学院
四、实验结果与分析（程序运行结果及其分析）
二叉树模型 篇3
私募股权投资的对象一般是非上市企业, 投资周期长与经营不确定性强是其显著特性, 这就对估值方法产生了新的需求。首先, 对被投资企业进行估值, 一个重要的考核指标是企业的发展动态, 特别是不能简单地把企业过往的业绩作为估值的唯一标准;再次, 由于私募股权的投资周期长, 就必须要将风险、经营不确定性等因素合理的引入到估值方法中。然而传统的估值方法并没有充分考虑企业价值的动态变化及经营不确定性, 因此很难对企业进行准确的估值, 而实物期权法恰恰解决了这一问题, 对私募股权投资目标企业做出准确估值。
1传统估值方法及其局限性
传统估值方法主要有现金流量贴现法 (DCF) 、相对估值法、资产评估法, 其在短期、低风险、较低不确定性情形下能较准确的对目标企业进行估值。但由于经济全球化进程不断加快、移动互联飞速发展, 使得私募股权投资的风险及不确定性显著增加, 传统估值方法也越来越显得不合时宜了。例如现金流量贴现法 (DCF) 局限性在于[1]:首先, 投资活动所具有的不确定性没有得到充分体现;其次, 将投资活动视为一次性和静态的思想也显得不合适宜。另一方面Dixit和Pindyck[2]认为DCF法隐含了错误的假设:投资是可逆的 (Reversible) 、无法递延的, 即停止或放弃投资是没有成本的, 已经完成的投资可以全部收回或者得到相应的补偿。而事实上, 如若投资失败, 先前的投资不仅不能全部收回, 大部分将会直接转化为沉没成本, 因此大部分的投资是不可逆的 (Irreversible) , 而且是可以递延的 (Deferrable) 。Hayes和Gavin[3]指出使用DCF方法容易低估企业的价值, 导致过于短视的投资决策。同样相对估值法、资产评估法也存在着对风险及不确定性难以度量的问题。
从时间坐标来看, 传统估值方法大致是从三个不同时段来分析企业资产的。如图1所示, 主要分为三个时间段:
显而易见, 传统估值方法是站在某一时点上对企业价值进行估算的, 是一种静态、刚性的评价方法, 忽略了企业的经营柔性、管理弹性和战略性等问题, 没有考虑到公司对投资时机的选择, 在大多数情况下并不能十分真实、准确地评估企业的价值, 进而可能导致私募股权投资的决策出现偏差或错误。
2 私募股权投资中的期权特性
2.1 实物期权含义
实物期权 (real options) 的概念最初是由Stewart Myers教授1977年在麻省理工学院提出的, 是金融期权理论在实物 (非金融) 资产上的扩展, 把金融市场的规则引入私募股权投资评估决策中的一种思想 (实物期权与金融期权对比, 见表1所示) , 即投资者进行投资时所能拥有的根据实际情况随时改变投资行为的一种权利。
实物期权首先考虑了目标企业的发展潜力。即作为后续投资必要前提的初始投资, 将不以能立即产生可观的现金收入为目的, 先以部分的前期投资建立期权, 这样企业就拥有了做后续投资的权利。因此, 前期的投资机会可以看作是原始投资加上对企业未来成长潜力的买权。其次考虑了投资的灵活性。如果投资过程中有多种可选方案, 随着时间的推移, 不确定性程度将逐渐降低, 那么就可以依据市场条件选择比较有利的投资方案[4]。第三考虑了管理柔性。当考虑投资一个项目时, 投资者可以对投资时机进行选择, 即马上投资、延缓投资或者放弃投资。如果市场状况不明朗, 则可等市场明朗后再投资, 即延迟期权;如果市场条件没有预期的好, 则可放弃投资, 缩小项目的投资规模, 即收缩期权;如果市场情况良好, 则可履行投资的未来支出, 扩大投资规模, 即扩张期权;如果市场状况相当恶化, 则可选择放弃投资, 即放弃期权[5]。正是由于实物期权法充分地考虑了目标企业的不确定性、风险性及战略性, 因此更适合对不确定性条件下的项目投资进行决策评价。
2.2 实物期权理论在私募股权投资中的实用性
清科研究中心统计, 2013年中国私募股权投资市场, 共新募集完成349支私募股权投资基金 (中国大陆) , 共计募资金额345.06亿美元, 同比增长36.3%;在被投资的23个一级行业当中, 地产行业最为热门, 累计交易105起, 热门投资第二梯队主要以新兴产业 (生物技术/医疗健康、互联网、清洁技术等) 为主, , 投资数量均超过40起 (按案例数, 见图2所示;按投资金额, 见图3所示) 。
不难看出, 2013年私募股权投资主要集中在房地产行业、互联网、电信及增值业务、清洁技术等战略新兴产业, 这此产业大多属于长期性、战略性投资, 具有高风险、高收益的特点, 同时私募股权投资所处的政治、经济环境具有不确定性特点, 投资者可以根据环境的变化更改投资决策, 即所谓的管理弹性, 这使企业投资具有典型的期权特征, 因而适于采用实物期权理论进行投资决策分析。
私募股权投资中, 由于风险性及不确定性程度比较高, 传统的估值方法, 越来越难以对目标企业的实际价值作出正确评估。与传统估值理论恰恰相反, 实物期权方法认为, 未来经营环境的不确定性越高, 则期权价值越大, 相应的投资获得的回报也越大。另外实物期权还具有选择权的灵活性、收益的不确定性、标的资产当前价值的波动性等特性, 这些特性与私募股权投资非常相似, 也符合私募股权投资的特点。实物期权思想逐步被引入到私募股权投资领域, 体现了在不确定条件下价值评估的优势。
Stewart Myes[6]指出一个投资方案所带来的利润, 来自于企业当前所拥有的资产 (S1) , 再加上一个对未来投资机会的选择 (S2) 。即:S=S1+S2。故而在私募股权投资中, 目标企业的价值是由DCF法计算的净现值 (NPV) 与期权价值二者之和组成的, 即:目标企业总价值=NPV+期权价值。这时的判断方法为:目标企业总价值>0, 投资可行, 但不表示马上投资。在私募股权投资过程中, 投资机会常常取决于目标企业未来的发展状况, 未来发展预示着风险与机会同在。风险越大, 期权价值就越大。因为如果项目发展势头良好, 行使期权, 增加投资, 就会提高私募股权投资盈利的可能性;如果项目发展势头不好, 放弃期权, 就限制了私募股权投资的亏损。
3 私募股权投资中二叉树期权估值模型
该模型假定起始阶段投资项目的价值为V, 在每一个时间段内, 投资项目的价值可能有两种变化趋势, 即以概率p上升到u V或以概率q=1-p下降到d V。这样, 在每一期的期末, 投资项目的价值只能取两种可能结果中的一个值。在下一阶段, 投资项目的可能价值为u2V、ud V、d2V。如图4 所示, 上下两个方向的运动变化列出了可能的路径[7]。
二叉树估值模型主要有两种方法: (1) 动态复制技术。期权定价的核心思想就是动态复制技术, 其关键在于找到一个与被评价项目具有共同风险特性的可交易证券, 然后将该证券与无风险债券组合, 复制出相对应的实物期权收益特征。 (2) 风险中性假设。风险中性假设前提是投资者对不确定性持风险中性态度, 其核心是出风险中性概率的构造。期权定价属于无套利均衡分析, 适合于风险中性假设, 许多文献在运用二叉树模型时都采用该方法。动态复制技术与风险中性假设分析的评估结果一致, 本文将运用风险中性假设分析对项目投资进行评价。
设定无风险利率为r, 初始时刻可投资的额度为I, V0为项目的当前现金流入值, V+是项目成功的期望现金流入价值, V-是项目失败的期望现金流入价值, D是项目的期权价值, Du是项目成功时的期权价值, Dd是项目失败时的期权价值, 按照离散模型方法可得:
延迟期权价值
则项目总价值R=NPV+D。
4 私募股权投资二叉树模型算例分析
我们以一个含有延迟期权的私募股权投资项目为例, 某从事新能源开发的公司于2013 年6 月初获得私募股权投资机构500 万元投资, 预计产品投入市场后, 每年能产生现金流量220 万元 (税后) , 现经过公司市场部门考察、调研, 发现该项目最大的不确定性在于市场对新能源的反应情况, 现估计产品未来现金流量波动率为30%。私募股权投资期望回报率为16%, 国债利率为5% (3 年期) , 分析私募股权投资公司是否投资该项目。
(1) 计算项目净现值:
, 依据传统方法判断, 不适合对该项目进行投资。
(2) 计算项目的期权价值:依据风险中性法
风险中性概率为:
期权价值为:
项目总价值:
结果表明, 由于项目总价值大于0, 所以值得对该项目进行投资。又因为马上投资的价值-5.90 万元, 小于0, 所以私募股权投资公司应持有该项期权, 推迟到第3 年再进行投资。
5 结论
实物期权隐含在投资项目中, 它充分考虑了内在和外在两方面的价值, 除了现有现金流价值外, 还考虑了经营柔性、战略性以及不确定性带来的价值, 因此可以更科学地评估目标企业的整体价值, 帮助投资者做出最好的决策, 这就是实物期权法的本质。
摘要：本文将实物期权理论引入私募股权投资决策中, 分析了传统估值方法存在的缺陷及私募股权投资的期权特性, 构建了基于风险中性条件的二叉树期权估值模型, 并对该模型在私募股权投资中进行了实例分析。
关键词：私募股权投资,实物期权,二叉树期权估值模型
参考文献
[1]杨春鹏.实物期权及其应用[M].上海:复旦大学出版社, 2003.
[2]Dixit, A.K.and Pindyck, R.S..The option approach tocapital investment[J].Harvard Business Review, 1995, 73:105-115.
[3]Hayes RH.and Garvin D A.Managing as if Tomorrow Mattered[J].Harvard Business Review, 1982, 60:77-79.
[4]Lucia Santos, Isabel Soares, Carla Mendes, Paula Ferreira.Real Options versus Traditional Methods to assess Renewable Energy Projects[J].Renewable Energy, 2014, 68:588-594.
[5]蔡晓钰, 陈忠, 蔡晓东.房地产投资的实物期权理论研究回顾与述评[J].管理工程学报, 2006, 20:108-112.
[6]Stewart Myes.公司财务原理[M].机械工业出版社, 2008.
[7]刘洪久.不确定环境中模糊二叉树期权价值评估方法研[J].财会通讯究, 2013, 17:37-39.
python二叉树的实现实例 篇4
-03-03python使用cookie库操保存cookie详解
2014-03-03使用python实现扫描端口示例
2014-01-01python检测lvs real server状态
2014-04-04python使用内存zipfile对象在内存中打包文件示例
2014-06-06python教程之用py2exe将PY文件转成EXE文件
2014-04-04python操作xml文件示例
2014-02-02python抓取网页内容示例分享
2014-06-06python网络编程学习笔记(七)：HTML和XHTML解析(HTMLParser、Beau
二叉树的遍历算法 篇5
关键词：二叉树,遍历,满二叉树,完全二叉树
1二叉树
二叉树是由n (n≥0) 个结点组成的有限集合, n=0时称为空二叉树; n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。可见二叉树是递归定义的。 二叉树的结点最多只有两棵子树。因此二叉树的度最多为2。二叉树的子树有左右之分, 即使只有一棵子树也要区分左子树还是右子树。
一棵高度为h的满二叉树是具有2h-1 (h≥0) 个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点按照从根结点开始、 自上层而下层、每层自左而右进行编号, 约定根结点编号为0, 则可以得到一个有序序列。对于一棵高度为h的二叉树, 如果它的每个结点都与高度为h的满二叉树序号为0~n-1的结点一一对应, 则称这棵二叉树为完全二叉树。满二叉树是完全二叉树, 而完全二叉树不一定是满二叉树。完全二叉树的第1~h-1层是满二叉树, 并且该层所有结点都必须集中在该层左边的若干位置上。如图1所示。
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点, 并且每个结点仅被访问一次。虽然二叉树是非线性结构, 但遍历二叉树访问结点的次序是线性的, 而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。
1.1孩子优先的遍历规则
假设有一棵由A、B、C 3个元素构成的二叉树: A为根结点、B为左孩子、C为右孩子, 对其遍历可得到所有的序列有: ABC、BAC、BCA、CBA、CAB、ACB。可以发现, 后3个序列分别与前3个序列的次序相反, 并且前3个序列的共同特点是, B在C之前, 即先遍历左子树还是右子树在算法设计上没有本质区别, 因此约定遍历子树的次序是先左后右, 则二叉树孩子优先的遍历有3种次序, 分别称为先根次序、中根次序和后根次序。规则如下:
(1)先根次序: 访问根结点, 遍历左子树, 遍历右子树;
(2)中根次序: 访问左子树, 遍历根结点, 遍历右子树;
(3)后根次序: 访问左子树, 遍历右子树, 遍历根结点。
二叉树的遍历过程是递归的。如图2所示的一棵二叉树的3种遍历序 列为 : 先根次序ABDGCEFH、中根次 序DGBAECHF、后根次序GDBEHFCA。由此可知 , 先根次序遍历最先访问根结点; 后根次序遍历最后根结点; 中根次序遍历左子树上的结点在根结点之前访问, 右子树上的结点在根结点之后访问。
将一个中缀表达式 (a+b) ×c-d/e表示为一棵表达式二叉树, 两个操作数分别为运算符结点的左、右孩子结点, 运算符都是分支结点, 操作数都是叶子结点, 则按照后根次序遍历可得到后缀表达式ab+c×de/-。
1.2兄弟优先的遍历原则
二叉树的层次遍历是按照层次次序进行的。遍历过程是从根结点开始, 逐层深入, 从左至右依次访问完当前层的所有结点, 再访问下一层。如图2 (a) 所示的二叉树的层次遍历序列为: ABCDEFGH。这种遍历的特点是兄弟优先。
2二叉树的存储结构
如果将一棵完全二叉树的所有结点按照序号进行顺序存储, 根据二叉树的性质, 由结点序号i可知其父母结点、左孩子结点和右孩子结点的序号。将完全二叉树的结点按照次序进 行编号, 实际上是对完全二叉树的一次层次遍历。与非完全二叉树的层次遍历不同, 完全二叉树在按层次遍历到最后一个结点之前不会遇到空子树。如果对非完全二叉树进行顺序存储, 有以下两种办法: 其一, 仅仅存储结点, 则结点顺序存储的线性关系不能反映二叉树中的结点间的层次关系; 其二, 通过补充空子树的方式将一棵非完全二叉树变成完全二叉树的方式, 则不仅浪费存储空间, 而且线性映射关系也不明确, 也不可行。
因此, 二叉树的顺序存储结构仅适用于完全二叉树和满二叉树。二叉树主要采用链式存储结构。每个结点至少要有两条 链分别连接左、右孩子结点, 才能表达二叉树的层次关系。
采用二叉链表结构的每个结点有3个域: data数据域、left左孩子结点、right右孩子结点。一棵有n个结点的二叉树及其二叉链表存储结构如图3所示, 其中root指向二叉树的根结点。采用二叉链表存储二叉树, 设p指向其中一个结点, 则p.left、p.right分别指向其左、右孩子结点 , 每个结点到达其孩子结点所花费的时间是O (1), 这种方式只存储了结点到孩子结点的单向关系, 没有存储结点到父母结点的关系。因此, 要获得父母结点将花费较多时间, 需要从根结点开始在二叉树中进行查找。
为了解决二叉链表存储的二叉树操作效率问题, 可在二叉链表的基础上采用三叉链表结构, 即增加一条链parent连接父母结点。这样三叉链表存储了父母结点与孩子结点的双向关系。 如图4所示。
后面的二叉树操作都基于二叉链表及Java语言。二叉树的操作主要有创建二叉树、获得父母或孩子结点、 遍历、插入和删除等。描述二叉树抽象数据类型BinaryTTree接口定义如下。其中, 泛型T为结点的元素类型。
二叉树主 要由二叉 树结点类BinaryNode和二叉树 类BinaryTree共同完成。BinaryNode的定义如下。
为了方便地更改结点间的链接关系, BinaryNode类声明中成员变量的访问权限定义为public, 允许其他类访问。否则, 要提供公有方法set、getData、getLeft、getRight等, 提供给其他类调用。
二叉树类BinaryTree及其部分成员方法声明如下, 其中成员变量root指向二叉树的根结点。
3二叉树的遍历
3.1递归遍历算法
作为遍历问题的基本点, 需要在BinaryTree类中增加先根次序、中根次序、后根次序遍历二叉树的成员方法。 这3种遍历算法都是递归算法, 差别只是在于结点的访问时间不同。具体实现如下。
递归方法必须有参数, 通过不同的实际参数区别递归调用执行中的多个方法。一棵二叉树由多棵子树组成, 一个结点也是一棵子树的根。因此, 二叉树中实现遍历规则的递归方法以结点p为参数, 比如preOrder (p) 表示以先根次序遍历以p结点为根的子树, 当p指向不同结点时, 遍历不同的子树; 当p为空子树时, 递归结束。每个遍历算法都有两个重载。
3.2二叉树基本操作
基于二叉树遍历的基本操作有: 构建二叉树、求结点个数、求高度、 查找、求父母结点、替换、插入、 删除等。根据不同的应用需求, 可采用不同的次序进行遍历。
3.2.1 构造二叉树
由于二叉树是数据元素之间具有层次关系的非线性结构, 而且二叉树中每个结点的两棵子树有左右之分, 因此建立一棵二叉树必须明确两点: 结点与父母结点及孩子结点之间的层次关系; 兄弟结点之间的左右子树的次序关系。
二叉树的一种遍历序列将二叉树的非线性关系映射成一种线性关系。因此, 已知一棵二叉树可得到唯一的一组先根、中根和后根或层次遍历序列; 但是, 已知二叉树的一种遍历序列却不能唯一确定一棵二叉树。以下讨论两种能够唯一确定一棵二叉树的表示法。
3.2.1.1 先根和中根序列表示
由于先根次序或后根次序反映父母与孩子结点的层次关系, 中根次序反映兄弟结点间的左右次序。因此, 已知先根和中根两种遍历, 或中根和后根两种遍历序列, 能够唯一确定一棵二叉树。证明过程如下:
已知: 二叉树的先根和中根两种次序遍历序列, 可唯一确定一棵二叉树。
证明: 假设数组prelist和inlist分别表示一棵二叉树的先根和后根次序遍历序列。序列长度均为n。
(1)由先根次序遍历算法可知 , 该二叉树的根为prelist[0];该根结点必定在中根序列中 , 假设它在中根序列inlist中的位置为i, 则有inlist [i] =prelist [0]。
(2) 由中根次序遍历算法可知, inlist [i] 之前的结点在根的左子树上, inlist [i] 之后的结点在根的右子树上。因此, 根的左子树由i个结点组成, 子序列为:
左子树的先根序列: prelist [1] ,…,prelist [i]; 右子树的中根序列: inlist [0] ,…,inlist [i-1]。
根的右子树由n-i-1个结点组成, 子序列为:
右子树的先根序列: prelist [i+1] ,…,prelist [n-1]; 右子树的中根序列: inlist [i+1] ,…,inlist [n-1]。
(3)如此递归, 可唯一地确定一棵二叉树。
同理可证明: 中根与后根次序遍历可唯一地确定一棵二叉树; 先根和后根次序遍历序列不能唯一确定一棵二叉树; 同一个层次遍历序列不能唯一确定一棵二叉树。
上面的证明过程实际上描述了由先根和中根序列如何构造一棵二叉树的过程。在BinaryTree类中增加以下构造方法, 以先根和中根次序遍历序列构造二叉树。
3.2.1.2 标明空子树的先根序列表示
已知一棵二叉树的先根遍历序列为AB, 则能够确定A是根结点, 并且B是A的孩子结点, 但不能确定是哪个孩子, 可能是左孩子, 也可能是右孩子。这是因为先根序列只能反映父母与孩子结点之间的层次关系, 不能反映兄弟结点之间的左右次序。
如果在先根遍历次序中标明空子树, 通过空子树位置反映兄弟结点之间的左右次序, 则可唯一确定一棵二叉树。比如, 以 ^ 表示空子树, 则二叉树及其先根次序遍历序列如图2所示。
这种标明空子树的先根便利序列, 明确了二叉树中结点与父母、孩子以及兄弟结点之间的关系, 因此能够唯一地确定一棵二叉树。设prelist表示一棵已标明空子树的二叉树的先根次序遍历序列, 则构造二叉树的递归算法如下:
(1)prelist [0]一定是二叉树的根 , 创建根结点。并且prelist [1] 一定是根的左孩子。
(2)如果prelist [i] 不是空子树 , 则创建一个结点 , 该结点的左孩子结点元素时prelist [i+1], 但父母与孩子之间的链接还未建立; 否则, 当前子树为空, 返回上一层结点。
(3)返回到当前结点时, 下一个元素prelist [i+1] 是当前结点的右孩子结点; 当一个结点的左、右孩子的链接都已建立, 则以当前结点为根的一棵子树已经构建好, 返回上一层结点。
(4)重复执行步骤 (2)、 (3), 直到返回根结点, 则二叉树构建完毕, root指向根结点。
在BinaryTree类中增加以下构造方法, 以标明空子树的先根序列构造一棵二叉树。
其中, prelist数组保存标明空子树的先根序列, create(prelist)方法创建一棵子树 , 子树的根值是prelist [i] 。由于create(prelist)是递归方法, 参数按照层次关系变化, 而i是数组下标, 从0递增到preorder.length-1, 因此i不能作为方法的参数, 也不能作为方法的局部变量, 只能将它作为BinaryTree类的私有成员变量, 相对于create方法是全局变量。
3.2.2 求二叉树结点个数
在BinaryTree类中增加count方法, 返回一棵二叉树或子树的结点个数。
3.2.3 求二叉树高度
一棵二叉树的高度是其较高的一棵子树的高度加1。因此求二叉树的高度必须采用后根次序遍历算法, 首先分别计算出左、右子树的高度, 再计算以当前结点为根的子树高度。在BinaryTree类中增加height方法, 返回一棵二叉树或子树的高度。
3.2.4 查找
在BinaryTree类中增加search方法, 在一棵二叉树或子树中查找关键字为key的元素, 返回首次出现的关键字为key的元素结点。若未找到, 则返回null。该方法采用先根次序遍历算法在二叉树中查找。
3.2.5 获得父母结点
在BinaryTree类中增加getParent方法 , 返回指定 结点node的父母结点。
3.2.6 插入结点
在二叉链表的二叉树中, 链的方向是单向的, 都是由结点指向其孩子结点, 没有指向其父母结点的链。与单链表的插入操作类似, 在二叉链表的二叉树中插入一个结点p, 需要修改p的父母结点的left或right域。因此 , 在二叉树中插入一个结点, 需要指定插入结点作为哪个结点的左孩子还是右孩子。在BinaryTree类中增加以下方法 : insertRoot (x) 方法插入元素x作为根结 点 , 原根结点 作为其左 孩子 ; insertChild ( p,x, leftChild) 方法插入元素x作为p结点的孩子, p结点的原左/右孩子成为新结点的左/右孩子, leftChild指定左/右孩子, 取值为true (左孩子)、false (右孩子), 返回插入结点。
3.2.7 删除一棵子树
在二叉链表的二叉树中删除一个结点p或一棵子树, 需要修改p的父母结点的left或right域。如果只删除一个结点p而不是删除一棵子树, 则需要约定如何调整子树结构的规则。换言之, 若删除一个结点p, 原先以p结点为根的子树则变成由原左子树和右子树组成的森林, 约定一种规则使这个森林组成一棵子树。这里简化, 只讨论删除一棵子树问题。
在BinaryTree类中增加以下删除一棵二叉树或子树的方法:
3.2.8 叶子结点
在BinaryTree类中增加以下方法, 判断某个结点是否为叶子结点; 计算叶子结点的数量。
3.3二叉树的层次遍历
二叉树层次遍历的特点是兄弟优先。两个兄弟结点的访问次序是先左后右, 连续访问; 它们后代结点的访问次序是: 左兄弟的所有孩子一定在右兄弟的所有孩子之前访问, 左兄弟的后代结点一定在右兄弟的同层后代结点之前访问。
在BinaryTree类中增加以下二叉树的层次遍历算法, 其中使用链式队列存储二叉树结点BinaryNode
3.4二叉树的非递归算法
二叉树电子家谱设计 篇6
1 电子家谱系统简介
1.1 系统复杂性
李士勇认为复杂性是指系统在演化过程中和环境交互作用, 呈现出的复杂的动态行为特性和突出的整体特性。除此之外, 人们一般认为复杂系统是由众多存在复杂相互作用的组分 (或子系统) 组成的。家谱系统涉及众多子系统, 形成了规模庞大的多层次结构, 因此家谱系统具有多方面的复杂性。
1.2 系统结构
家谱是家族成员间相互联系组成一种体系结构。同家谱数据中由后代节点和父代节点分别组成家谱树的特点对应, 家谱系统通常采用树形结构。
2 二叉树家谱系统设计
2.1 家谱的体系结构
二叉树能够很好的反映家谱中成员之间的关系。本文系统中使用父子——兄弟结构, 即左子树第一个节点为父节点的儿子 (或兄弟) , 同理右子树第一节点表示父节点的兄弟 (或儿子) 。并且采用三叉链表的方式存储二叉树, 不仅便于对字节点进行查找, 还可以回溯查询关联节点确定成员间关系。
2.2 家谱成员及功能设计
2.2.1 数据单元设计
选定家族成员作为数据基本单元, 并在程序中定义为结构体Bi TNode。因为在一个家族中, 家谱中每个家族成员是最基本的组成部分。Bi TNode结构如下:
typedef struct Bi TNode{
标记、姓名、生日、住址、婚否、建在否、性别、妻子 (如已婚) 、死亡日期 (如已死亡) ;
struct Bi TNode*lc, *rc, *father;
}Bi TNode, *Bi Tree;
2.2.2 功能设计
系统设计了多种实用功能, 主要功能有:
3 设计实现的注意要点
建立树时, 由于新申请结点的孩子指针、兄弟指针等均未赋空值;但在函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用函数时出现系统保护异常 (使用了不安全的指针) 。因此在系统初始化时, 需要对以上几种属性赋予无影响初始值。
删除结点时, 只考虑到删除本身结点, 而其孩子结点的情况未考虑, 故在删除某些结点时会出现“断链”现象。故在删除某一结点时, 首先要判断此结点是否有孩子及兄弟, 然后进行相应操作。
4 结语
电子家谱系统是一种重要工具, 它使家谱得以充分保护和使用。笔者的二叉树电子家谱系统设计提高了家谱使用的实用性和易用性, 为家谱系统的电子信息化打下了一定基础。家谱电子信息化是一个庞大的系统工程, 今后我们将研究家谱便易搜索算法以及家谱成员流动模式。
参考文献
[1]王鹤鸣.中国家谱通论[M].上海:上海古籍出版社, 2010:4.
[2]司马贺.人工科学:复杂性面面观[M].上海:上海科技教育出版社, 2004:78-79.
[3]李士勇.非线性科学与复杂性科学[M].哈尔滨:哈尔滨工业大学出版社, 2006:23.
二叉树操作的递归算法分析 篇7
二叉树是数据结构课程内容中的重点和难点,学好数据结构就必须要掌握二叉树的存储结构和基本操作的算法。二叉树最常用的存储结构是二叉链表,根据二叉链表的示意图,我们很容易理解二叉树的这种存储形式。因此,掌握二叉树的关键就是要理解二叉树基本操作的算法。本文将分析二叉树操作的递归求解方法,以求和数据结构爱好者共同学习和研究。
2 递归
递归是一种非常有用的算法设计工具。一个函数、过程如果在其定义或说明内部直接地或间接地出现有其本身的引用,这种用自己定义自己的方法称之为递归[1]。
递归方法实际上是将一个原问题转化为和原问题相同的子问题,只不过子问题的规模比原问题的规模要小。这种转换多次进行,直到满足某个约束条件为止。用递归方法求解问题关键就是要确定两方面内容:(1)子问题(2)递归结束条件。
例如:求n!
因此,可将原问题“求n!”转换为子问题“求(n-1)!”,原问题和子问题为同样的问题,都是求某数的阶乘,但子问题数字小。随着不断转换,子问题数字越来越小,当求1!时,可直接给出值1。所以,递归结束条件就是n=1。
3 二叉树操作的递归求解方法
二叉树的特点是每个结点至多只有两棵子树(左子树和右子树),且左右子树也是二叉树。因此,二叉树或者为空,或者可分为三部分:根结点、左子树、右子树。由于二叉树中的左子树和右子树也是二叉树,因此,二叉树的组成具有递归的特点,那么,二叉树的许多操作可考虑用递归方法来描述。下面将讨论几个常见二叉树操作的递归算法。
3.1 遍历二叉树
遍历二叉树是指按某条搜索路径巡访二叉树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次[2]。常见的二叉树遍历方法有三种:先序遍历、中序遍历、后序遍历,下面以先序遍历为例,分析其递归算法。
先序遍历二叉树的思想是:若二叉树为空,则没有任何结点可访问,因此空操作;当二叉树不为空时,先序遍历二叉树就是要:访问根结点、先序遍历左子树、先序遍历右子树。采用递归方法分析:1)原问题为先序遍历二叉树。2)原问题可分为三步:访问根结点、先序遍历左子树和先序遍历右子树。访问根结点直接对应访问语句,例如输出语句。先序遍历左子树和先序遍历右子树这两个问题都属于先序遍历二叉树的问题,与原问题一样,只不过左子树和右子树比原二叉树规模要小。因此,子问题为先序遍历左子树和先序遍历右子树。3)递归结束条件就是二叉树为空。
确定递归算法的子问题和递归结束条件后,就可写出先序遍历的递归算法:
3.2 建立二叉树的二叉链表
建立二叉树的二叉链表存储结构是二叉树的必备操作,因为在程序中,只有创建了二叉树的二叉链表存储结构,才可以进行二叉树的其他操作。显然,二叉树中的每个结点对应二叉链表中的一个结点,因此,创建二叉链表,就是要为二叉树中的每个结点建立一个结点存储结构。可以按照某种遍历顺序依次为各个结点建立存储结构。若按照中序遍历顺序或后序遍历顺序建立,则在建立二叉链表过程中,已建立的结点是分散的、不能连接成一个链表,这就不易掌控所有已建立的结点。如果按先序遍历顺序建立,则已建立的结点都可链接在根指针所指的二叉链表中。因此,可按先序遍历的顺序为各个结点建立存储结构。
建立二叉树的二叉链表的算法思想是:若二叉树为空树,则根指针应设置为空;若二叉树非空,则为根结点建立存储结构,再建立左子树的二叉链表和右子树的二叉链表。采用递归方法分析:1)原问题为建立二叉树的二叉链表。2)子问题为建立左子树的二叉链表和建立右子树的二叉链表。3)递归结束条件是二叉树为空树。
根据用户输入的序列,建立二叉树的二叉链表的递归算法如下:
使用此算法建立二叉树的二叉链表,用户在输入结点序列时要注意:空子树也要输入,用空格代表空子树。例如图1所示二叉树,应首先标出空子树,见图2,然后对其先序遍历得到输入序列:AB__CD__E__。
3.3 求二叉树的深度
二叉树深度可按如下规则求取:当二叉树为空树,则深度为0;当二叉树只有一个结点,则深度为1;否则,二叉树的深度为左子树深度和右子树深度中的较大值,再加上1。采用递归方法分析:1)原问题为求二叉树的深度。2)子问题为:求左子树深度和求右子树深度。3)递归结束条件是二叉树为空或者二叉树只含有一个结点。根据上面分析,可得到如下递归算法:
3.4 返回结点e的左兄弟
采用递归方法分析:1)原问题为在一棵二叉树中找结点e的左兄弟。2)子问题可设定为在左子树中找结点e的左兄弟,和在右子树中找结点e的左兄弟。3)递归结束条件可有两种情况:a)若二叉树为空树,则结点e的左兄弟不存在;b)若根结点的右孩子为结点e,则结点e的左兄弟为根结点的左孩子。递归算法如下:
4 总结
二叉树是数据结构课程中的重要内容,掌握二叉树关键是掌握二叉树各种操作的算法。本文采用递归方法分析了二叉树的先序遍历、创建二叉链表、求深度、求结点e的左兄弟这四个操作的求解方法。对于二叉树的许多其他操作,也可以与此类似,采用递归方法求解。
摘要：二叉树是数据结构课程中的重点内容。由于二叉树本身具有递归的特点,因此二叉树的许多操作可采用递归方法求解。该文首先介绍了递归方法,然后采用递归方法分析二叉树的几个常见操作,并给出详细算法。
关键词：递归,二叉树,遍历,算法
参考文献
[1]李伟.浅析C语言递归算法[J].电脑知识与技术,2012(10).
二叉树结构的文本模式显示 篇8
检查二叉树结果可以通过输出二叉树的遍历结果来进行,尤其是层序遍历[2];也可以在集成开发环境中通过监视(Watch)追踪左右子树,这不直观也非常繁琐。图形显示二叉树是比较直观和形象的[3],因此在教学中可以采用图形显示[4,5],比如图1;但是它的缺点也很明显,要求学生掌握一定的图形编程,而不少学生在学习数据结构的时候图形编程基础比较弱,因此教与学往往是在命令行的方式下进行输出,即通过printf或cout进行输出(C/C++语言),所以采用图形输出进行数据结构教学有一定的局限性。
叶品菊等开发了在文本方式下显示二叉树的方法[2],该方法用层序进行输出,每一层输出在一行中,但该方法父结点与子结点之间没有任何东西相连(如图2),因而输出的图形不像一颗树,而是结点的有规律的排列,显示的直观性略差。任燕在其编著的教材《数据结构C++语言描述》[6]中,二叉树的示例图是屏幕截图的,从图中可以看出它利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,显示效果非常直观与形象,与图形模式下的显示方式基本相同,只是链式存储二叉树需要转换成顺序存储二叉树,“以便使链式存储二叉树能以树状形式显示”[6]。该文给出了一种文本模式的二叉树结构显示方法,该方法利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,使用队列对链式存储二叉树进行层序输出,该方法进行较小的改动可以应用于顺序存储二叉树的显示,加入特殊字符’|’经适当修改也可顺利地显示3阶B_树。由于该方法直观形象且是文本模式,因而可以作为数据结构教与学的有效手段之一。
1 显示方法
文本模式下的二叉树显示主要的是计算结点的输出位置,输出位置是由空格的多少来决定的,父结点与子结点之间的连接由三种特殊字符’_’、’/’和’’构成。倒数第一层和倒数第二层之间只需’/’和’’就可连接,左子树由’/’连接,右子树由’’连接。其它层数之间的结点连接由两行构成,第一行连接线由一个或多个’_’与’/’或’’构成,左子树的连接线形如“_____/”,右子树的连接线形如“_____”;第二行的连接只需’/’和’’,左子树是’/’,右子树是’’。其它非连接线位置由空格填充。为了让斜线(/或)指向结点位置,结点不在斜线(/或)的正下方(文献[6]是在正下方),而是偏一格,这样底层结点相邻3个空格,这样的显示效果比文献[6]中的显示效果更为自然和美观。输出的具体编排见图4。
为了计算空格的个数,需要知道二叉树的显示宽度。由于底层结点相隔3个空格,因此二叉树的显示宽度为满二叉树的底层结点数乘4,高度为5的二叉树显示宽度是64个字符长度,高度为6的二叉树显示宽度是128个字符长度。而在文本模式下,由于文本模式每行80个字符(缺省属性)的限制,该文的显示方法只能显示高度不超过5的二叉树。如果要显示高度为6的二叉树,有两种方法,一是修改文本模式每行显示宽度的属性,只要每行可显示超过128个字符即可;二是显示时采用紧凑格式,结点在斜线的正下方[6],这样底层相邻结点之间只有一个空格,高度为6的二叉树显示宽度为64,显示效果见图5,与图3相比美观性略差。文献[2]采用分页的方式来显示高度超过6的二叉树。考虑到该文的方法主要用于教与学,高度为5的满二叉树有31个结点,对于教学来说高度与结点数都足够,因此该文方法不需其它的改动完全满足正常的教学要求。
空格的具体个数依赖于结点所处的层数,计算时分数据域行、第一行连接符和第二行连接符,倒数第一层和倒数第二层之间只有第一行连接符。具体计算公式如下:
数据域:(2n-2个□)a(2n+1个□)(n为树高,□代表空格,a为数据)
第一行连接符:(2n-1个□)(2n-1-3个_)/□(2n-1-3个_)(2n-1+3个□)
第二行连接符:(2n-1-1个□)/(2n-3个□)(2n-1+2个□)
计算第一行连接符时,n=2将导致2n-1-3=-1,因此前面的空格需要减少一个,即2n-1个空格变为2n-1-1个空格。第二行连接符计算时,不会出现这种问题,因为n=2时没有第二行连接符。
2 程序实施
根据以上方法采用C++进行编程,二叉树的类定义如下:
二叉树的输出是从根结点开始,一层一层地输出。每一层分3行输出,第一行输出结点数据,简单起见结点数据类型为字符型;第二行和第三行为连接符,第一行连接符包括三种字符’_’、’/’和’’,第二行只包括’/’和’’两种字符。如果不用字符’_’而用字符’~’也可以,此时第一行连接符包括’/’和’’,第二行包括’~’、’/’和’’三种字符。倒数第一层没有连接符,倒数第二层没有第二行连接符。每一行输出时一个结点一个结点地输出,空结点也需输出,只是结点数据和连接符全部用空格替代。
由于整体输出顺序是层序,因此用结点指针型的队列来处理层序输出;每一层的结点需重复3次进行输出处理,每个结点处理完后需要放回到队列以便重复提取。每一层的3行输出结束后队列需要更新,即下一行的结点进入队列。由于空结点也需处理,队列一直不空,为了充分利用队列,用一个临时结点来表示一层结点的处理结束,否则需要计数处理。加了注释的代码如下:
由于空结点也需要处理,因此代码中有大量的分支语句;为了压缩代码长度,程序编制时大量使用了三目运算符?:。即使这样程序仍有70余行,如果希望进一步压缩代码,三行输出的循环控制压缩到一个循环,此时第一行和第二行的连接符需要存储在两串字符串中,循环结束再输出。这样处理后代码压缩到50余行,压缩量不大且可读性略有下降,不建议这样处理。
3 实例应用
二叉树是数据结构中的基础数据类型,因此应用的地方较多,该文举几个简单的例子。二排序叉树是有利于搜索的数据类型,采用该文方法把搜索的结果用特定字符’*’标识出来如图6。哈夫曼树是一种最优二叉树,带权的初始结点都在叶子上,构造过程中新建的结点都是分支结点;哈夫曼树可以采用顺序存储[6],该文方法略作修改即可应用于顺序存储,用特殊字符’@’标识分支结点显示的哈夫曼树如图7。平衡二叉树是一种优化后的二叉排序树,它的左右子树的高度不超过1,每个结点有一个平衡因子表示左右子树的平衡情况,可以用更为直观的符号表示平衡因子,即’>’代表1、’=’代表0和’<’代表-1,显示时把数据域后面的空格减少一个,用于输出平衡因子的代表符号,显示结果如图8。B_树是一种多路平衡查找树,可用于外部文件的动态查找,B_树的插入与删除算法比较复杂,非常适合学生的编程技能训练,在调试过程中如何快速有效地检查结果比较麻烦,采用该文的方法经适当地修改可以方便地显示3阶B_树。为了显示3阶B_树,增加一个符号’|’指向中间的子树,最重要的修改是显示起始位置的计算,另外用字符’~’替代了字符’_’,此时第一行连接符包括’/’、’|’和’’,第二行包括’~’、’/’、’|’和’’四种字符,这样显示的效果也非常好,如图9。
4 结论
二叉树结构的文本模式显示方法使用了’_’、’/’和’’三种字符来显示二叉树的结构,由于不涉及图形操作,该方法有很强的可移植性,不论TC环境或者VS环境,该文提供的代码都可直接使用。该文的方法也可方便地改为独立的函数,也方便其它的语言实现。该方法方便了树型数据结构程序的调试,不仅可以应用于各种二叉树,也可应用于三叉树,比如3阶B_树。由于直观地显示了二叉树的结构,因而可以提高教与学的效率。同时,算法也使用了队列,对学生巩固已学过的数据结构知识非常有帮助。
参考文献
[1]中国计算机科学与技术学科教程2002研究组.中国计算机科学与技术学科教程2002[M].北京:清华大学出版社,2002.
[2]叶品菊,吴斌,胡远望,等.直观显示二叉树结构的算法[J].江南大学学报:自然科学版,2008,7(1):60-63.
[3]刘福君,李华,王玉森,等.基于二叉树的故障树画树算法研究[J].计算机技术与发展,2006,16(7):117-118.
[4]刘惠敏,董毅.动态模拟二叉树的建立[J].黄冈职业技术学院学报,2004,6(1):75-76.
[5]白雪峰,李沛.二叉排序树的建立及对其中序遍历的动态模拟[J].电脑知识与技术,2005,12(8):84-86.
二叉树模型 篇9
关键词：电路结构优化,二叉树优化法,CVSL电路,互补CMOS逻辑
0 引 言
CVSL电路适合于整个系统或模块的高速设计中。在单端式逻辑(Single- ended logic)和差动式逻辑间需要提供互补信号的反相器[1]。对于复杂逻辑,由于两个NMOS Tree有共同项,电路可进一步化简,减少MOS管数量。传统的方法是用卡诺图法,但卡诺图并不能显示出电路的连接关系,若改用二叉树算法,则可以很明了的反映出电路的连接关系。
1 CVSL电路的特点
互补静态CMOS特点电路的特点是P管阵列的逻辑结构正好是N管阵列的对偶,若一阵列是串联,则另一阵列必定是并联。NMOS阵列是原量控制,PMOS阵列是非量控制, 因而,N型阵列和P型阵列可以接同一个输入信号[2]。电路中PMOS管的数目与NMOS管的数目相同。如果输入变量共有k个,则总共需要2k个晶体管,形成一种全互补电路。但管子数量多,版图可能比较复杂。只有设计得当, 版图才会有规则。
虽然CMOS电路有许多优点,但一般认为其与伪NMOS相比有两大缺点:
(1) CMOS电路的速度比伪NMOS低。任何一级CMOS倒相器至少有两只管子,一只P管和一只N管,它们的栅极是连接在一起的,输入电容加倍,前级的充放电就比较慢。
(2) CMOS电路所需的器件数多。一个逻辑电路需要设计两套逻辑函数,分别传送原函数和其补函数。因而,CMOS电路的 逻辑冗余度较高。不仅浪费硅片面积,而且增加互联任务,使性能降低[3]。伪NMOS电路只采用一个P管作为上拉负载,以代替全互补标准CMOS电路中的P阵列逻辑。但增加了静态功耗,提高了输出低电平,降低了噪声容限。为克服功耗提出电路的改进方案即CVSL电路[4],如图1所示。
由于电路同时接收差动式的输入(Differential Input)且提供差动式的输出(Differential Outputs),所以又称为DCVSL(Differential Cascade Voltage Switch Logic)电路。并且原量反量同时输出。虽然比CMOS所用MOS管数量多,但提供互补输出且由于电子迁移率高于空穴,相同面积下速度比CMOS高(是一种高速设计)。由于存在正反馈,完全消除了Pseudo-NMOS中的静态电流,使输出达到rail to rail(低功耗高噪声容限),进一步提高了翻转速度。
该电路适合于整个系统或模块都用DCVSL的设计,在单端式逻辑(Single- ended Logic)和差动式逻辑间需要提供互补信号的反相器。对于复杂逻辑,由于两个NMOS Tree有共同项,所以电路可进一步化简,减少了MOS管数量。
2 用二叉树优化CVSL电路
任何一个逻辑表达式F可表示为一些简单函数的和,也即它的展开对应着一个递归的二叉树,以一位二进制全加器为例,其和S的真值表和逻辑表达式如下所表1所示。
本位和S=A′B′C1+A′BC1"+AB′C1′+ABC1,构造其所对应的二叉树如图2所示。
实际上,二叉树中的一些节点是重复的,在该图2中,最后一层的0和1节点它们可以合并,对二叉树有缩减规则,其一是当两个节点传输到下一个节点的传输路径完全相同时,两个节点可以缩减为一个;当一个节点的所有传输路径都归结到同一个下一级节点时,这个节点可以省略。如图3所示。
合并0项和1项,通过缩减规则最终可得一位二进制全加器的二叉树如图4所示。将所有节点转化为NMOS的连接点,将路径有相应的NMOS管来代替,即可得到最终的CVSL电路,如图5所示,这样用二叉树转化为MOS电路的过程就完成了。
3 结 语
本文对比了CMOS电路与CVSL电路的特点,针对CVSL电路速度快功耗低的优点,在高速电路和VLSI设计中通常采用该电路,但由于CVSL电路共享的NMOS管较多,为提高利于率,对比互补的特点,提出了优化电路的二叉树算法。它比传统的真值表优化法,其直观性更强,很好地解决了CVSL电路的设计问题。