二叉树模型范文

二叉树模型范文（精选9篇）

二叉树模型 第1篇

期权最先在金融领域出现, 但它更广泛地被用于投资评价。期权定价可基于复制原理或风险中性原理, 两者比较, 根据风险中性原理计算较为简易。这里, 笔者试图根据风险中性原理基于EXCEL2007平台, 建立美式期权估价模型。

一、EXCEL2007的相关函数及工具介绍

1. 单元格绝对引用与相对引用。例:在A4单元格内输入“=sum ($A1:A$3) ”, 复制A4单元格, 并粘贴至B5单元格, B5格的公式为“=sum ($A2:B$3) ”, 前面加“$”的为绝对引用, 不随移动复制位置的改变而改变。

2. if (Logical_test, value_if_true, value_if_false) , 判断Logical_test条件是否为真, 为真则执行value_if_true, 为假则执行value_if_false。例如:A1单元格输入“50”, A2格内输入“=if (A1>60, ”及格”, ”不及格”) ”, 结果A2格内值为“不及格”。

3. sumproduct (array1, array2, array3, .) , 返回相应的数组或区域乘积的和。例如:在A1:A3区域分别输入“1, 2, 3”, 在B1:B3区域内输入“2, 3, 4”, 在B4内输入“=sumproduct (A1:A3, B1:B3) ”, B4格内的计算实质为“=A1*B1+A2*B2+A3*B3”, 结果值为“20”。

4. OR (logical1, logical2, ...) , 在其参数组中, 任一参数值为TRUE, 即返回TRUE;只有当所有参数值均为FALSE时才返回FALSE。例如:在某单元格输入“=OR (D4=“”, D4=“入库”) ”, 如果D4单元格为空值或“入库”字样, 结果为TRUE;若为其他字符或公式, 结果为FALSE。

5. EXP (number) , 计算e的n次方, 常数e等于2.718 281 828 459 0。

6. YEARFRAC (start_date, end_date) 。返回start_date和end_date之间的天数占全年天数的百分比。例:在某单元格内输入“=YEARFRAC (2007/7/1, 2007/10/1) ”, 结果显示“0.233333”, 表示2007/7/1至2007/10/1的时间长度为0.233 33年。

7. MAX (number1, number2, ) , 返回一组数中的最大值。

8. INT (number) , 将数字向下舍入到最接近的整数。例:在某格输入“=INT ( (9.456 7*100+0.5) /100) ”, 结果为9.46, 实质是将9.456 7四舍五入至小数点后两位小数。输入“=INT ( (A1*1000+0.5) /1000) ”, 实质是将A1单元格中的数四舍五入至小数点后三位小数。

9. 选项按钮。点击“控件”“插入”“表单控件”“选项按钮” (“控件”工具箱需从左上角的Office按钮中调出, 点击“Office按钮”“EXCEL选项”按钮“自定义”选项“开发工具选项卡”中的“控件”, 添入“自定义快速访问工具栏”中) 。以表1中的“期权类型”选择为例, 在工作表中按左键拖动画出其外形, 将选项圆圈旁的文字改为“看涨期权”, 再选中该选项, 右键点击, 选择“设置控件格式”命令, 在打开的窗口中, 选择“控制”标签, 并输入链接单元格为“C5”。用以上同样方法制作“看跌期权”选项, 链接单元格也为“C5”。这样选择“看涨期权”选项, C5格显示1, 选择“看跌期权”选项, C5格显示2。再在“控件”工具箱中选择“分组框”工具, 在工作表内看涨、看跌两个选项外画出一个分组方框, 并将其名字改为“期权类型”。将该“分组框”及看涨、看跌两选项按钮一并选中, 右键点击, 选中“组合”命令, 这样就形成一个三项合一的组合框。

1 0. 数值调节钮。以表1中的“期权期数”调节为例, 点击“控件”“插入”“表单控件”“数值调节钮”, 在工作表中画出其外形, 再选中该按钮, 右键点击, 选择“设置控件格式”命令, 在打开的窗口中, 选择“控制”标签, 输入当前值为“10”, 最小值为“1”, 最大值为“100”, 步长为“1”, 链接单元格为“J6”。这样J6格内期权期数会随着“数值调节钮”上下箭头的调节在1至100间按步长1增减变动。

二、美式期权二叉树模型设计方法

例:Frank公司2009年10月7日股票的收盘价为50元, 其股票日收益率的年标准差为0.856 7, 半年期的国库券收益率为4.67%。如果在2009年10月7日购入基于该股票的美式期权, 到期日为2010年6月5日, 其看涨期权与看跌期权执行价格皆为51元, 分别计算该看涨期权和看跌期权的价格。

根据以上问题, 建立美式期权二叉树定价模型表1至表3。

本模型的期权期数为1~100间的任意整数, 计算过程大致分十六步, 每一步的操作都可通过旁边解说框中的文字或公式详细了解。表1至表3内某些步骤中的公式解释如下:

第4步, 计算每期无风险收益率。无风险收益率应当用无违约风险的固定证券收益来估计, 例如参考国库券市场利率。同时应选择与期权到期时间相同的国库券市场利率;如果没有, 应选择与期权到期时间最接近的国库券市场利率。本模型中期权到期时间与半年期最近, 所以选择半年期的国库券收益率4.67%作为该期权的无风险收益率。另外需要注意的是, 本题计算每期无风险收益率, 不可用公式“年无风险收益率/ (2*期权期数) ”来计算, 因为期权模型使用的是连续复利而不是常见的年复利。连续复利假定利息是连续支付的, 利息支付的频率比每秒1次还要频繁。因此, 计算公式为:F=Pert, 其中F表示终值, P为现值, r为年无风险收益率, t表示每期时间 (以年为单位) 。根据上述公式, 每一元现值在每期时间后的终值=1*ert, 这样, 每期无风险收益率=ert-1, 也即:EXP (r*t) -1。

第5、6步, 计算每期股价上升及下降率。有关公式为:, 1-股价下降率, 其中, e为自然常数, σ为股票收益率年标准差, t为以年表示的时间长度。这样将上述公式调整后, 可得:股价上升率, 股价下降率 (注:这里将股价下降率表示为负数) 。

第7步, 计算风险中性概率。每期期望报酬率 (每期无风险收益率) =风险中性概率股价上升率+ (1-风险中性概率) 股价下降率, 公式调整后, 风险中性概率= (每期无风险收益率-股价下降率) / (股价上升率-股价下降率) 。

第15步, 计算美式期权价格。表3中, 该步的公式较复杂, 但其基本计算原理如下: (1) 在期权最后一期, 如表中第100期, 看涨期权到期收益=MAX (到期时的股票价格-期权执行价格, 0) , 看跌期权到期收益=MAX (期权执行价格-到期时的股票价格, 0) , 两个公式可合并, 看涨 (或看跌) 期权到期收益=MAX[1 (或-1) (到期时的股票价格-期权执行价格) , 0], 在表3中计算时可用公式“期权到期收益=MAX (C6 (到期时的股票价格-期权执行价格) , 0) ”。 (2) 期权计算的其他期内对其价值的计算。美式期权可在期权到期日按照执行价格行权, 也可在到期日前的任何时点上行权 (本例中假设在每期期末行权) 。是否提前行权, 取决于行权与暂不行权给投资者带来收益的大小, 哪种方式的收益高, 就采用哪种方式。因此, 计算到期日前某一期期末的期权价格时, 应同时计算行权与不行权的价值大小并取与较大数值对应的选择方式。在行权条件下, 第t期看涨 (看跌) 期权价值=1 (或-1) (t期股票市价-行权价格) ;而在不行权条件下, 第t期期权价值= (风险中性概率第t+1期期权上行价值+ (1-风险中性概率) 第t+1期期权下行价值) / (1+每期无风险收益率) 。 (3) 公式编辑中需要考虑到空格的处理。

