树和二叉树的基本知识
树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继；把一个国家或一个地区的各级行政区划分看作为一棵树，树中的结点为行政区的名称及相关信息，树中的关系为上下级关系，如一个城市包含有若干个区，每个区又包含有若干个街道，每个街道又包含有若干个居委会；把一本书的结构看作是一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构；在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。
在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，具有良好的递归特性，特别适宜于程序设计，因此我们常常将一般树型结构转换成二叉树进行处理。
第一节树
一、树的定义
一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：
1．每个元素称为结点(node)；
2．有一个特定的结点，称为根结点或树根（root）；
3．除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合T0,T1,T2,……T m-1，而每一个子集T i又都是一棵树（称为原树的子树subtree）。
图1
图1就是一棵典型的树结构。从树的定义可以看出：
1．树是递归定义的，这就决定了树的操作和应用大都是采用递归思想来解决；
2．一棵树中至少有1个结点，这个结点就是根结点，如上图中的结点1；
3．只有根结点没有前趋结点，其余每个结点都有唯一的一个前趋结点；
4．所有结点都可以有0或多个后继结点；
二、树的基本概念
下面以图1为例给出树结构中的一些基本概念：
1．一个结点的子树个数，称为这个结点的度（degree），如结点1的度为3，结点3的度为0。度为0的结点称为叶结点（又称树叶leaf，如结点3、5、6、8、9）。度不为0的结点称为分支结点（如结点1、2、4、7）。根结点以外的分支结点又称为内部结点（如结点2、4、7）。树中各结点的度的最大值称为这棵树的度（又称宽度），图1所示这棵树的（宽）度为3。
2．在用上述图形表示的树结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端的结点为下端结点的父结点，称下端的结点为上端结点的子结点，称同一个父结点的多个子结点为兄弟结点。如结点1是结点2、3、4的父结点，结点 2、3、4都是结点1的子结点，它们又是兄弟结点，同时结点2又是结点5、6的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点1、4、7是结点8的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点7、8、9都是结点4的子孙。
3．定义一棵树的根结点的层次（level）为1，其它结点的层次等于它的父结点的层次数加1。如结点2、3、4的层次为2，结点5、6、7的层次为3，结点8、9的层次为4。一棵树中所有结点的层次的最大值称为树的深度（depth），图1所示这棵树的深度为4。
4．若树中各结点的子树是按照一定的次序从左向右安排的，它们之间的次序不能互换，这样的树称之为有序树，否则称之为无序树。所以，树虽然是非线性结构，但也是有序结构。例如，对于下面图2中的两棵树，若看作为无序树，则是相同的；若看作为有序树，则是不同的，因为根结点A的两棵子树的次序不同。又如对于一棵反映了父子关系的家族树，兄弟结点之间是按照排行大小而有序排列的，所以它是一棵有序树。因为任何无序树都可以当作具有任一次序的有序树来处理，所以下面如果不特别指明，均认为树是有序的。
图2
5.对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。如图1中，结点1和结点8之间存在着一条路径，并可用（1、4、7、8）表示这条路径，该条路径的长度为3。从根结点出发，到树中的其余结点一定存在着一条路径。注意，不同子树上的结点之间不存在路径。但是，如果把树看成是一个图的话(可以把树理解为是图的一个子类)，那么我们就可以继承图的路径的定义，认为不同子树上的两个结点应该是有路径的（图论意义上的路径）。
6．森林（forest）是m(m>=0)棵互不相交的树的集合。
三、树的表示方法和存储结构
树的表示方法有多种，如图1采用的就是一种形象的树形表示法；另外还有一种常用的表示方法“括号表示法”，它的表示方法归纳如下：先将整棵树的根结点放入一对圆括号中，然后把它的子树由左至右放入括号中，同层子树用圆括号括在一起（同层子树之间用逗号隔开），而对子树也采用同样的方法处理，直到所有的子树都只有一个根结点为止。用括号表示法表示图1的步骤如下：
=（T）
=（1（T1，T2 ，T3 ）） {A是根结点，有3棵子树，用逗号隔开}
=（1（2（T11，T12），3，4（T31））） {分别对3棵子树做同样的操作}
=（1（2（5，6），3，4（7（T311，T312））））
=（1（2（5，6），3，4（7（8，9））））
实际上，以上方法是按照树的层次逐步展开，直到所有结点都已列出。
树的存储结构也有多种形式，其中使用较多的采是链式存储结构，下面给出几种常见的存储树的数据结构。
1．父亲表示法：定义一个数组，每个数组元素为一个记录，除了存放一个结点的数据信息外，还存放该结点的父结点编号。数据结构定义如下：
Const m=10； {树的结点数}
Type node=Record
data:Integer； {数据域}
parent:Integer； {指针域}
End；
Var tree:Array[1..m] Of node；
这种方法充分利用了树中除根结点外每个结点都有唯一的父结点这个性质，很容易找到树根（可以规定根结点的父结点为0），但找孩子时却需要遍历整个线性表。
2．孩子表示法：利用单链表，每个结点包括一个数据域和若干个指针域，每个指针都指向一个孩子结点。由于一般树的各个结点的孩子数不确定，所以指针数应该等于整棵树的度。当树的度越大时，空指针域所占比例也越大，给存储空间造成很大浪费。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
Const m=10； {树的度}
Type tree=^node；
node=Record
data:Char； {数据域}
child:Array[1..m] Of tree {指针域，指向若干孩子结点}
End；
Var t:tree；
注：空间上的浪费其实可以用“虚开实用”的方法完美地解决，在FreePascal等环境下可以用Getmem、Freemem等过程达到这个目的，这样建立一棵普通树的时间复杂度也是很不错的。有兴趣的同学可以参考有关书籍与程序。
由于每个结点都只存放各自孩子结点的编号，所以这种方法只能从根（父）结点遍历到子结点，不能从某个子结点返回到它的父结点。
3．父亲孩子表示法：利用双链表结构，每个结点包括一个数据域和二个指针域，一个指向该结点的若干孩子结点，一个指向其父结点。克服了上述第1种存储方法的缺点，假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
Const m=10；
Type tree=^node；
node=Record
data:Char；
child:Array[1..m] Of tree；
father:tree
End；
Var t:tree；
4．孩子兄弟表示法：有些程序中需要对兄弟结点进行处理，这种情况下，可以使用另外一种双链表结构，每个结点包括一个数据域和二个指针域，一个指针指向该结点的第一个孩子结点，一个指针指向该结点的下一个兄弟结点。克服了上述第2种存储方法的缺点，假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
Type tree=^node；
node=Record
data:Char；
firstchild,next: tree；
End；
Var t:tree；
四、树的遍历
在应用树结构解决问题时，往往需要按照某种次序获得树中全部结点的信息，这种操作叫做“树的遍历”。遍历一般按照从左向右的顺序，常用的遍历方法有：
1．先序（根）遍历：先访问根结点，再从左到右按照先序思想遍历各棵子树。
图1先序遍历的结果为：{1，2，5，6，3，4，7，8，9}；
2．后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。
图1后序遍历的结果为：{5，6，2，3，8，9，7，4，1}；
3．层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。
图1层次遍历的结果为：{1，2，3，4，5，6，7，8，9}；
4．叶结点遍历：有时我们把所有的数据信息都存放在叶结点中，而其余结点都是用来表示数据之间的某种分支或层次关系，这种情况就用这种方法。
图1按照这个思想访问的结果为：{5，6，3，8，9}；
很明显，先序遍历和后序遍历两种方法的定义是递归的，所以在程序实现时往往也是采
用递归的思想，既通常所说的“深度优先搜索”。按照先序遍历思想编写的递归过程如下：Procedure tra1(t,m) {访问以t为根结点的含有m棵子树的过程}
Begin
If t <>Nil Then Begin
Write(t^.data,’’)； {访问根结点}
For I:=1 To m Do {前序遍历各子树}
tra1(t^.child[I],m)；
End；
End；
也可以用堆栈的方法编写这个程序，留给读者作为练习。
层次遍历应用也较多，实际上就是我们所说的“广度优先搜索”。思想如下：若某个结点被访问，则该结点的子结点应被记录下来，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：
Const n=100；
Var head,tail,i:integer；
q:array[1..n] of tree；
p:tree；
Begin
tail:=1；head:=1； {初始化}
q[tail]:=t；tail:=tail+1； {t进队}
While ( head p:=q[head]；head:=head+1； {取出队首结点} Write(p^.data,‘‘)； {访问某结点} For i:=1 To m Do {该结点的所有子结点按顺序进队} If p^.child[i]<>Nil Then Begin q[tail]:=p^.child[I]；tail:=tail+1； End； End； End； 例1：单词查找树 [问题描述] 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母； 2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词； 3．在满足上述条件下，该单词查找树的结点数最少。 4．例如图3左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列 表，请统计对应的单词查找树的结点数（包含根结点）。 [问题输入] 输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母。文件总长度不超过32K，至少有一行数据。 [问题输出] 输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。 [样例输入] A AN ASP AS ASC ASCII BAS BASIC [样例输出] 13 图3 [算法分析] 首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位……如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加入单词查找树中去。但，本问题只是问你结点总数，而非建树方案，且有32K 文件，所以应该考虑能不能通过不建树就直接算出结点数？为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则说单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中已有单词的差的最小值。 单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是，得出建树的等效算法： ①读入文件； ②对单词列表进行字典顺序排序； ③依次计算每个单词对前一单词的差，并把差累加起来。注意：第一个单词相对于“空”的差为该单词的长度； ④累加和再加上1（根结点），输出结果。 就给定的样例，按照这个算法求结点数的过程如下表： 表1 [数据结构] 先确定32K（32*1024=32768字节）的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复，所以长度为1的单词（单个字母）最多26个；长度为2的单词最多为26*26=676个；因为每个单词后都要一个换行符（换行符在计算机中占2个字节），所以总共已经占用的空间为：（1+2）*26+（2+2）*676=2782字节；剩余字节（32768-2782=29986字节）分配给长度为3的单词（长度为3的单词最多有26*26*26=17576个）有29986/（3+2）≈5997。所以单词数量最多为26+676+5997=6699。 定义一个数组：a：array[1..32767] of char；把所有单词连续存放起来，文件中每个单词后的换行符转换成数组中的一个“空格”字符。这样既省略了一个存放单词长度的数组，又方便且节省了一点空间。另外为了排序，再设一个数组index:array[1.. 6700] of integer；存放每个单词在a中的起始位置。这样，排序时用a比较，但只要交换index的值就可以了。 [参考程序] Program p1(Input, Output)； Var a:Array[1..32767] Of Char； index:Array[1..6700] Of Integer； n,k,i,j,tot,t:Integer； s,pre,now:String； Function cmp(i, j:Longint):Boolean；{比较从a[i]开始的字符串和从a[j]开始的字符串Begin 大小，小于则返回False，否则返回True} While ((a[i]=a[j]) And (Ord(a[i])<>32) And (Ord(a[j])<>32)) Do Begin Inc(i)；Inc(j)；End； If (a[i] End； Begin {main} Assign(Input,'word.in')； Reset(Input)； Assign(Output,'word.out')；Rewrite(Output)； Fillchar(a, sizeof(a), 0)； n := 0；{单词个数} k := 0；{下标} While (Not Eof) Do {读入文件中的单词并且存储到数组中} Begin Readln(s)； n := n+1； index[n] := k+1；{第n个单词的首字母起点下标} For i:=1 To Length(s) Do {存入一个单词} a[k+i] := s[i]； k := k+i+1； {为下个单词的下标设定好初值,i即为当前单词的长度} End； For i:=1 To n Do {n个单词的字典排序} For j:=i+1 To n Do If cmp(index[i], index[j]) Then Begin t := index[i]；index[i] := index[j]；index[j] := t；End； tot := 0； {计数器} pre := ''； {前一个单词} For i:=1 To n Do {统计} Begin now := ''； j := index[i]； {第i个单词的首字母在a数组中的下标为j} While (Ord(a[j])<>0) Do {换行符换成了空格} Begin now := now + a[j]；j := j+1；End； {当前处理的单词存入now中} j := 1； While ((pre[j]=now[j]) And (j<=length(pre))) Do Inc(j)；{求两个单词的差} tot := tot+(Length(now)-j+1)； {累加} pre := now；{把当前单词作为下次比较的前一个单词} End； Writeln(tot+1)； Close(Input)； Close(Output)； End. 第二节二叉树 一、二叉树的概念 二叉树（binary tree,简写成BT）是一种特殊的树型结构，它的特点是每个结点至多只有二棵子树，即二叉树中不存在度大于2的结点，而且二叉树的子树有左子树、右子树之分，孩子有左孩子、右孩子之分，其次序不能颠倒，所以二叉树是一棵有序树。它有如下5种基本形态： 图4 第一节讲述的树的一些术语、概念也基本适用于二叉树，但二叉树与树也有很多不同，如：二叉树的每个结点至多只能有两个结点，二叉树一定是有序的，二叉树可以为空（但树不能为空，至少要有1个结点）。 二、二叉树的性质： 性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。 性质2：深度为k的二叉树至多有2k –1个结点（k>=1）。 特别地，一棵深度为k且有2k –1个结点的二叉树称为满二叉树。图5是深度为4的满二叉树，这种树的特点是每层上的结点数都达到了最大值。 图5 可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。如图6就是一个深度为4，结点数为12的完全二叉树。 图6 完全二叉树具有如下特征：叶结点只可能出现在最下面两层上；对任一结点，若其右子树深度为m，则其左子树的深度必为m或m+1。图7和图8所示的两棵二叉树就不是完全二叉树，请读者思考为什么？ 图7 图8 性质3：对任何一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。性质4：具有n个结点的完全二叉树的深度为trunc(LOG2n)+1 （trunc为取整函数） 性质5：一棵n个结点的完全二叉树，对于任一编号为i结点，有： 1．如果i=1,则结点i为根，无父结点；如果i>1,则其父结点编号为trunc(i/2)。 2．如果2*i>n，则结点i为叶结点；否则左孩子编号为2*i。 3．如果2*i+1>n，则结点i无右孩子；否则右孩子编号为2*i+1。 三、二叉树的存储结构 二叉树的存储结构与普通树的存储结构基本相同，有链式和顺序存储两种方法。 1．链式存储结构:单链表结构或双链表结构，基本数据结构定义如下： Type tree=^node； {单链表结构} node=Record data:Char； {数据域} lchild,rchild:tree {指针域：分别指向左、右孩子} End； Var bt:tree； Type tree=^node； {双链表结构} node=Record data:Char； {数据域} lchild,rchild,father:tree {指针域：分别指向左、右孩子及父结点} End； Var bt:tree； 如图9左边所示的一棵二叉树用单链表就可以表示成右边的形式。 bt 图9 2．顺序存储结构:即几个数组加一个指针变量，一般用在满二叉树和完全二叉树中，将每个结点编号后作为数组的下标变量值，基本数据结构定义如下： Const n=10； {最多10个结点} Var data:Array[1..n] Of Char； {n个结点的数据域} lchild:Array[1..n] Of Integer； {n个结点的左孩子} rchild:Array[1..n] Of Integer； { n个结点的右孩子} bt:Integer； {根结点指针} 这种结构可以很方便地从根结点往下遍历，但是如果想从某个分支结点或叶结点遍历整 棵树，则还需设置一个父结点数组，操作也教麻烦。其实如果树的结点较少，也可采用邻接矩阵的方法，这样操作起来也很方便。 二叉树在处理表达式时经常用到，一般用叶结点表示运算数，分支结点表示运算符。这样的二叉树称为表达式树，如表达式（a+b/c）*(d-e)就可以表示成图10。 bt 图10 例2：医院设置 [问题描述] 设有一棵二叉树（如图11），其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2*20+2*40=136；若医院建在3处，则距离和=4*2+13+20+40=81…… [输入格式] 输入文件名为hospital.in，其中第一行一个整数n，表示树的结点数（n<=100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。 [输出格式] 输出文件名为hospital.out，该文件只有一个整数，表示最小距离和。 [样例输入] 5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 [样例输出] 81 [问题分析] 这是一道简单的二叉树应用问题，问题中的结点数并不多，数据规模也不大，采用邻接矩阵存储，用Floyed法求出任意两结点之间的最短路径长，然后穷举医院可能建立的n个结点位置，找出一个最小距离的位置即可。当然也可以用双链表结构或带父结点信息的数组存储结构来解决，但实际操作稍微麻烦了一点。 2[参考程序] Program p2(Input, Output)； Var a : Array [1..100] Of Longint ； g : Array [1..100, 1..100] Of Longint ； n, i, j, k, l, r, min, total : Longint ； Begin Assign(Input, 'hospital.in')； Reset(Input)； Assign(Output, 'hospital.in')； Readln(n)； For i := 1 To n Do 图11 For j := 1 To n Do g[i][j] := 1000000； For i := 1 To n Do {读入、初始化} Begin g[i][i] := 0； Readln(a[i], l, r)； If l > 0 Then Begin g[i][l] := 1；g[l][i] := 1 End ； If r > 0 Then Begin g[i][r] := 1；g[r][i] := 1 End ； End ； For k := 1 To n Do {用Floyed 法求任意两结点之间的最短路径长} For i := 1 To n Do If i <> k Then For j := 1 To n Do If (i <> j) And (k <> j) And (g[i][k] + g[k][j] < g[i][j]) Then g[i][j] := g[i][k] + g[k][j]； min := Maxlongint ； For i := 1 To n Do {穷举医院建在N 个结点，找出最短距离} Begin total := 0； For j := 1 To n Do Inc(total, g[i][j] * a[j])； If total < min Then min := total ； End ； Writeln(min)； Close(Input)；Close(Output)； End. [后记] 在各种竞赛中经常遇到这样的问题：N-1条公路连接着N 个城市，从每个城市出发都可以通过公路到达其它任意的城市。每个城市里面都有一定数量的居民，但是数量并不一定相等，每条公路的长度也不一定相等。X 公司（或者是政府）决定在某一个城市建立一 个医院/酒厂/游乐场……，问：将它建在哪里，可以使得所有的居民移动到那里的总耗费最小？这种题目都是本题的“变型”，一般称为“树的中心点问题”。除了简单的穷举法外，还有更好的时间复杂度为O(n)的算法，我们讲在后面的章节中继续讨论。 四、普通树转换成二叉树 由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。如何转换呢？一般方法如下： 1．将树中每个结点除了最左边的一个分支保留外，其余分支都去掉； 2．从最左边结点开始画一条线，把同一层上的兄弟结点都连起来； 3．以整棵树的根结点为轴心，将整棵树顺时针大致旋转45度。 第一节中的图1所示的普通树转换成二叉树的过程如图12所示： 图12 同样我们可以把森林也转换成二叉树处理，假设F={T1，T2，…，Tm}是森林，则可按如下规则转换成一棵二叉树B=(root,lb,rb)。 1．若F为空，即m=0，则 B为空树； 2．若F非空，即m<>0，则B的根root即为森林中第一棵树的根root(T1)；B的左子树lb是从T1中根结点的子树森林F1={T11，T12，…，T1m1}转换而成的二叉树；其右子树rb 是从森林F’ ={T2，T3，…，Tm}转换而成的二叉树。 五、二叉树的遍历 在二叉树的应用中，常常要求在树中查找具有某种特征 的结点，或者对全部结点逐一进行某种处理,这就是二叉树的 遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问 树中的各个结点，而且每个结点仅被访问一次。“访问”的含 义很广，可以是对结点作各种处理，如输出结点的信息等。 遍历方法共有3种：先序（根）遍历，中序（根）遍历，图13 后序（根）遍历。下面以图13所示的二叉树为例分别讲解这3种方法。 1．先序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①访问根结点 ②先序遍历左子树 ③先序遍历右子树 很明显，这是一种递归定义，下面给出一种手工方法（括号法）求先序遍历的结果。 ={1，2，3，4，5，6，7，8，9} {所有结点} ={1，{2，4，5，7}，{3，6，8，9}} {按先序思想遍历，将根结点单独列出，左右子树 分别用括号括起来} ={1，{2，{4，7}，{5}}，{3，{}，{6，8，9}}} {再对以2、3结点为根的树先序遍历} ={1，{2，{4，{7}，{}，5}，{3，{}，6，{8}，{9}}} {再对以4、5、6结点为根的树先序遍历，遇到无左、右子树的情况就用一对空括号，遇到叶子结点就脱到本层括号，遇到空括号就省略} ={1，2，4，7，5，3，6，8，9} {去掉内层所有括号，得到结果} 2．中序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①中序遍历左子树 ②访问根结点 ③中序遍历右子树 可以根据以上方法，得出上图中序遍历的结果为：{7，4，2，5，1，3，8，6，9} 3．后序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①后序遍历左子树 ②后序遍历右子树 ③访问根结点 可以根据以上方法，得出上图后序遍历的结果为：{7，4，5，2，8，9，6，3，1} 显然，以上3种遍历方法都是采用递归的思想，下面以先序遍历为例给出递归算法：Procedure preorder(bt:tree)；{先序遍历根结点为bt的二叉树的递归算法} Begin If bt<>Nil Then Begin Write(bt^.data)； preorder(bt^.lchild)； preorder(bt^.rchild)； End； End； 我们也可以把递归过程改成用栈实现的非递归过程，下面给出先序遍历的非递归过程。 Procedure inorder(bt:tree)； {先序遍历bt所指的二叉树} Var stack:Array[1..n] Of tree； {栈} top:integer； {栈顶指针} p:tree； Begin top:=0； While Not ((bt=Nil)And(top=0)) Do Begin While bt<>Nil Do Begin {非叶结点} Write(bt^.data)； {访问根} top:=top+1； {右子树压栈} stack[top]:=bt^.rchild； bt:=bt^.lchild； {遍历左子树} End； If top<>0 Then Begin {栈中所有元素出栈，遍历完毕} b:=stack[top]；top:=top-1； End； End； End； 关于前面讲的表达式树，我们可以分别用先序、中序、后 序的遍历方法得出完全不同的遍历结果，对于图14采用三种遍 历后的结果如下，它们正好对应着表达式的三种表示方法： -+a*b-cd/ef (前缀表示、波兰式) a+b*c-d-e/f (中缀表示、代数式) abcd-*+ef/- (后缀表示、逆波兰式) 图14 六、二叉树的其它重要操作： 除了“遍历”以外，二叉树的其它重要操作还有：建立一棵二叉树、插入一个结点到二叉树中、删除结点或子树等，下面分别给出基本算法框架。 1．建立一棵二叉树 Procedure pre_crt(Var bt:tree)；{按先序次序输入二叉树中结点的值， Begin 生成二叉树的单链表存储结构} Read(ch)； If ch=’’ Then bt:=Nil {’’表示空树} Else Begin New(bt)； {建根结点} bt^.data:=ch； pre_crt(bt^.lchild)； {建左子树} pre_crt(bt^.rchild)； {建右子树} End； End； 2．删除二叉树 Procedure dis(Var bt:tree)； Begin If bt<>Nil Then Begin Dis(bt^.lchild)； {删左子树} Dis(bt^.rchild)； {删右子树} Dispose(bt)； {释放父结点} End； End； 3．插入一个结点到二叉树中 Procedure insert(Var bt:tree；n:Integer)； Begin If bt=Nil Then Begin {空树，则为根结点} New(bt)； bt^.data:=n； bt^.lchild:=Nil； bt^.rchild:=Nil； End Else If n Else If n>bt^.data Then insert(bt^.rchild,n)； {>，右} End； 4．在二叉树中查找一个数，找到返回该结点,否则返回nil Function find(bt:tree；n:Integer):tree； Begin If bt=Nil Then find:=Nil Else If n Else If n>bt^.data Then find(bt^.rchild,n) Else find:=bt； End； 5．用嵌套括号表示法输出二叉树 Procedure print(bt:tree)； Begin If bt<>Nil Then Begin Write(bt^.data)； If (bt^.lchild<>nil) Or (bt^.rchild<>nil) Then Begin Write(‘(’)；print(bt^.lchild)； If bt^.rchild<>Nil Then Write(‘,’)； print(bt^.rchild)；Write(‘)’)； End； End； End； 七、二叉树的计数问题 在实际应用中经常需要求“具有n个结点的不同形态的二叉树有多少棵？具有n个结点的不同形态的树有多少棵？”要解决上述问题，首先要了解下面两个概念：“相似二叉树”是指两者都为空树或者两者均不为空树，且它们的左右子树分别相似。“等价二叉树”是指两者不仅相似，而且所有对应结点上的数据元素均相同。二叉树的计数问题就是讨论具有n个结点、互不相似的二叉树的数目Bn。 在n很小时，很容易得出，B0=1，B1=1，B2=2，B3=5（见图15）。 图15 一般情况，一棵具有n(n>0)个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树、和一棵具有n-i-1个结点的右子树组成，其中0（无左子树）<=i<=n-1（无右子树）,i=0表示无左子树，i=n-1表示无右子树，根据乘法原理可以得出具有n个结点的不同形态的二叉树有Bn棵： Bn = ∑- = -- 1 1 * n i i Bn Bi（n>0） 特别地：Bn = 1 (n=0) 我们可以利用生成函数（有兴趣的同学自己查阅相关书籍）讨论这个递归公式，得出：Bn=C n2n /(n+1)。 由于n个结点的树可以转换成根结点固定的、下面有n-1个结点的二叉树,所以可以推出：Tn=B（n-1）。即具有n个结点的不同形态的树有C n-12n-2 /n棵。 八、由遍历结果确定二叉树的形态问题 下面我们换个角度考虑这个问题，从二叉树的遍历已经知道，任意一棵二叉树的先序遍历结果和中序遍历结果都是唯一的。那么反过来，给定一棵二叉树的先序遍历结果和中序遍历结果，能否确定一棵二叉树呢（即是否唯一）？ 由定义，二叉树的先序遍历是先访问根结点，再遍历左子树，最后遍历右子树。即在二叉树的先序遍历结果中，第一个结点必是根，假设为root。再结合中序遍历，因为中序遍历是先遍历左子树，再访问根，最后遍历右子树。所以结点root正好把中序遍历结果分成了两 部分，root之前的应该是左子树上的结点，root之后的应该是右子树上的结点，依次类推，便可递归得到一棵完整的、确定的二叉树。即：已知一棵二叉树的先序遍历结果和中序遍历结果可以确定一棵二叉树。可以同理推出：已知一棵二叉树的后序遍历结果和中序遍历结果也可以确定一棵二叉树。但，已知一棵二叉树的先序遍历结果和后序遍历结果却不能确定一棵二叉树，为什么？你可以举出反例吗？ 例如已知一棵二叉树的先序遍历结果为ABCDEFG，中序遍历结果为CBEDAFG。构造出这棵二叉树的步骤如图16： 图16 例3: 二叉树的遍历问题 [问题描述] 输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。 [输入格式] 输入文件为tree.in，共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。 [输出格式] 输出文件为tree.out，仅一行，表示树的后序遍历序列。 [样例输入] abdec dbeac [样例输出] debca [参考程序] Program p3(Input, Output)； Var s1, s2 : String； Procedure try(l1, r1, l2, r2 : Integer)； {递归、后序} Var m : Integer； Begin m := pos(s1[l1], s2)； {求l1的第一个字符在l2中的位置} If m > l2 Then try(l1 + 1, l1 + m - l2, l2, m - 1)； {遍历第m个的左半边} If m < r2 Then try(l1 + m - l2 + 1, r1, m + 1, r2)； {遍历第m个的右半边} Write(s1[l1]) End； Begin {main} Assign(Input，’tree.in’)； Reset(Input)； Assign(Onput，’tree.out’)； Rewrite(Onput)； Readln(s1)；Readln(s2)； try(1, Length(s1), 1, Length(s2))； Writeln Close(Input)； Close(Output)； End. 全国计算机等级考试二级公共基础之树与二叉树 1.6 树与二叉树 1.6.1 树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。如图： 在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根（如R）。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点（如W，Z，A ，L，B，N，O，T，H，X）。 在树结构中，一个结点拥有的后件个数称为结点的度（如R的度为4，KPQDEC 结点度均为2）。 树的结点是层次结构，一般按如下原则分层：根结点在第1层；同一个层所有结点的所有子结点都在下一层。树的最大层次称为树的深度。如上图中的树深度为4。R结点有4棵子树，KPQDEC结占各有两棵子树；叶子没有子树。 在计算机中，可以用树结构表示算术运算。在算术运算中，一个运算符可以有若干个运算对象。如取正（+）与取负（-）运算符只有一个运算对象，称为单目运算符；加（+）、减（-）、乘（*）、除（/）、乘幂（**）有两个运算对象，称为双目运算符；三元函数f(x,y,z)为 f函数运算符，有三个运算对象，称为三目运算符。多元函数有多个运算对象称多目运算符。 用树表示算术表达式原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点 (2)运算符的每一个运算对象在树中为该运算结点的子树(在树中的顺序从 左到右) (3)运算对象中的单变量均为叶子结点 根据上面原则，可将表达式：a*(b+c/d)+c*h-g*f表示如下的树。 树在计算机中通常用多重链表表示，多重链表的每个结点描述了树中对应结点的信息，每个结点中的链域（指针域）个数随树中该结点的度而定。 1.6.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是很有用的非线性结构。它与树结构很相似，树结构的所有术语都可用到二叉树这种结构上。 二叉树具有以下两个特点： （1）非空两叉树只有一个根结点 （2）每个结点最多有两棵子树，且分别称该结点的左子树与右子树。 也就是说，在二叉树中，每一个结点的度最大为2，而且所有子树也均为二叉树。二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有。 //二叉树的基本操作 #include 二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include /*二叉树的基本参数计算*/ #include t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=T->data; t1=swap(T->lchild); //交换左右子树 t2=swap(T->rchild); t->lchild=t2; t->rchild=t1; } return(t); } //求树的叶子结点数 int leafs(BiTree T) { int num1,num2; if(T==NULL) return 0; else if(T->lchild==NULL&&T->rchild==NULL) return 1; else { num1=leafs(T->lchild); num2=leafs(T->rchild); return (num1+num2); } } //求二叉树的深度 int Depth(BiTNode *T) { int dep1,dep2; if(T==NULL) return(0); else { dep1=Depth(T->lchild); dep2=Depth(T->rchild); if(dep1>dep2) return(dep1+1); else return(dep2+1); } } //按广义表形式输出二叉树 void Disptree(BiTNode *T) 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 实验6.1 实现二叉树各种基本运算的算法 编写一个程序algo6-1.cpp，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（T为如图所示的一棵二叉树）： （1）以括号表示法输出二叉树T。 （2）输出H结点的左、右孩子结点值。 （3）输出二叉树T的叶子结点个数。 （4）输出二叉树T的深度。 （5）输出对二叉树T的先序遍历序列。 （6）输出对二叉树T的中序遍历序列。 （7）输出对二叉树T的后序遍历序列。 提示：创建二叉树的算法参见书上131页的算法6.4。按先序序列输入二叉树中结点的值（一个字符），#字符表示空树。输入序列： ABD##EHJ##KL##M#N###CF##G#I## 以括号表示法输出二叉树的结果为： A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))) 程序段 #include 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test10.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： typedef struct BiTNode { TElemType data ; struct BiTNode *lchild , *rchild ; }BiTNode,*BiTree ; 基本操作如下： ①void InitBiTree(BiTree &T ) //初始化二叉树T ②void CreateBiTree(BiTree &T) //按先序遍历序列建立二叉链表T ③bool BiTreeEmpty (BiTree T); //检查二叉树T是否为空，空返回1，否则返回0 ④int BiTreeDepth(BiTree T); //求二叉树T的深度并返回该值 ⑤void PreOrderTraverse (BiTree T); //先序遍历二叉树T ⑥void InOrderTraverse (BiTree T); //中序遍历二叉树T ⑦void PostOrderTraverse (BiTree T); //后序遍历二叉树T ⑧void DestroyBiTree(BiTree &T) //销毁二叉树T 二 叉 树 基 本 运 算 班级：计科112 姓名：张航 学号：201100814205辅导老师：高艳霞 二叉树的各种基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历， 分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验步骤 1.程序源码 #include 第六章树 第一部分：知识点 知识脉络： 重点：二叉树的性质、：I树的各种遍历方法及它g1所确定的序列问的关系、 二又树上的基本运算算法 的实现、二又树的线索化方法，构造赂夫曼树的方法。 难点：二叉树上各种算法，特别是遍历的非递归算法的设计。 一、二叉树的遍历的非递归算法 1.先序遍历 先将根结点入栈，然后只要栈不空，先出栈，然后沿着左子针依次访问沿途经过的子树根结点，同时将右指针进栈（以便递归访问左子树后访问右子树），如此重复，直至栈为空。 void PreOrderBiTree(BitTree T) { SqStack S; BitTree p; InitStack(&S); /* 初始化一个空栈*/ Push(&S,T); /* 根结点指针进栈*/ while(!EmptyStack(S)) /* 栈为空时算法结束*/ { Pop(S，&p); /* 弹栈，p指向(子树)根结点*/ while(p) { printf("%d ",p->data); /* 访问根结点*/ if(p->rchild) Push(S,p->rchild); /* 非空的右指针进栈*/ p=p->lchild; /* 沿着左指针访问，直到左指针为空*/ } } 2.中序遍历 先沿着左指针走到最左下的结点同时将沿途经过的（子树）根结点指针进栈。当走到空指针时，出栈得到一个结点并访问，然后跳到右子树上。如此重复，直到指针为空并且栈为空为止。 void InOrderBitree(BitTree T) { SqStack S; BitTree p; InitStack(&S); /* 初始化一个栈*/ p=T; /* p指向根结点*/ while(p||!EmptyStack(S)) /* 当p为空且栈为空时算法结束*/ { while(p) { Push(S,p); p=p->lchild; /* 沿左指针走，沿途经过的(子树)根结点指针进栈*/ } Pop(S，&p); printf("%d ",p->data); /*当左指针为空时弹栈并访问该结点(子树根结点) */ p=p->rchild; /* 向右跳一步到右子树上继续进行遍历过程*/ } } 3.后序遍历 void PostOrderBiTree(BitTree T) { SqStack S; BitTree p,q; InitStack(S); p=T;q=NULL; while(p||!EmptyStack(S)) { if(p!=q) { while(p) { Push(S,p); if(p->lchild) p=p->lchild; else p=p->rchild; } } if(S->top==S->base) break; GetTop(S,&q); if(q->rchild==p) { p=Pop(S); printf("%d ",p->data); } else p=q->rchild; } 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include 树和二叉树的基本知识 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继；把一个国家或一个地区的各级行政区划分看作为一棵树，树中的结点为行政区的名称及相关信息，树中的关系为上下级关系，如一个城市包含有若干个区，每个区又包含有若干个街道，每个街道又包含有若干个居委会；把一本书的结构看作是一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构；在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。 在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，具有良好的递归特性，特别适宜于程序设计，因此我们常常将一般树型结构转换成二叉树进行处理。 第一节树 一、树的定义 一棵树（tree）是由n（n>0）个元素组成的有限集合，其中： 1．每个元素称为结点(node)； 2．有一个特定的结点，称为根结点或树根（root）； 3．除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合T0,T1,T2,……T m-1，而每一个子集T i又都是一棵树（称为原树的子树subtree）。 图1 图1就是一棵典型的树结构。从树的定义可以看出： 1．树是递归定义的，这就决定了树的操作和应用大都是采用递归思想来解决； 2．一棵树中至少有1个结点，这个结点就是根结点，如上图中的结点1； 3．只有根结点没有前趋结点，其余每个结点都有唯一的一个前趋结点； 4．所有结点都可以有0或多个后继结点； 创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* //二叉树的基本操作 #include cout<<"--------------请选择------------"< [1996] 设t 为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。 int swithLRChild(BiTree *t) { BiTree *stack[100] = {0}; int stack_length = 0; if (NULL == t){ return 0; } stack[stack_length++] = t; while (stack_length > 0){ //pop stack BiTree *node = stack[stack_length - 1]; stack_length -= 1; BiTree *temp = node ->lchild; node->lchild = node ->rchild; node->rchild = temp; if (NULL != node ->rchild){ stack[stack_length++] = node ->rchild;} if (NULL != node ->lchild){ stack[stack_length++] = node ->lchild; } } return 1; } [1998]一棵高度为K 且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t 中，试设计删除树中序号为i 且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树(不一定是完全二叉树)的算法。 //存数据的位置是从 1 的索引开始的，避免需要访问索引为0 的空间，避免需要频繁的索引 转换 void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) { //因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了 int del_node_index = 2*i; if (2*del_node_index + 1 >= *last_index) 二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include 二项式期权定价模型 1.实验名称： 二项式期权定价模型 2.实验目的： 利用二叉树期权定价模型公式Excel 模板计算期权价格。 3.基本原理 计算到期时资产价值的分布，求出资产的期望值，用适当的贴现率计算现值，得到资产的当前价值。 （1） 计算n 期中上升i 次的概率： ()(1)i i n i i n P n C p p -=-； （2） 计算在终期时的价格分布： ()0i n i ni S S u d -= （3） 计算期权的价值： ()0max(,0)i n i ni Call S u d K -=-，()0max(,0)i n i ni Put K S u d -=-； （4）计算终期时的期望值：0 ()n n ni i ECall P i Call ==∑， ()n n ni i EPut P i put ==∑； （5）计算期权在起初时刻的价值： ()00 (1)max(,0)n RT RT i i n i i n i n i Call e ECall e C p p S u d K ----===--∑ ()00 (1)max(,0)n RT RT i i n i i n i n i Put e EPut e C p p K S u d ----===--∑。 4. 实验数据域内容 已知股票价格为50，执行价格为50，时间为半年，无风险利率为5%，波动率为20%， 分为10个时间段，利用二叉树定价模型计算看涨看跌期权的价格。 5. 操作过程与结果 （1）定义变量的符号 在单元格B2—B14中分别输入S 、K 、T 、R 、VOL 、n 、dt 、u 、d 、G-factor 、D-factor 、p 分别表示股票价格、期权执行价格、期权有效期、无风险利率、股价波动率、时段数、时段、上升因子、下降因子、增长因子、贴现因子、风险中性概率。如图： 二叉树定价模型 期权定价的二叉树模型 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）为 ,又注意到该组合的当前价值是，故有 即 二叉树的基本操作实验报告 学号姓名实验日期 2012-12-26 实验室计算机软件技术实验指导教师设备编号 401 实验内容二叉树的基本操作 一实验题目 实现二叉树的基本操作的代码实现 二实验目的 1、掌握二叉树的基本特性 2、掌握二叉树的先序、中序、后序的递归遍历算法 3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求 (1)认真阅读书上给出的算法 (2)编写程序并独立调试 四、给出二叉树的抽象数据类型 ADT BinaryTree{ //数据对象D:D是具有相同特性的数据元素的集合。 //数据关系R: // 若D=Φ，则R=Φ，称BinaryTree为空二叉树; // 若D?Φ，则R={H}，H是如下二元关系; // (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1， // (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。 //基本操作: CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。 // 操作结果:按definiton构造二叉树T。 BiTreeDepth( T ) // 初始条件:二叉树T存在。 // 操作结果:返回T的深度。 PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 InOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 PostOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。 // 操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。 LeafNodes(p) // 初始条件:二叉树T存在。 // 操作结果:返回T的叶子结点数。全国计算机等级考试二级公共基础之树与二叉树1
二叉树的基本 操作
实验三 二叉树的基本操作实现及其应用
实验三二叉树的基本操作
二叉树的基本参数计算
数据结构——二叉树基本操作源代码
二叉树课程设计
数据结构实验三——二叉树基本操作及运算实验报告
实验10 二叉树的基本操作
二叉树运算实验报告
二叉树
二叉树基本操作经典实例
二叉树的基本操作及实现.cpp
树和二叉树的基本知识
二叉树的基本 操作
东北大学计算机初试历年二叉树算法题目及解答
C++二叉树的创建与遍历实验报告
二叉树定价模型
二叉树定价模型知识讲解
二叉树的基本操作实验报告
相关主题
文本预览