下载文档原格式
⼆叉树详解树是⼀种⽐较重要的数据结构，尤其是⼆叉树。
⼆叉树是⼀种特殊的树，在⼆叉树中每个节点最多有两个⼦节点，⼀般称为左⼦节点和右⼦节点（或左孩⼦和右孩⼦），并且⼆叉树的⼦树有左右之分，其次序不能任意颠倒。
本篇博客将详细为⼤家解析⼆叉树。
⾸先介绍两个概念：满⼆叉树：在⼀棵⼆叉树中，如果所有分⽀结点都有左孩⼦和右孩⼦结点，并且叶⼦结点都集中在⼆叉树的最下层，这样的树叫做满⼆叉树如：完全⼆叉树：若⼆叉树中最多只有最下⾯两层的结点的度数可以⼩于2，并且最下⾯⼀层的叶⼦结点都是依次排列在该层最左边的位置上，则称为完全⼆叉树如：区别：满⼆叉树是完全⼆叉树的特例，因为满⼆叉树已经满了，⽽完全并不代表满。
所以形态你也应该想象出来了吧，满指的是出了叶⼦节点外每个节点都有两个孩⼦，⽽完全的含义则是最后⼀层没有满，并没有满。
⼆叉树的链式存储结构是⼀类重要的数据结构，定义结果为：Cpp代码1. //定义树的结构2. struct node3. {4. node * lchild;5. node * rchild;6. string data;7. //初始化8. node()9. {10. lchild=rchild=NULL;11. }12. };⼆叉树的建⽴⾸先我们⽤户输⼊⽣成⼀棵⼆叉树，要⽣的的⼆叉树如下图所⽰：#代表空结点。
下⾯我们根据上⾯图中所⽰的⼆叉树，利⽤先序依次输⼊ABDG###E#H##C#F##(即先序遍历）⽣成⼆叉树的代码如下：Cpp代码1. //⼆叉树⽣成--先序遍历输⼊要⽣成的⼆叉树数据，#代表空结点2. void CreateTree(node * & root)3. {4. char data;5. cin>>data;6. if(data!='#')7. {8. root=new node;9. root->data=data;10.11. CreateTree(root->lchild);12.13. CreateTree(root->rchild);14.15. }16. }⼆叉树节点查找采⽤递归的⽅法在⼆叉树root⾥查找只为aim的结点，若找到此节点则返回其指针，否则返回NULL 查找代码如下：Cpp代码1. //检查⼆叉树是否包含数据aim,有则返回其指针2. node * Findnode(node * & root,string aim)3. {4. node * p;5. if(root==NULL)//空树6. return NULL;7. else if(root->data==aim)8. return root;9. else10. {11. p=Findnode(root->lchild,aim);12. if(p!=NULL)13. return p;14. else15. return Findnode(root->rchild,aim);16. }17. }这⾥解释⼀下递归中的return的意思：return 对当前函数来说是结束了，对调⽤它的⽗函数来说你这个函数执⾏完成了，⽗函数就会接着执⾏下⼀语句。
第10章二叉树法期权定价及其Python应用本章精粹蒙特卡罗模拟法便于处理报酬函数复杂、标的变量多等问题，但是在处理提前行权问题时却表现出明显的不足。
本章将要介绍的二叉树法可以弥补蒙特卡罗模拟法的这种不足。
二叉树的基本原理是：假设变量运动只有向上和向下两个方向，且假设在整个考察期内，标的变量每次向上或向下的概率和幅度不变。
将考察期分为若干阶段，根据标的变量的历史波动率模拟标的变量在整个考察期内所有可能的发展路径，并由后向前以倒推的形式走过所有结点，同时用贴现法得到在0时刻的价格。
如果存在提前行权的问题，必须在二叉树的每个结点处检查在这一点行权是否比下一个结点上更有利，然后重复上述过程。
10.1 二叉树法的单期欧式看涨期权定价假设：(1) 市场为无摩擦的完美市场，即市场投资没有交易成本。
这意味着不支付税负，没有买卖价差(Bid-Ask Spread)、没有经纪商佣金(Brokerage Commission)、信息对称等。
(2) 投资者是价格的接受者，投资者的交易行为不能显著地影响价格。
(3) 允许以无风险利率借入和贷出资金。
(4) 允许完全使用卖空所得款项。
(5) 未来股票的价格将是两种可能值中的一种。
为了建立好二叉树期权定价模型，我们先假定存在一个时期，在此期间股票价格能够从现行价格上升或下降。
下面用实例来说明二叉树期权定价模型的定价方法。
1. 单一时期内的买权定价假设股票今天(t =0)的价格是100美元，一年后(t =1)将分别以120美元或90美元出售，就是1年后股价上升20%或下降10%。
期权的执行价格为110美元。
年无风险利率为8%，投资者可以这个利率放款(购买这些利率8%的债券)或借款(卖空这些债券)。
如图10-1所示。
今天 1年后t =0 t =1u S 0=120 上升20% 1000=Sd S 0=90 下降10%u 0max(u ,0)max(120110,0)10C S X =-=-=?0=Cd 0max(d ,0)max(90110,0)0C S X =-=-=图10-1 买权价格图10-1表示股票买权的二叉树期权定价模型。
二叉树定价模型期权定价的二叉树模型Cox、Ross和Rubinstein提出了期权定价的另一种常用方法二叉树（binomial tree）模型，它假设标的资产在下一个时间点的价格只有上升和下降两种可能结果，然后通过分叉的树枝来形象描述标的资产和期权价格的演进历程。
本章只讨论股票期权定价的二叉树模型，基于其它标的资产如债券、货币、股票指数和期货的期权定价的二叉树方法，请参考有关的书籍和资料。
8.1一步二叉树模型我们首先通过一个简单的例子介绍二叉树模型。
例8.1 假设一只股票的当前价格是$20，三个月后该股票价格有可能上升到$22，也有可能下降到$18. 股票价格的这种变动过程可通过图8.1直观表示出来。
在上述二叉树中，从左至右的节点（实圆点）表示离散的时间点，由节点产生的分枝（路径）表示可能出现的不同股价。
由于从开始至期权到期日只考虑了一个时间步长，图8.1表示的二叉树称为一步（one-step）二叉树。
这是最简单的二叉树模型。
一般地，假设一只股票的当前价格是，基于该股票的欧式期权价格为。
经过一个时间步（至到期日T）后该股票价格有可能上升到相应的期权价格为；也有可能下降到相应的期权价格为. 这种过程可通过一步（one-step）二叉树表示出来，如图8.2所示。
我们的问题是根据这个二叉树对该欧式股票期权定价。
为了对该欧式股票期权定价，我们采用无套利（no arbitrage）假设，即市场上无套利机会存在。
构造一个该股票和期权的组合（portfolio），组合中有股的多头股票和1股空头期权。
如果该股票价格上升到，则该组合在期权到期日的价值为；如果该股票价格下降到，则该组合在期权到期日的价值为。
根据无套利假设，该组合在股票上升和下降两种状态下的价值应该相等，即有由此可得(8.1)上式意味着是两个节点之间的期权价格增量与股价增量之比率。
在这种情况下，该组合是无风险的。
以表示无风险利率，则该组合的现值（the present value）为 ,又注意到该组合的当前价值是，故有即将(8.1)代入上式，可得基于一步二叉树模型的期权定价公式为(8.2)(8.3)需要指出的是，由于我们是在无套利（no arbitrage）假设下讨论欧式股票期权的定价，因此无风险利率应该满足： .现在回到前面的例子中，假设相应的期权是一个敲定价为$21，到期日为三个月的欧式看涨权，无风险的年利率为12%，求该期权的当前价值。
二叉树的基本性质（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；解释：最多的时候是满二叉树，它的第1层有21-1=1个结点；第2层有22-1=2个结点；第3层23-1=4个结点；第4层有24-1=8个结点；……（2）深度为m的二叉树最多有2m-1个结点，最少有m个结点；（3）对于任意一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个；即如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]+1表示取log2n的整数部分；（5）给定N个节点，能构成h(N)种不同的二叉树；h(N)为卡特兰数的第N项。
h(n)=C(n,2*n)/(n+1)。
（6）具有n个结点的完全二叉树的深度为[log2n]+1；（7）设完全二叉树共有n个结点。
如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
性质1 在二叉树的第i层上至多有2i-1个结点(i>=1)。
证明采用归纳法证明此性质。
当i=1时，只有一个根结点，2i-1=20 =1,命题成立。
现在假定对所有的j，1<=j<i,命题成立，即第j层上至多有2j-2个结点，那么可以证明j＝i时命题也成立。
由归纳假设可知，第i－1层上至多有2i-2个结点。
由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×（2i-2）＝2i-1。
性质2 深度为k的二叉树至多有2k－1个结点（k>=1)。