在此, 可以用“条件格式”功能, 将表3中B227:CX327区域中选择提前行权的单元格用突出颜色显示出来。需要指出的是, 凡是提前行权的时点应采用行权条件下的计算方式而非风险中性法。

点击“开始”“条件格式”“管理规则”命令, 在打开的“条件格式规则管理器”窗口中点击“新建规则”命令, 在“选择规则类型”内选择“使用公式确定要设置格式的单元格”选项, 在下面的公式空白框中输入新建规则公式“=B227=$C$6* (B124-$F$5) ”, 再点击下面的“格式”按钮, 在打开的对话框中设置单元格填充颜色为灰色, 点击“确定”回到“条件格式规则管理器”窗口, 在公式应用的空白框中输入:“=$B$227”, 点击“确定”后完成B227格的条件格式设定。选中B227格, 点击“复制”, 再选中C227:CX327区域, 点击“粘贴”“选择性粘贴”命令中的“格式”粘贴, 这样该区域中用行权公式计算的格子就显示为灰色。从表中可看到:美式看涨期权最佳行权时机发生在股息发放的前一期 (美式看跌期权则在股息发放后行权) 。

摘要：会计准则要求期权的计量报告采用公允价值, 其公允价值的确定需要使用期权定价模型。在手工条件下进行期权估价, 计算工作量大, 往往需要借助计算机软件工具。因此本文试图根据风险中性原理, 基于EXCEL2007平台建立美式期权估价模型的方法。

关键词：期权,EXCEL,价格评估,二叉树

参考文献

[1].中国注册会计师协会.财务成本管理.北京:中国财政经济出版社, 2011

实验报告：二叉树 第2篇

一 实验目的

1、进一步掌握指针变量，动态变量的含义；

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

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

4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。

二 实验原理

树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。遍历二叉树的实质是将非线性结构转为线性结构。

三 使用仪器，材料 计算机 2 Wndows xp 3 VC6.0

四实验步骤

【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。

【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。

五实验过程原始记录 基本数据结构描述； 2 函数间的调用关系； 用类C语言描述各个子函数的算法； 附录：源程序。

六 试验结果分析

二叉树模型 第3篇

影响寿险产品定价的因素很多,如死亡率、退保率、利率等,其中,死亡率因素对寿险产品定价的影响首当其冲。对保险专业的本科生而言,熟悉生命表,理解生命表相关概念并掌握死亡率的计算是一项基本的学习任务,然而,由于这部分内容涉及到的符号标记多、公式多、应用到的数学统计学知识多,抽象性强,不少学生会感到不同程度的吃力。精算学教师在授课过程要积极探索,引入学生熟知的工具,借助简单有效的模型,把抽象的知识形象化和直观化。

二叉树模型又叫二项期权定价模型,是由考克斯(J.C.Cox)、罗斯(S.A.Ross)、鲁宾斯坦(M.Rubinstein)和夏普(Sharpe)等人提出的一种期权定价模型,主要用于计算美式期权的价值。其优点在于简化了期权定价的计算并增加了直观性,不需要太多数学知识就可以加以应用。二项式期权定价模型的基本假设是:在给定的时间间隔内,证券的价格运动有两个可能的方向:上涨或者下跌。虽然这一假设非常简单,但由于可以把一个给定的时间段细分为更小的时间单位,因而二项式期权定价模型适用于处理更为复杂的期权。二叉树模型实际上是在用大量离散的小幅度二值运动来模拟连续的资产价格运动。

在给定的任意时间间隔内,一个存活的人面临两种可能:生存或死亡,这种客观情况与二项式期权定价模型的基本假设类似,由此说明了二叉树模型在推导投保人死亡率公式过程中的可适用性。本文以二叉树模型为基本模型和工具,推导了死亡率计算公式的形成过程,以期提高教学的直观性,降低学习难度,改善学习效果。

二、本文创新

本文把金融学中的二叉树模型应用于精算学公式的教学,这种跨学科的尝试不仅达到了本学科的教学目的,培养了学生的思维能力,而且为以后的此类教学乃至整个高等教育教学提供了有益借鉴。

三、模型与推导过程

本文提供了两个二叉树模型:模型一是基于经验生命表建立的,用来推导投保人经过整数年的死亡率公式;模型二用来推导投保人经过任意时间长度的死亡率公式。这样安排是基于以下考虑:(1)从学生最熟悉、最容易理解的知识入手,由浅入深,符合学生的知识水平和认识能力;(2)重在传授思维方式。模型二建立在模型一的基础上,但并不是简单的重复,从第一个模型到第二个模型,是离散到连续的质变,是思维的升华。

(一)模型一:基于经验生命表的二叉树模型(相邻节点的时间间隔为一年)

生命表里面的死亡率是投保人存活到一定年龄时,在未来一年内死亡的概率,因此,生命表反映的是整数年的死亡率。下面我们令二叉树相邻节点的时间间隔为一年,构造一个基于经验生命表的二叉树模型,并借助该工具推导投保人经过若干整数年后的死亡率。

以一个x岁投保n年定期寿险的投保人为例,假设投保发生在年初,投保时的投保年龄为0岁,在未来一年内,投保人可能生存,也可能死亡,概率分别为px和qx,px+qx=1;投保第一年末为1岁,此时,如果投保人生存,在未来一年内,其生存概率和死亡概率分别为px+1和qx+1,px+1+qx+1=1;…;投保第n-1年末为n-1岁,此时,如果投保人生存,在未来一年内,生存和死亡的概率分别为px+n-1和qx+n-1,px+n-1+qx+n-1=1。二叉树的节点分别表示投保人存活到不同年龄时,在未来一年内的生存概率或死亡概率,构造的二叉树模型(如下页图1所示):

X岁的投保人在未来n年内,即在投保年龄(0,n]之间死亡概率nqx的分解式为:

(1)的含义:x岁的投保人在未来n年内死亡的概率等于该投保人在未来n年各年内死亡的概率之和;其在投保第t年内死亡的概率等于他在前t-1年各年内生存的条件概率(即他在前t-1年内生存的概率)与第t年死亡的条件概率之乘积。

该公式的应用:可以用来计算任意投保年龄的投保人经过一定整数年后的死亡概率与生存概率(因为nqx+npx=1)。

(二)模型二:模型一的推广(相邻节点的时间间隔为 Δt)

生命表的缺陷在于只能反映投保人经过整数年的死亡率,然而实际情况是,投保人的死亡可能发生在一年中的任意时刻,因此,上面基于生命表的二叉树模型对死亡率的计算是比较粗糙的。为了精确定价人寿保险,需要计算投保人在未来任意时刻的死亡率,这就需要构造基于更短时间间隔的二叉树模型。为达到这个目的,把1年等分为m等份,每等份时间间隔为Δt=1/m年,令二叉树相邻节点间的时间间隔为Δt,当Δt→0时,我们就可以刻划投保人在任意时刻的死亡率了。

仍以x岁的投保人为例,推导他在投保当年经历若干Δt的死亡概率。构造的二叉树模型(如图2所示):

参考上面模型的分析思路,我们可以得到x岁的投保人经过任意时间t的死亡概率tqx的计算公式:

该公式的应用:该公式突破了生命表的局限性,可以用来计算投保人自投保开始经历任意时长的死亡率。

四、结论与启示

本文用二叉树模型来刻画投保人在不同时刻的死亡和生存概率,使得抽象的概念和知识变得形象和直观,让学生一目了然,容易接受。为了循序渐进地推导死亡率的计算公式,本文提供了两个二叉树模型,其一是基于生命表的模型,相邻节点间隔为一年;在此基础上引入了相邻节点间隔为任意时长的模型,两个模型各有自己的使用范围。模型一用来解决投保人在整数年的离散型死亡率的计算;模型二用来解决投保人在任意时刻的连续型死亡率的计算。这样安排体现了由浅入深、从特殊到一般、从离散到连续的辩证思维过程,既是一种知识的传授,更是一种思维方法的传授过程。

第四次实验--二叉树遍历 第4篇

public T data;

//数据域，存储数据元素

public BinaryNode left, right;

//链域，分别指向左、右孩子结点

//构造结点，参数分别指定元素和左、右孩子结点

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ 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 || objinstanceofBinaryNodethis.data.equals(((BinaryNode)obj).data);

}

public booleanisLeaf()

//判断是否叶子结点

{ returnthis.left==null this.right==null;

} } 二、二叉树中的遍历方法的声明.BinaryTree public class BinaryTree {

public BinaryNode root;

//根结点，结点结构为二叉链表

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)

//先根次序遍历以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)

//返回先根次序遍历以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)

//中根次序遍历以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)

//后根次序遍历以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 create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ 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 p=new BinaryNode(elem);

//创建叶子结点 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 create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String

{

p = new BinaryNode(elem);

//创建叶子结点 p.left = create(prelist);

//创建p的左子树 p.right = create(prelist);

//创建p的右子树

}

} return p;

}

}

三、运行程序

.BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树

public class BinaryTree_make {

public static BinaryTree make()

//构造给定的一棵二叉树

{ BinaryTreebitree=new BinaryTree();//创建空二叉树

BinaryNodechild_f, child_d, child_b, child_c;//创建4个二叉链表域 child_d = new BinaryNode(”D“, null, new BinaryNode(”G“));child_b = new BinaryNode(”B“, child_d, null);child_f = new BinaryNode(”F“, new BinaryNode(”H“), null);child_c = new BinaryNode(”C“, new BinaryNode(”E“), child_f);bitree.root = new BinaryNode(”小唐“, child_b, child_c);//创建根结点 returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍历二叉树 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 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍历

bitree1.inOrder();//中根遍历

bitree1.postOrder();

} }

//后根遍历

四、运行结果

五、实验内容

1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历

六、附加实验内容

在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。

七、实验报告要求

1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。

二叉树模型 第5篇

2009年我国创业板市场的推出, 使得对创业板企业进行合理的估值成为投资者关心的问题。创业板企业较之主板上市公司具有:企业规模小、成长性强、业务模式新、经营风险高等特点。其中高成长性和高风险性是其主要特征。高成长性主要依托于企业内部新产品和新商业模式的开发和实现, 这些潜在的增长机会对创业板企业的价值起到决定性作用, 这也成为创业板企业最大的亮点。但是不容否认的是, 创业板企业由于行业及自身发展的原因存在很大的风险。这是因为创业板企业大部分是高科技公司, 高科技的研发大部分是分阶段进行的, 因此很容易受到宏观经济、行业发展、资本、技术更新及人才等多方面的影响, 任何一个方面的负面因素都有可能导致高科技企业处于经营困境, 甚至走向破产。而且创业板企业的高成长性主要体现为非线性成长规律, 这些特征使得运用传统的估值方法难以反映创业板企业的管理弹性和未来不确定因素影响下的真实价值, 因此本文在分析传统估值方法局限性的基础上, 尝试运用实物期权理论中的改进的二叉树模型对创业板企业进行价值评估。

二、传统企业估值方法的局限性

目前对公司估值采用的传统方法主要有重置成本法、市场法和折现现金流法 (D CF) 三种。这三种方法主要是静态的评估企业价值, 适用于传统稳定的上市企业。由于创业板企业不同于主板企业的特征, 运用上述三种方法评估出来的价值, 往往与企业的真实价值存在偏差, 具有很大的局限性。

(一) 重置成本法的局限性

重置成本法是按资产全新情况下的限价为基础, 以当前市价为标准来评估企业的价值。其思路可以表示为:V=C*r

其中V为被评估资产价值, C为重置成本, r为成新率。该方法主要是对过去和现在的评价, 没有考虑企业的未来潜在价值, 其局限性主要表现为:该方法是一种静态的评估方法, 其反映的是企业的历史和现有状况, 而无法准确反映企业未来的动态发展过程;该方法通常不考虑企业中无形价值和人力资本价值, 而这对创业板企业来说, 却是较为重要的一个影响企业价值的因素。所以, 采用重置成本法对创业板企业进行资产评估会低估其真实的价值。

(二) 市场法的局限性

市场法是以活跃、公平的市场存在 (市场是有效的) 为前提。该方法的理论依据是将被评估企业与具有相同行业和财务特征的企业进行比较, 来对企业的市场价值进行评估的方法。其思路为:V=P*α

其中V为待估企业的价值, P为估价指标, 代表企业的实际经济意义, α为比率系数, 比率系数的计算, 要注意其在样本企业中的稳定性。运用该方法成功与否关键在于估价指标和比率系数的正确选择。实际上, 这存在很多问题:一方面创业板企业多为具有高成长性的创新型公司, 由于高新技术的差异很大, 盈利增长点不同, 很难在市场上找到与之相类似的可比公司, 所以估价指标很难确定;另一方面, 创业板企业的处在发展阶段, 其比率系数相对来说都不够稳定, 这使得评估结果不可靠。这些问题的存在使得运用市场法很难反映创业板企业的真实价值。

(三) 折现现金流法的局限性

折现现金流法是通过预测公司未来的盈利能力, 并按适当的折现率进行折现, 借以确定企业价值的方法。该方法有两个基本假设, 即投资决策的不可延迟性和投资项目成本可以收回, 这往往与现实不符。对于创业板企业来说, D CF法存在以下缺点:第一, D CF法没有考虑企业管理层的决策选择权力即管理柔性, 此方法假定投资决策只能采取刚性的策略, 而实际上管理者可以根据企业外部环境的变化, 采取相应的措施;第二, D CF法认为企业的现金流是可预计的, 用资本资产定价模型计算出风险报酬率或用无风险利率作为折现率, 以计算未来现金流量的现值, 而且随着不确定性增加而调整折现率, 主观性强。第三, 创业板企业存在潜在增长机会的价值, 其未来的现金流表现出非线性的特征, 而D CF方法是静态和线性分析方法, 不能对此作出分析。

三、创业板企业的改进二叉树价值评估模型

在实物期权研究方面, Trigeorgis认为企业投资机会本质上等同于增长期权, 因此企业的市场价值包括两个部分:一是公司所有有形资产的现值;二是公司所拥有增长期权的价值之和。这样企业的价值就可以表述为:

其中V是企业的真实价值, V1是表示现有资产现金流量的贴现值, V2是企业的增长期权的价值。实物期权数量化了企业未来发展中固有的管理弹性价值, 根据Judy Lewent (M erck的财务总监) 的说法, 所有的商业决策都是实物期权。二叉树模型利用动态规划技术透明地处理各种实物期权价值, 中间环节的价值和决策是可见的, 这使管理者对实物期权的价值来源有更直观的认识。

(一) 改进的二叉树定价方法

考虑无红利支付的股票, 股票价格为S。股票价格行为模型中指出, 股票价格行为服从几何布朗运动, 其离散形式为:

其中参数μ为单位时间内股票价格的预期收益率, σ为股票价格的波动率, ε为标准正太分布的随机抽样值。该方程表明△S/S服从均值为μ△t, 标准差为σ△t的正态分布。设初始股票价格S经过时间△t, 股价或者从S以概率p上升到一个新的水平Su, 或者以概率1-p下降到新的水平Sd (u>1, d<1) , 如图1所示。

股价增长的比率为u-1, 股价减少的比率Á为1-d。根据风险中性估值原理, △t末股票价格的期望值为:

其中r为无风险利率, 由此,

即:

由 (2) 式可知股票价格的比率变化在△t时间内的方差为σ2△t, 又依据变量G的方差定义为E (G 2) -[E (G) ]2, 由 (5) 式可得:

公式 (5) 、 (7) 给出了p、u、d的两个条件。Cox、R oss、R ubinstein用的第三个条件是:u=1/d, 将其带入 (8) 、 (9) 运用关于的一阶泰勒展开式, 忽略比△t高阶的小项近似求解得到:p+ (c-d) / (u-d) , u=e, d=e , c=er△t。但是Cox等人给出的第三个条件u=1/d没有理论依据, 而且存在缺点:当σ<| (r-q) |, 其中q为红利支付率, 也就是较小的σ将导致负的概率出现。

下面重新构造一种方法得出参数p、u、d。

从公式 (8) 解出

由此可知只要得出u, p和d也就随之确定。在风险中性假定下, 由公式 (3) 可知, 股票价格S经过△t时间后的期望值为Ser△t。由前文假定可知u表示股价S在△t后的上升比率, 假定u为随机变量, 则u的期望值E (u) =er△t, 由公式 (2) 可知u的方差近似为σ2 (u) =σ2△t。张铁 (2000) 研究u的标准差σ (u) 为u取值er△t在加权L2范数下的误差, 由此根据误差校正的原则, u的取值可以为u=er△t±σ (u) 。因为概率p应满足:0燮p燮1, 由 (9) 式可知u叟er△t, 所以u=er△t±σ (u) , 即u=er△t+σ , 代入 (9) 式解出:

p=0.5, u=er△t+σ姨△t, d=er△t-σ姨△t (10)

由此可以得出该公式使得概率p不会产生负值, 更符合现实的需要。

(二) 企业实物期权价值分析

假设一个企业由于市场前景看好, 计划在未来的第t年进行增资扩张, 为计算方便设时间变量△t为1年, 企业在第t年年初追加投资It, 并且这样做使得企业在第t年的收益在原有基础上增加k%。企业当前收益为V, 以后每年企业收益依据市场环境从初始值V以概率p或1-p随机移动到V u (收益处于增长状态) 或者是V d (收益处于下降状态) , 且u>1, d<1。设定当前时间为t=1, 则在第二年, 收益有两种可能即V u和V d, 在三年收益有三种可能即V u2、V ud、V d2, 依据式 (10) 同理依此类推可得第i年的收益值:

Vij=V uj-1di-j, 其中1燮i燮t, 1燮j燮i (11)

这样就得到了图1的扩展形式如图2所示。

设ft, j为企业第i年第j个结点的预期收益价值, 其中i, j取值同式 (11) 。第t年即企业追加投资的时期, 结点 (t, j) 的预期收益价值为:

其中Vt, j为第t年不追加投资时j结点的项目收益。

企业的预期收益价值计算是从收益树图的末端即追加投资期向后递推进行的。其递推过程为, 第i阶段从结点 (i, j) 向 (i+1) 阶段的结点 (i+1, j+1) 移动的概率为p, 而向 (i+1, j) 结点移动的概率是 (1-p) 。

如果在风险中性假设下, 考虑企业追加投资的扩张期权价值, 则式 (12) 应改为:

项目在i阶段结点 (i, j) 的预期收益价值为:

其中1it-1, 1ji, r为无风险利率。依次递推fi+1, jf2, 2f1, 1即可得到企业的整体价值即:f=f1, 1。

如果按照传统的D CF方法计算企业价值, 则项目在i阶段结点 (i, j) 的预期收益价值为:

其中1it-1, 1ji, R为风险调整贴现利率。同理可得企业的整体价值即f'=f'1, t。

我们记含有扩张期权的价值为F, 依据式 (14) 、 (15) 可得到企业在两种方法下的价值。根据 (1) 式可得企业追加投资的期权价值为:

其中TF为项目扩张期权的价值。

由式 (12) 、 (13) 、 (14) 和 (16) 结合前文中得出的p、u、d的计算公式 (10) 即可求得创业板企业含有扩张期权的真实价值。

四、应用实例分析

(一) 实例描述

某软件企业A刚刚在创业板上市, 当前企业的收益为900万, 以后每年若市场前景看好则收益以概率p增加, 若行情不好则收益以 (1-p) 相应减少, 收益波动率预计为69%, 行业的风险调整贴现率为20%, 市场无风险利率 (取2010年3月期国债利率) 近似为3%。现在企业管理层预计未来市场行情看好, 计划在第5年追加投资700万元, 这样使得企业在第5年的收益增加50%。各相关变量数据如表1所示。

(二) 价值分析

已知, 单位时间△t=1, 无风险利率为3%, 所以企业收益单位时间上涨幅度为;企业收益单位时间下降幅度为 ;上涨概率p=0.5;下降概率1-p=0.5。

由式 (11) 结合企业A的数据可得各年收益如图3所示。

由式 (13) 、 (14) 可得到企业包含扩张期权的价值为4594.55万元, 如图4所示。

根据式 (12) 、 (15) 可得到传统D CF方法得到的企业价值为3302.84万元, 如图5所示。

根据公式 (16) 可得企业包含的扩张期权的期权价值为F=f-f’=4594.55-3302.84=1291.71万元。由此看出如果不考虑追加投资的扩张期权而按照D CF方法计算, 那么将会低估企业的真实价值。

五、结论

创业板企业未来的发展存在各种风险, 运用传统的企业估值方法将会低估企业未来不确定性因素所蕴含的实物期权价值。本文借鉴金融期权中的二叉树定价模型, 将改进的二叉树模型运用到创业板企业估值当中, 根据本文分析, 得出以下结论:第一, 同传统实物期权二叉树模型相比, 避免了上下波动概率p为负的情况, 推导出的参数结果符合参数真实关系, 同时保证了计算精度。第二, 二叉树模型评估方法能够直观、清楚地反映未来不确定性的各种结果, 管理者可以将其作为在企业未来发展中进行价值判断的一种可参考的方法。第三, 通过算例分析得出, 改进的二叉树模型比D CF方法更能全面考虑企业管理弹性和不确定性对企业价值的影响, 得出的企业价值更贴近真实价值。

参考文献

[1]中国证券业协会:《证券投资分析》, 中国财政经济出版社2009年版。

[2]Dixit A K, R S Pindyck.Investment under uncertainty[M].Prineeton, NJ:Princeton University Press, 1994.

[3]房四海, 王成.创业企业定价的复合实物期权模型[J].数量经济技术经济研究, 2003 (9) :63.

二叉树模型 第6篇

随着国际金融市场的不断发展和完善, 大量金融衍生产品应运而生, 其中就包括奇异期权, 即由标准期权经过组合、变化衍生出来的各种新产品。障碍期权是其中一种, 因其比普通标准欧式期权价格便宜, 倍受市场青睐, 被广泛用于资产风险管理。金融产品作为资本市场投资工具, 具有较高的风险收益特性, 如何正确评估产品的内在价值就显得尤为重要。而选择合理的定价模型则是正确评估产品价值的重中之重。本文主要研究了上升敲入欧式看涨障碍期权 (对于看跌期权, 可以通过期权评价公式求得) 的二叉树和蒙特卡洛模拟定价模型, 以比较二者之间的差异。

二、障碍期权的涵义及定价模型

2.1向上敲入障碍期权的涵义

障碍期权是一种路径依赖期权, 其收益依赖于标的资产的路径变化, 当期权在有效期内的资产价格触及到某一水平, 即通常所说的障碍时, 期权合约生效或失效。向上敲入障碍期权是指障碍水平高于标的资产初始价格, 且资产价格在规定时间内达到障碍水平, 期权才得以生效的金融衍生品。

2.2二叉树定价模型

假设市场是完全市场, 不存在套利行为和交易成本, 所有资产可以无限细分, 没有卖空限制, 且股票不支付红利。设股票初始时刻价格为S0, 期权初始价值为f, 无风险收益率为常数r, 期权执行价格为K, 障碍值为SB (SB>S0) , 期权的有效区间为[0, T], 将其细分为N个等长的区间[tn, tn+1] (0≤n≤N-1) , 在每个区间上股票价格或者以概率p上升为原来的u倍, 或者以概率1-p下降为原来的1/u (d=1/u) , 相应的, 期权价值变为fu或fd。

根据风险中性原理, 可以求得模型的参数p, u, d的表达式:

其中, σ是股票价格的实际波动率, △t=T/N。

由向上敲入欧式看涨障碍期权的定义知, 时刻t的期权价值为

其中, Iω (S) 是集合ω的特征函数, 可简写为Iω, 即

在风险中性世界里, 知在T-△t时刻的期权价值可由t时刻期权价值的期望值在△t时间内用无风险收益率r贴现得到, 即

同理, T-2△t时刻的期权价值可由T-△t时刻期权价值的期望值在△t时间内用无风险收益率r贴现得到, 以此类推, 可以得到在初始时刻的期权价值。

但是存在一个问题, 即设定的障碍价格水平不一定正好落在二叉树结点上, 即障碍价格 (真实障碍) 水平处于两个结点水平之间。虽然这种情况可以通过将时间步长缩短, 细化时间间隔的方法减少误差, 但是会大大增加计算复杂度。本文采用线性插值的方法进行处理。首先选定最为临近障碍价格水平的两个结点水平, 分别作为内障碍水平和外障碍水平, 然后利用线性插值公式求得 (图1) 。

2.3蒙特卡洛模拟定价模型

蒙特卡洛模拟方法的思路很简单, 首先是随机生成风险中性条件下资产价格的多条不同路径, 然后计算所有路径期权价值的期望值, 最后用无风险利率贴现即可得到所求期权价格。

障碍期权是路径依赖期权, 其收益是到期日前所有股票价格的函数, 即

, 假设股票价格遵循几何布朗运动, 由伊藤引理可得股票价格的随机路径:

其中, ε是由标准正态分布产生的随机数, 可由Box-Muller法或大数法则产生。因此, 只要随机生成一个ε, 就可以得到股票价格的一条路径。

设第i条路径的障碍期权收益为fi, 则

计算k条路径期权收益的均值作为期权价值的期望值, 即

在风险中性条件下, 用无风险利率r贴现得到障碍期权的估计价格, 即

三、实例与结论

3.1实例

选取的数据来源于姜礼尚所编的《期权定价的数学模型和方法 (第二版) 》, 设一张6个月的看涨期权股票, 现股价为145元, 无风险利率r=6%, 波动率σ=0.295。期权的执行价格为145元, 障碍价格分别为160元和190元。

通过matlab编程实现了上述实例中的向上敲入障碍期权的二叉树和蒙特卡罗模拟定价过程。表1给出了两种模型计算的结果和实际值。

3.2结论

表1中障碍价格为0时的期权价格, 表示标准期权的价格为12.87元。从中可以看出, 无论采用二叉树定价法还是蒙特卡洛模拟定价法, 都验证了障碍期权的价值要比普通期权的价值要低这一事实。

随着模拟路径的增加, 蒙特卡洛模拟方法得到的障碍期权价格与实际越接近, 这是因为样本数据增加后, 会减少估计值与实际值的误差水平, 使估计值更加接近实际值。

蒙特卡罗模拟比二叉树方法得出的结果更接近于实际价格, 更具有良好的实用性。其主要原因: (1) 二叉树定价模型中, 由于时间步长不够长, 由内外障碍价格计算出来的期权价格不能很好的精确到真实障碍水平下的障碍价格; (2) 随着障碍的增加, 障碍期权的价格偏离实际价格越大, 其主要原因是随着障碍价格的增加, 内外障碍价格差增大, 导致偏离真实障碍越大; (3) 二叉树定价时, 仅仅将到期时股票价格低于障碍水平时的期权价格赋予零值, 是存在缺陷的。因为二叉树定价法的原理是从后往前计算, 这与股票价格从前向后变动的方向是相反, 股票价格可能在到期之前已经触及到障碍价格, 而在到期时又下降到障碍价格以下, 在此情况下, 该条路径仍然是有效的, 其值并不为零。

摘要：基于对障碍期权的涵义理解以及对二叉树和蒙特卡洛模拟定价模型步骤的详细阐述, 采用两种方法分别对上升敲入看涨障碍期权进行了价格评估, 并通过实例分析两种方法的差异性。

关键词：障碍期权,二叉树定价,蒙特卡洛模拟定价

参考文献

[1]郑振龙, 陈蓉.金融工程 (第二版) [M].北京:高等教育出版社, 2008.141-233.

[2]姜礼尚.期权定价的数学模型和方法 (第二版) [M].北京:高等教育出版社, 2003.255-284.

[3]徐腾飞, 曹小龙, 胡云姣.离散障碍期权定价的蒙特卡罗模拟[J].北京化工大学学报 (自然科学版) , 2013, (3) :123-127.

[4]邢晓芳, 周圣武, 石广平等.基于跳扩散模型的欧式上升敲入期权定价研究[J].云南大学学报 (自然科学版) , 2009, (s2) :354-357.

二叉树模型 第7篇

二叉树是数据结构非常重要的一种非线性结构，是树型结构的一种特殊形式，在计算机处理领域有着广泛的应用。况且对二叉数的大部分操作，都是在遍历过程中实现的，在许多教材中，都指出了如何对二叉数进行遍历，但并没有对如何通过二叉数的遍历序列还原二叉数作更详尽的介绍，本文就针对如何由二叉数的遍历序列还原二叉数的算法方面进行分析研究，并在turboC中实现此算法。

一、二叉数的定义

是有限元素的集合，是另一种树型结构，它可以为空，也可以由树根结点和至多两棵子树组成，每棵子树内部又是一棵二叉数。在二叉树中，每个结点的左子数的根结点被称之为左孩子，右子树的根结点被称之为右孩子。

二、二叉树的遍历

从二叉数的定义或组成可以知道，标准二叉数包括树根和左右子数三个部分。而且二叉树是递归定义的，换句话说，二叉树的每棵子树中，也是由这三个部分组成的。所以，寻找对二叉树进行遍历的规律，实际上就是研究对这三个部分访问顺序的规律。按照数学排列组合的方法，这三个部分有六种不同的访问顺序：DLR、DRL、LDR、RDL、LRD、RLD。其中D代表树根，R代表右子树，L代表左子树。但六种不同的访问顺序又可以分为从左到右和从右到左的两组，每组有三种不同的访问顺序。两组不同的访问顺序对称的，因此，只考虑其中一组即可。

这里以从左到右的一组为例，有DLR、LDR、LRD三种访问顺序，我们以访问根结点的顺序，对它们分别命名为先根遍历、中根遍历、后根遍历。

1、先根遍历（前序遍历）

若二叉树为空，则不访问任何结点。若二叉树不为空，则其访问顺序为：

(1)访问根结点

(2)先根遍历左子树

(3)先根遍历右子树

2、中根遍历（中序遍历）

若二叉树为空，则不访问任何结点，若二叉树不为空，则其访问顺序为：

(1)中根遍历左子树

(2)访问根结点

(3)中根遍历右子树

3、后根遍历 (后序遍历)

(1) 后跟遍历左子树

(2)后跟遍历右子树

(3)访问根结点

由前序和中序遍历或者由中序和后序遍历序列，可以唯一确定一颗二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。

三、还原二叉数的步骤与算法

1、由先序和中序遍历还原二叉树的步骤为：

画出先序遍历序列的第一个结点，即二叉树的根结点

在中序遍历序列中找到根结点，以此为界分别数出二叉树根结点的左、右子树的结点个数

依照左、右子树的结点个数由先序遍历序列的第二个结点数起，分别找出左、右子树的先序遍历序列

由左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出

2、由先序和中序遍历还原二叉树的算法为：

3、由后序和中序遍历还原二叉树的步骤为：

画出后序遍历序列的最后一个结点即为二叉树的根结点

中序遍历序列中找到根结点，以此为界数出二叉树根结点的左子树结点个数

依照左子树的结点个数由后序遍历序列的第一个结点数起，则可分别找出左、右子树的后序遍历序列

从左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出。

4、由后序和中序遍历还原二叉树的算法为：

结束语

在许多的教材中都只对二叉树的三种遍历给出了算法描述，却没有提到如何由遍历序列来确定二叉树，但掌握各个序列间的相互联系，学会利用二叉树的各种遍历序列特性去还原二叉树在实际应用中恰恰是不容忽视的问题，本文对如何还原二叉树的问题进行了说明，并用Turbo C语言编写并验证了相应的算法代码。

摘要：二叉树是一种常用的数据结构, 它的实际应用十分广泛。二叉树的遍历有三种方式, 分别为先序, 中序和后序, 本文针对如何由二叉树的遍历序列还原二叉树的问题, 提出了由先序遍历和中序遍历或后序遍历和中序遍历唯一确定一棵二叉树的算法, 并对这两种算法进行了分析描述, 并在turboC中得以实现。

关键词：先序遍历,中序遍历,后序遍历,还原,二叉树

参考文献

[1]严蔚敏、吴伟民:《数据结构》, 清华大学出版社, 2007年。

二叉树顺序存储结构探讨 第8篇

用链式存储结构表示非线性结构是一种直观的想法, 二叉链表和三叉链表是二叉树的两种链式存储结构[1,2,3], 它们均适用于所有的二叉树。将非线性结构进行某种线性抽象能够 顺序存储到线性的存储器中是一种具有挑战性的思考。通常提出的二叉树的顺序结构是基于二叉树的性质5来实现的[1,2,3], 性质5中总结的规律就是对 (某类) 二叉树的一种线性抽象。但是这种顺序存储结构天生具有缺陷, 它只适用于完全二叉树或结点密集型二叉树或高度不大的二叉树。主要工作是, 提出一种适用于所有二叉树的顺序存储结构。

2 相关知识

定义1二叉树是由n (n≥0) 个结点构成的有限集合:

(1) 它可以为空 (空二叉树);

(2) 若不为空 , 则它是由一个根结点和称为根的左子树和根的右子树两个互不相交的结点集构成;

(3) 左、右子树本身又是二叉树。

定义2满二叉树是:

(1) 高度为h且具有2h个结点的二叉树。

(2) 每一层都充满的二叉树 (即每层的结点数均达到最大值的二叉树)。

(3) 没有度数为1的结点 , 且叶子结点均分布在最大层的二叉树。

上述3个定义是等价的。

定义3完全二叉树是满足下述两个约束条件的二叉树:

(1) 除去最大层是一棵满二叉树;

(2) 最大层上的结点向左充满。

所谓向左充满是指, 层中的结点是从左向右依次存放的。因此, 具有n个结点的完全二叉树也可以理解为, 按照层次结构自上而下从左向右依次放置n个结点所得到的二叉树。例如, 图1是一棵按层次编号后的完全二叉树。

定义4 (二叉树性质5)[3]对具有n个结点的完全二叉树进行按层次编号 (此处编号从1开始), 对于编号为i的结点:

(1) 可计算i结点的双亲编号: 若i=1 (为根结点), 则无双亲; 否则其双亲编号为。

(2) 可计算i结点的左孩子编号 : 若2i>n, 则无左孩子 ; 否则其左孩子编号为2i。

(3) 可计算i结点的右孩子编号 : 若2i+1>n, 则无右孩子; 否则其右孩子编号为2i+1。

二叉树的性质5说明完全二叉树中结点之间的关系可以通过对结点编号的简单算术运算得到, 这意味着可以用线性结构表示这种非线性结构。完全三叉树和完全m叉树也有类似的性质。文献 [4] 给出了一个针对完全k (k≥2) 叉树的关于结点编号表示结点之间关系的一般性结论。目前大部分教材给出的二叉树的顺序存储结构都是利用二叉树的性质5来实现的。

3 常用的二叉树的顺序存储结构

3.1 结构描述

常用的二叉树的顺序存储结构是利用性质5来实现的。假设现在需要顺序存储一棵完全二叉树, 一般的处理步骤是: 首先从上至下、从左向右依次对完全二叉树中的结点进行编号 (即按层次编号), 编号从1开始; 然后用一个一维数组来存放所有结点的值 (一维数组的类型即为结点值的类型), 结点的值在一维数组中的存放位置由它们的编号来决定。类型定义如下:

#define MAX 100

typedef struct

{

DataType nodes [MAX] ; //结点信息存放在以其编号为下 //标的位置上

int n; //结点数

} SQ_BTree;

这样处理的巧妙之处是, 将蕴含分支信息 (包括方向信息, 即孩子的左右之分) 的结点编号 (由二叉树的性质5可知) 隐藏在了下标中, 从而不需要另辟空间存储分支信息; 不足之处是, 适用面窄。

为了让一般的二叉树也能采用这种顺序存储结构进行存储, 需要进行如下的处理过程: 通过在二叉树中添加外部结点 (二叉树原有的结点称为内部结构) 将其补充为一棵完全二叉树, 这个完全二叉树由内部结点和外部结点构成, 且最后一个叶子一定是原二叉树最大层上最右边的叶子; 然后对其进行按层次编号, 用一个一维数组来存放所有结点的值, 结点的值存放在一维数组中以它们编号为下标的位置上, 内部结点存储它的值, 外部结点的值统一用一个特殊的符号或值表示。

上述处理过程虽然使得这种顺序结构可以应用于一般的二叉树, 但是也带来另一个问题存储利用率不高。

定义5存储利用率是指, 实际所需存储空间大小与实际占用存储空间大小的比值。

用符号γ表示存储利用率。这个概念类似于教室利用率, 教室利用率是指就座的学生人数与教室座位总数的比值。为了更加明确常用的二叉树的顺序存储结构的不足, 下面对这种顺序存储结构作存储效率分析。

3.2 存储效率分析

为了便于分析, 引入一个分析指标二叉树的结点缺失率η。

定义6 (二叉树的结点缺失率)假设一棵具有n个 (内部) 结点的二叉树, 通过添加m个外部结点补充为一棵最小的完全二叉树, 这里所谓最小的完全二叉树是指这课完全二叉树的最后一个叶子一定是原二叉树最下最右的叶子。该二叉树的结点缺失率为: η= m/(n+m)。

考察图2 (a) 所示二叉树T, 补充得到的最小完全二叉树T' 如图2 (b) 所示, 对应的存储结构示意图如图3所示。

二叉树T的结点缺失率为: η= 4 / (6 + 4) = 40%; 假设结点值占l个字节, 则二叉树T的存储利用率为 (只考虑一维数组成员): y= 6 * l /(6 + 4 ) * l = 60%。

显然, 结点缺失率越大, 存储利用率就越低, 所以对相当大的一部分二叉树来说, 这种顺序存储结构不是很理想。为此, 提出了一种新的二叉树的顺序存储结构类双亲数组表示法。

4 类双亲数组表示法

4.1 结构描述

顺序存储结构借鉴了树的双亲数组表示法。首先回顾一下树的双亲数组表示法。

因为一条分支信息描述了相邻两个结点之间的孩子和双亲关系, 故如果能存储所有结点的信息和所有的双亲关系, 那么就在内存中表示了树。根据这个思路得到树的一种存储结构双亲数组表示法。在双亲数组表示法中, 每个结点对应的存储映像如图4所示。

其中: data域用来存储结点的信息; parent域用来存储结点的双亲编号。一棵具有n个结点的树, 对应n个图4所示的存储映像, 如何来组织这些存储映像呢? 双亲数组表示法用一组地址连续的存储单元 (即一个一维数组) 按照结点的编号依次存储这n个存储映像, 此时每个存储映像中的parent域存放的是该结点双亲在一维数组中的下标 (即双亲结点的编号)。

类型定义如下:

显然, 树的双亲数组表示法记录了树的所有结点信息和分支信息, 但没有记录分支的次序信息, 因此它适用于对无序树的存储。同样地, 如果直接套用树的双亲数组表示法存储二叉树, 那么只能知道二叉树由哪些结点组成、哪些结点之间具有父子关系, 至于在这些父子关系中的孩子是左孩子还是右孩子将无从判断, 故必须对树的双亲数组表示法进行适当改造以便能够用来存储二叉树 (改造得到的存储结构称为类双亲数组表示法)。

具体做法是: 在记录每个结点的信息和双亲编号的同时, 还记录一个标志, 此标志将指示结点是其双亲的左孩子还是右孩子。在类双亲数组表示法中, 每个结点对应的存储映像如图5所示。

其中: data域用来存储结点的信息; parent域用来存储结点的双亲编号; tag于用来存放标识结点是其双亲的左孩子还是右孩子的标签。一棵具有n个结点的二叉树, 对其进行按层次编号 (编号可以从0开始也可以从1开始; 若从0开始, 则用-1表示双亲不存在; 若从1开始, 则可用0表示双亲不存在), 它有n个图5所示的存储映像, 用一组地址连续的存储单元 (即一个一维数组) 按照结点的编号依次存储这n个存储映像。此时每个存储映像中的parent域存放的就是该结点双亲在一维数组中的下标 (即双亲结点的编号)。

类型定义如下:

图2 (a) 所示的二叉树按层次编号后如图6 (a) 所示, 它的类双亲数组表示法存储结构如图6 (b) 所示。

4.2 存储效率分析

假设结点值占l个字节, 一个整型值占2个字节, 则二叉树T的存储利用率为 (只考虑一维数组成员):

显然, 类双亲数组表示法的存储利用率的大小取决于结点值的类型, 存储利用率随结点值占据的字节数的变化曲线。

当l≥5时, 类双亲数组表示法的存储利用率y> 60%。因此对于实例T而言, 当它的每个结点值占5个及以上字节时, 采用类双亲数组表示法的存储利用率高于基于性质5的顺序存储结构的存储利用率; 当它的每个结点值占4个及以下字节时, 采用类双亲数组表示法的存储利用率低于基于性质5的顺序存储结构的存储利用率。

5 两种顺序存储结构存储效率对比

类双亲数组法的存储利用率受每个结点值所占字节数的影响, 存储利用率随着结点值所占字节数的增大呈现出非线性增长的趋势。同时可以发现, 类双亲数组法的存储利用率不受二叉树的具体树形的影响, 即类双亲数组法的存储利用率对结点缺少率是不敏感的。

通过第3节的分析可知, 利用性质5的二叉树的顺序存储结构的存储利用率不受每个结点值所占字节数的影响 (因为在计算存储利用率时, 结点值所占字节数会作为公因式被去掉)。同时发现, 它会随着结点缺失率的增加呈现线性减少的趋势。

在缺失率大于75%时, 即使结点值只占一个字节, 类双亲数组表示法的存储利用率也优于基于性质5的顺序存储结构的存储利用率。一棵深度为4的单右支二叉树的缺失率是11 / 15 = 73.3%, 一棵深度为5的单右支二叉树的缺失率是19 / 24 = 79.1%。由此可见, 缺失率在75%以上的二叉树在二叉树的集合中占据相当大的比例。依次类推, 当结点值占两个字节时, 只要二叉树的缺失率大于60%, 类双亲数组表示法的存储利用率就占优势; 当结点值占3个字节时, 只要二叉树的缺失率大于50%, 类双亲数组表示法的存储利用率就占优势等。

通过上面的分析可以得出结论, 对二叉树进行顺序存储时, 大部分情况下类双亲数组表示法的存储利用率要高于基于性质5的传统的顺序存储结构的存储利用率。

6 结语

针对二叉树的基于性质5的顺序存储结构适用面窄的问题, 提出一种二叉树的顺序存储结构类双亲数组表示法。通过对两种存储结构的存储利用率的比较分析可知, 类双亲数组表示法在大部分情况下的表现优于基于性质5的顺序存储结构。

摘要：为了得到一种适合存储所有二叉树的高效顺序存储结构,基于树的双亲数组表示法的思想,提出一种二叉树的顺序存储结构,对比分析表明,它的适用面更广。

用二叉树解决配送线路问题 第9篇

随着人们对物流重要性认识的不断深入,“第三利润源泉”的理念已经被越来越多的人们所认同。如何降低物流成本,提高物流效率和物流服务水平,是倍受企业关注的一个问题。而配送是一种先进的物流技术,在物流活动中具有十分重要的地位,是实现降低物流成本,获得良好经济效益的主要途径。因此,人们对物流配送技术提出了更高的要求,要求在考虑各种因素的情况下更加合理地选择配送线路和配载货物的方法,以实现物流供货系统的合理化[1,2]。本文应用二叉树的知识,对货物配载和配送路线的选择进行了研究,并提出了一种配送路线距离最短的算法,来实现对物流供货系统的优化。

1 货物配送路线的选择问题

配送中心是介于供货方和需求方之间的一个特殊层,它有两个不同的角色,一是存储,二是转运。当供货方与客户距离较远或运费较贵时,配送中心的存在可以降低物流的成本,因为它们的存在可以批量进、发货物,集中储运,从而降低物流系统成本,提高系统的效率[3],其模式如图1。

货物配送的一个基本问题是在已知客户地点、需求量的情况下解决车辆的行驶路线的问题,即确定一个从配送中心到客户端的最优路线,使总的配送距离最小。在实际配送中,经常会遇到车辆受承载能力、容积的限制,一辆车不能满足所配送区域用户的需求,此外客户服务时间窗口、服务优先等级、送货与取货混合等,均使配送运输问题变得复杂。解决运输复杂问题常用的方法就是VRP法。

VRP是最早由Dantzig于1959年提出,是运筹学中的热点问题。VRP是对一系列发货点和收货点,调用一定的车辆,组织适当的行车路线,使车辆有序地访问它们,在满足特定的约束条件下,力争实现一定的目标(如车辆空驶里程最短,运输总费用最低等)。典型的VRP可描述为[4]:

(1)多个客户同时需要运输服务,且一辆车不能同时满足这些客户的需求。

(2)每个客户只能被一辆车访问一次。

(3)所有车辆从仓库出发,并最终回到仓库。

(4)所有车辆必须满足能力约束。

(5)车辆在路线上可以取、送货。

2 基于二叉树的配送路线选择方法

2.1 问题定义

本文研究的路线选择问题定义为:(1)所有车辆从物流配送中心出发,并最终回到配送中心。(2)每个客户只能被一辆车访问,一辆车可以为多个需求点配送。(3)车辆的额定容量一定,配送车辆的载运量不能超过其额定的容量。(4)货物的装载只考虑其重量,不考虑其体积。(5)有足够多的可供支配的车辆。(6)各条路线的交通情况相同。

车辆配送路线问题就是研究在满足配送要求的前提下,使车辆总的行驶路线最短。本文中研究的车辆总的行驶路线最短的问题是在满足车辆额定容量的前提下实现的。

2.2 相关知识

本文下面提出的基于二叉树的配送路线选择算法中用到的一些基本理论如下:

(1)二叉树及其遍历。二叉树(binary tree)是一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

满二叉树:一棵深度为k,且有2的2k 2次方-1个结点的二叉树。特点:每一层上的结点数都是最大结点数。

完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次l,则其左分支下子孙的最大层次必为l或l+1。

遍历二叉树(traversing binary tree)的问题,即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。其中常见的有三种情况:分别称之为先(根)序遍历,中(根)序遍历和后(根)序遍历。前序遍历运算:即先访问根结点,再前序遍历左子树,最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。

(2)节约算法[5]。如图2所示,假设从配送中心向需求点i和j配送货物,在由O,i,j组成的三角形中,由三角形的任意两边之和大于第三边,配送方案b比配送方案a能够节约一定的里程。其节约的里程为:

式中,Sij表示节约的里程;COi表示配送中心O到客户i的距离;COj表示配送中心O到客户j的距离;Cij表示客户i到客户j的距离。

2.3 基于二叉树的配送路线选择方法

(1)建立一棵满二叉树。假设有n个需求点,依次对这n个需求点随机编号为1,2,…,n-1,n。并添加适当的结点(称为空白结点),这些结点的编号都为-1,其需求量为零。使n个需求点和添加的结点作为叶子结点,建立一棵满二叉树。

(2)对该满二叉树进行后序遍历,使其非叶子结点的需求量为其左子树需求量和其右子树需求量的和。这样就可以得到该满二叉树的所有结点的需求量。

(3)从根结点开始,先序遍历该满二叉树。若某结点的需求量小于车辆的额定载重量且其父结点的需求量大于车辆的额定载重量,调用步骤(4)。

(4)按先序遍历顺序遍历以该结点为根结点的子二叉树。记录下非空白叶子结点的遍历顺序,(若遇到编号为-1的叶子结点则跳过),并计算按此顺序车辆行驶的距离,其计算公式如下:

式中suml为这辆车行驶的总距离,Si为配送中心到需求点i的距离,Dij为需求点i到需求点j的距离,其它的符号代表的意义以此类推。

(5)则配送线路的总距离为各个车辆的配送距离的和即:

其中y为需要的配送车辆的数量。将这个值与已经求出的最短的配送路线的总距离(初始时该距离设置为一个比较大的数)进行比较,若该值小于已经求出的最短距离,则用该值代替已经求出的最短距离,并记录下各个车辆的配送路线。

(6)调整满二叉树叶子结点的排列顺序,重复上述(1)、(2)、(3)(4)、(5),直至该满二叉树所有叶子结点做完一个全排列时结束(如图3)。

2.4 对算法的一些说明

该算法主要是利用二叉树的遍历,在满足车辆额定载重量的情况下,求出配送车辆到需求点的路线及其行程长度。然后通过对需求点的重新排列求出在其它的配送情况下的行程长度,通过比较可得出配送路线的最小长度,即我们所求的最优配送路线。

算法中需求点和添加的空白结点依次间隔做为二叉树的叶子结点是考虑到在配送过程中车辆配送的需求点的个数为奇数个,这种情况下最极端的情况就是每辆车只能配送一个需求点,也就是我们建这种模型时的情况。现实中可以根据各个需求点的需求量适当的减少空白结点的个数,但是为了计算的方便,最好还是添加叶子结点使总的叶子结点满足建立满二叉树的要求。公式(2)体现了节约算法的思想,它要求一辆车尽可能的配送较多的需求点,这样可以节省总的行程。算法的最后一步交换结点,实际上是对叶子结点做一个全排列,这样可以考虑到所有可能的情况,但是有许多情况是不必考虑的,如两个空白结点的交换就没有什么意义,但是为了计算的方便我们还是将其所有的叶子结点做全排列。

2.5 算法的程序执行流程图(如图4)

3 实例应用

实例描述[6]:配送中心数为1,客户数k为8,车辆载重量q皆为8吨;各客户点需求量为gii=,1,2,…,8,(单位为吨),已知客户点与配送中心间的距离如表1(其中0表示中心仓库),要求合理安排车辆的运输路线,使总运输里程最小。

按照上述程序流程图将该方法编织成C++程序,解上述实例:(1)当建立由8个叶子结点(即此时不添加空白结点)组成的满二叉树时,解得其最优里程为138Km,对应的配送路径为0→8→4→7→2→0和0→1→3→5→6→0。因为此时没有加入空白结点所以配送车辆的配送的需求点的数目只能是偶数,故此时的解不一定是最优解。(2)加入3个空白结点建立由11个叶子结点组成的完全二叉树,解得最优的路程为135Km,对应的配送路线为0→2→8→5→3→1→0和0→6→7→4→0。(3)若加入8个空白结点建立由16个叶子结点组成的完全二叉树,则理论上需要较长的时间才能求出最优的配送路线。

4 小结

本文运用二叉树遍历的思想求解配送路线的选择问题,易于计算机编程实现,能求出问题的最优解,有一定的实际意义。但是由于该算法在结点交换时应用到了结点的排序,故其时间复杂度大,对于大规模的问题计算时间会很长,实用意义较小。但是随着计算机硬件性能的提高该算法的适用性会逐渐增强。为了提高算法的效率,对于结点交换的方式有待进一步研究。

摘要：物流配送是物流中的核心环节,配送成本在整个物流过程费用中占有很大的比重,因此为了减少配送成本有必要对其配送路线进行合理优化。运用二叉树遍历的知识并结合节约算法的思想,将货物需求点作为叶子结点并适当增加一些需求量为零的叶子结点构造一种有特殊意义的二叉树,提出了一种运用这种特殊二叉树在满足车辆额定载货量的前提下寻求最优配送路线的方法,并通过实例证明了其正确性。

关键词：物流配送,二叉树,最优路线

参考文献

[1]姜宏.物流运输技术与实务[M].北京:人民交通出版社,2001.

[2]李严锋,马士华.供应链环境下第三方物流的资源整合[J].经济问题探索,2003(9):65-67.

[3]Sunil Chopra,Peter Meindl.Supply chain management、strategy、planning and operation[M].北京:清华大学出版社,2001.

[4]玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,2000.

[5]徐丽群,侯立文,胡巍.基于GIS的物流配送线路图解优化模型[J].工业工程与管理,2007(4):25-28.