第5章树和二叉树
5.1 知识点概述
树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。
1、树的定义
树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中：
（1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。
2、树的基本存储结构
（1）双亲表示法
由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的
存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。
（2）孩子表示法
将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单
链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。
（3）双亲孩子表示法
双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。
（4）孩子兄弟表示法
这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。
3、二叉树的定义
二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
4、满二叉树
定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。
5、完全二叉树
定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
6、二叉树的性质
性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。
性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有： n0＝n2＋1
性质4 具有n个结点的完全二叉树的深度k为[log2n]+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：
1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。
2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i 的结点无左孩子。
3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。
7、二叉树的存储结构
顺序存储结构和链式存储结构。
（1）顺序存储结构
所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。
（2）链式存储结构
所谓二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。二叉树的链式存储结构通常有下面两种形式。
1）二叉链表存储
链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
2）三叉链表存储
每个结点由四个域组成， data、lchild、rchild和parent
其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。
8、二叉树的遍历
二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。
9、树和二叉树的基本操作：
初始化、求根函数、求双亲函数、求孩子结点函数、插入子树操作、删除子树操作、遍历操作等。
10、线索二叉树
为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。
11、哈夫曼树
（1）哈夫曼树的基本概念
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造
的具有最小带权路径长度的二叉树。
构造哈夫曼树基本思想是：
1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；
2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F 中；
4）重复2）3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
5.2 二叉树的基本操作及应用
一、实验目的
1、掌握二叉树的存储结构
2、掌握二叉树的遍历操作的实现方法
3、掌握递归方法能够编写相应的程序解决二叉树应用
4、掌握建立Huffman树及求Huffman编码的操作，加深对二叉树应用的理解
二、实验内容
（一）验证实验
1、已知二叉树用下面的顺序结构存储
＃define Max=20
struct nodes
{char data; //存结点值
int lc,rc; //存左右孩子下标，0表示无左、右孩子
}A[Max];
2、写出前序、中序和后序遍历该二叉树的算法。
实验程序：
前序遍历
#define Max 10
struct nodes
{char data;
int lc,rc;
}A[Max]={{'0',0,0},{'A',2,3},{'B',4,5},{'C',0,6},{'D',0,0},{'E',0,7},{'F',8,9},{'G',0, 0},{'H',0,0},{'I',0,0}};
void preorder(int root)
{ printf("%c",A[root].data);
if (A[root].lc!=0)
preorder(A[root].lc);
if (A[root].rc!=0)
preorder(A[root].rc);}
}
void main()
{int root=1;
printf("preorder\n");
preorder(root);
}
中序遍历
#define Max 10
struct nodes
{char data;
int lc,rc;
}A[Max]={{'0',0,0},{'A',2,3},{'B',4,5},{'C',0,6},{'D',0,0},{'E',0,7},{'F',8,9},{'G',0, 0},{'H',0,0},{'I',0,0}};
void inorder(int root)
{if (A[root].lc!=0)
inorder(A[root].lc);
printf("%c",A[root].data);
if (A[root].rc!=0)
inorder(A[root].rc);}
void main()
{int root=1;
printf("inorder\n");
inorder(root);
}
后序遍历
#define Max 10
struct nodes
{char data;
int lc,rc;
}A[Max]={{'0',0,0},{'A',2,3},{'B',4,5},{'C',0,6},{'D',0,0},{'E',0,7},{'F',8,9},{'G',0, 0},{'H',0,0},{'I',0,0}};
void postorder(int root)
{ if (A[root].lc!=0)
postorder(A[root].lc);
if (A[root].rc!=0)
postorder(A[root].rc);
printf("%c",A[root].data);
}
void main()
{int root=1;
printf("postorder\n");
postorder(root);
}
（二）设计实验
1、建立表达式二叉树并计算其结果
实验程序：
#include "stdio.h"
#include "stdlib.h"
int GetValue(int oper,int oper1,int oper2) ;
typedef char TElemType; //定义元素类型为字符型
typedef struct BTNode //定义二叉树的二叉链表结构
{TElemType data; //存放结点的数据，字符类型
struct BTNode *lchild, *rchild; //存放左、右子树的指针
}BTNode;
BTNode * CreateBTree(char *nodelist,int i)
{
BTNode *newnode; //声明新结点指针
if(nodelist[i]==0||i>7)//递归的终止条件
return NULL;
else
{
//为新结点分配内存空间
newnode=(BTNode *)malloc(sizeof(BTNode));
//将字符存入新结点
newnode->data=nodelist[i];
//递归建立左子树
newnode->lchild=CreateBTree(nodelist,2*i);
//递归建立右子树
newnode->rchild=CreateBTree(nodelist,2*i+1);
return newnode;//返回复制树的位置
}
}
void PreTraverse(BTNode *bt)
{
if(bt!=NULL) //遍历的终止条件
{
printf("%c",bt->data); //打印结点内容
PreTraverse(bt->lchild); //递归遍历左子树
PreTraverse(bt->rchild); //递归遍历右子树
}
}
void InTraverse(BTNode * bt)
{
if(bt!=NULL) //遍历的终止条件
{
InTraverse(bt->lchild); //递归遍历左子树
printf("%c",bt->data); //打印结点内容
InTraverse(bt->rchild); //递归遍历右子树
}
}
void PostTraverse(BTNode * bt)
{
if(bt!=NULL) //遍历的终止条件
{
PostTraverse(bt->lchild); //递归遍历左子树
PostTraverse(bt->rchild); //递归遍历右子树
printf("%c",bt->data); //打印结点内容
}
}
int Calculate(BTNode * bt)
{
int oper1=0; //前操作数
int oper2=0; //后操作数
if(bt->lchild==NULL && bt->rchild==NULL)
return bt->data-48;
else
{
oper1=Calculate(bt->lchild); //左子树
oper2=Calculate(bt->rchild); //右子树
return (GetValue(bt->data,oper1,oper2));
}
}
int GetValue(int oper,int oper1,int oper2)
{
int result=0;
switch((char)oper)
{
case '*': result=oper1*oper2;return(result);
case '/':result=oper1/oper2;return(result);
case '+':result=oper1+oper2;return(result);
case '-':result=oper1-oper2;return(result);
}
}
void main()
{
BTNode * root=NULL; //声明表达式二叉树指针int result; //声明结算结果变量//声明二叉树数组结点数据//
char nodelist[8]={'-','+','*','/','4','8','6','2'};
root=CreateBTree(nodelist,1); //建立表达式二叉树
//输出前缀表达式
printf("\n 前缀表达式PreTraverse expression:[");
PreTraverse(root);
printf("]\n");
//输出中缀表达式
printf("\n InTraverse expression:[");
InTraverse(root);
printf("]\n");
//输出后缀表达式
printf("\n PostTraverse expression:[");
PostTraverse(root);
printf("]\n");
//计算表达式结果
result=Calculate(root);
printf("\n calculate result is [%2d]\n",result);
getchar();
}
2、根据Huffman编码原理，编写一个在用户输入结点权重的基础上建立的Huffman编码程序。
程序设计思路：构造一棵Huffman树，由此得到的二进制前缀便为Huffman编码
由于Huffman树没有度为1的结点，则一棵有n 个叶子结点的Huffman树共有2n-1个结点，设计一个结构数组，存储2n-1个结点的值，包括权重、父结点、左结点和右结点等
参考程序：
#include
#define MAX 21
typedef struct{
char data;
int weight;
int parent;
int left;
int right;
}HuffNode;
typedef struct{
char cd[MAX];
int start;
}HuffCode;
void main()
{
HuffNode ht[2*MAX];
HuffCode hcd[MAX],d;
int i,k,f,j,r,n=0,c,m1,m2;
printf("请输入元素个数(1->%d):",MAX-1);
scanf("%d",&n);
if(n>MAX-1||n<1)
return;
for(i=0;I printf("第%d个元素=>\n\t结点值:",i+1); scanf("%c",&ht[i].data); printf("\t权重:"); scanf("%d",&ht[i].weight); } for(i=0;i<2*n+1;i++) ht[i].parent=ht[i].left=ht[i].right=0; for(i=n;i<2*n-1;i++){ m1=m2=0x7fff; j=r=0; for(k=0;k if(ht[k].parent==0) if(ht[k].weight m2=m1; r=j; m1=ht[k].weight; j=k; } else if(ht[k].weight m2=ht[k].weight; r=k; } ht[j].parent=i; ht[r].parent=i; ht[i].weight=ht[j].weight+ht[r].weight; ht[i].left=j; ht[i].right=r; } for(i=0;I d.start=n; c=i; f=ht[i].parent; while(f!=0){ if(ht[f].left==c) d.cd[--d.start]='0'; else d.cd[--d.start]='1'; c=f; f=ht[f].parent; } hcd[i]=d; } printf("输出Huffman编码:\n"); for(i=0;i printf("%c:",ht[i].data); for(k=hcd[i].start;k printf("%c",hcd[i].cd[k]); printf("\n"); }} 实验结果：元素个数：6 第一个元素a：权重：7 第二个元素b：权重：9 第三个元素c：权重：12 第四个元素d：权重：22 第五个元素e：权重：23 第六个元素f：权重：27 输出Huffman编码： a:1110 b:1111 c:110 d:00 e:01 f:10 第六章树和二叉树 一．选择题 1. 以下说法错误的是。 A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种"分支层次"结构 2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。 图6-2 4 棵二叉树 3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。 A. t->left == NULL B. t->ltag==1 C. t->ltag==1 且t->left==NULL D .以上都不对 4. 以下说法错误的是。 A.二叉树可以是空集 B.二叉树的任一结点最多有两棵子树 C.二叉树不是一种树 D.二叉树中任一结点的两棵子树有次序之分 5. 以下说法错误的是。 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 6. 如图6-3所示的4 棵二叉树，是平衡二叉树。 图6-3 4 棵二叉树 7. 如图6-4所示二叉树的中序遍历序列是。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6-4 1 棵二叉树 8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。 A. acbed B. decab C. deabc D. cedba 9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。 A. 前序 B.中序 C. 后序 D. 层次序 10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。 A.42 B.40 C.21 D.20 12. 一棵二叉树如图6-5所示，其后序遍历的序列为。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 目录 摘要 (1) ABSTRACT (2) 第一章绪论 (3) 1.1 背景介绍 (3) 1.2 本文的主题 (4) 第二章预备知识 (5) 2.1 期权 (5) 2.2二叉树方法 (6) 2.2.1 方法概述 (6) 2.2.2 二叉树方法的优点和缺点 (9) 2.2.3 风险中性定价 (9) 2.3 Black-Scholes 期权定价模型 (11) 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 第三章本论 (14) 3.1期权定价的二叉树模型 (14) ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 3.2 例子模拟计算和结果分析 (18) 3.3 模型改进——三叉树 (19) 第四章结论...................................... 错误!未定义书签。谢辞及参考文献 (23) 谢辞 (23) 参考文献 (23) 附录 (25) 计算过程中涉及算法 (25) 摘要 Black-Scholes 期权定价模型为期权定价尤其是欧式期权定价提供了良好的解析结果，而Black-Scholes 公式是此模型的核心，但是此公式并不能很好地求解出在很多衍生模型例如亚式期权以及美式期权中的解析解。二叉树方法作为一种数值方法，同时也是图论中一种重要方法，应用于期权定价问题中，它有了更特别的演变。本文利用二叉树方法计算期权定价的数值解，用二叉树方法迭代多次，求出较为准确的期权价格。通过B-S公式得出的结果与二叉树方法得到的结论对比，分析二叉树方法模拟的优点和缺点。同时，我们还要研究二叉树模拟的步数与预测结果和精度间的关系，从而更加深入了解二叉树方法。然而，我们在模型中设立了许多条件，这些都使模型离真实情况越来越远，我们必须不断发展模型，完善模型。三叉树方法正是二叉树方法的合适补充。 关键词：二叉树方法，Black-Scholes 模型，风险中性定价 第六章树和二叉树试题 一、单项选择题 1.树中所有结点的度等于所有结点数加（）。 A. 0 B. 1 C. -1 D. 2 2.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. -1 4.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A. n B. n-1 C. n+1 D. 2*n 5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等 于0而小于等于树的高度），最多具有（）个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不 小于（）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。假定空树 的高度为-1。 A. 5 B. 6 C. 7 D. 8 8.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。假 定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1 9.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号 为（）。假定根结点的编号为0 A. 2i B. 2i-1 C. 2i+1 D. 2i+2 10.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结 点，其双亲结点的编号为（）。 A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 11.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（） 结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙 12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。 A. 1 B. 2 C. 3 D. 4 13.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则 该二叉树的高度为（）。假定根结点的高度为0。 A. 3 B. 4 C. 5 D. 6 二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。 3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。 习题6树和二叉树 说明： 本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。 6.1单项选择题 1. 由于二叉树屮每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B.错误 2. 假定在一棵二叉树屮，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B_个。 A. 15 B. 16 C. 17 D. 47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。 A. 3 B.4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。 A.5 B.6 C. 30 D. 32 5. 深度为5的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为 B 。 A. 2h B. 2h-l C. 2h+l D. h+l 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h,则_A_。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -l 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如杲某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后 序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确 B.错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha 12. 在一非空二叉树的中序遍历序列中, A.只有右子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B_。 14. 一棵二叉树如图6.2所示，其中序遍历的序列为 B 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh C. bdgaechf D. gdbehfca 根结点的右边_A_。 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6」 长春建筑学院《数据结构》课程设计（论文） 基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation 年级: 学号: 姓名: 专业: 指导老师: 二零一三年十二月 摘要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。 二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。 本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。 关键词：二叉树；左子树；右子树 习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是 第5章树和二叉树 一．选择题 （1）由3 个结点可以构造出多少种不同的二叉树（ D ） A．2 B．3 C．4 D．5 （2）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B． 500 C．254 D．501 （3）一个具有1025个结点的二叉树的高h为（）。 A．11 B．10 C．11至1025之间 D．10至1024之间 （4）深度为h的满m叉树的第k层有（）个结点。(1= 第六章 树和二叉树 一、选择题 1．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ B ） A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ D ） A ．5 B ．6 C ．7 D ．8 4. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 5. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A ．9 B ．11 C ．15 D ．不确定 7．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ） A ． 250 B ． 500 C ．254 D ．505 E ．以上答案都不对 9. 有关二叉树下列说法正确的是（ B ） A ．二叉树的度为2 B ．一棵二叉树的度可以小于2 C ．二叉树中至少有一个结点的度为2 D ．二叉树中任何一个结点的度都为2 10．二叉树的第I 层上最多含有结点数为（ C ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 11. 一个具有1025个结点的二叉树的高h 为（ C ） A ．11 B ．10 C ．11至1025之间 D ．10至1024之间 12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 13. 一棵树高为K 的完全二叉树至少有（ C ）个结点 A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2 k 14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历 实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 15．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ B ） 一、选择题 1、设T是一棵树，T’是对应于x的二叉树，则T的先根次序遍历和T’的（）次序遍历相同。 A、先根 B、中根 C、后根 D、以上都不是 2、 3、若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（）。 A、acbed B、decab C、deabc D、cedba 4、具有35个结点的完全二叉树的深度为（） A、5 B、6 C、7 D、8 5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（） A、98 B、99 C、50 D、48 6、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无左孩子 7、二叉树在线索化后，仍不能有效求解的问题是（） A、先根线索二叉树中求先根后继 B、中根线索二叉树中求中根后继 C、中根线索二叉树中求中根前驱 D、后根线索二叉树中求后根后继 8、在线索化二叉树中，t所指结点没有左子树的充足条件是（） A、t-lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 9、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（） A、2h B、2h-1 C、2h+1 D、h+1 10、深度为5的二叉树至多有（）个结点。 A、16 B、32 C、31 D、10 11、在一非空二叉树的中序遍历序列中，根结点的右边（） A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点 12、树最适合用来表示（） A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 13、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（） A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 14、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（） A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 15、线索二叉树是一种（）结构 A、逻辑 B、逻辑和存储 C、物理 D、线性 16、森林的后根遍历序列与其对应二叉树的（）遍历序列一致。 A、先根 B、后根 C、中根 D、不可能 二、填空题 1、由一棵二叉树后序序列和（中序）可唯一确定这棵二叉树。 2、含有n个结点的二叉树用二叉链表表示时，有（N+1）个空链域。 3、有m个叶子结点的哈夫曼树有（2*M-1）个结点。 习题五参考答案 备注: 红色字体标明的是与书本内容有改动的内容 一、选择题 1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。 A．先根 B. 中根 C. 后根 D. 层次 2．在哈夫曼树中，任何一个结点它的度都是（ C ）。 B．0或1 B. 1或2 C. 0或2 D. 0或1或2 3．对一棵深度为h的二叉树，其结点的个数最多为（ D ）。 A．2h B. 2h-1 C. 2h-1 D. 2h-1 4．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ）A．所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ）B．所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ） A．2 B. 3 C. 4 D. 5 7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。 A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA 8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ B ）。 A．ABCDEF B. ABDCEF C. ABCDFE D. ABDECF 9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ）A．2 B. 3 C. 4 D. 5 10．在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。 A．n-1 B. n C. n+1 D. 0 二、填空题 1.在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，……，度为m 的结点有n m个，则这棵树中的叶结点的个数为1+n2+2n3+3n4+…+(m-1)n m。 2.一棵具有n个结点的二叉树，其深度最多为 n ，最少为 [log2n]+1 。 3.一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。 4.以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。 5.有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。 第6章树和二叉树 一、基础知识题 1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 [解答]二叉树的叶结点有⑥、⑧、⑨。分支结点有①、 ②、③、④、⑤、⑦。结点①的层次为0；结点②、 ③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、 ⑧的层次为3；结点⑨的层次为4。 2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。 [解答] （1）顺序表示 ①②③④⑤⑥⑦ ⑧⑨ （2）二叉链表表示 3．在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ [解答] 结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。 4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 [解答] 具有3个结点的树具有3个结点的二叉树 5．如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。 [解答] 总结点数n=n0+n1+n2+…+n m 总分支数e=n-1= n0+n1+n2+…+n m-1 =m×n m+(m-1)×n m-1+…+2×n2+n1 则有 n 0=∑=+-m i i n i 2 1))1(( 6．试分别找出满足以下条件的所有二叉树： （1） 二叉树的前序序列与中序序列相同； （2） 二叉树的中序序列与后序序列相同； （3） 二叉树的前序序列与后序序列相同。 [解答] （1） 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； （2） 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； （3） 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 7．填空题 （1）对于一棵具有n 个结点的树，该树中所有结点的度数之和为 n-1 。 （2）假定一棵三叉树的结点个数为50，则它的最小高度为 4 ，最大高度为 49 。 （3）一棵高度为h 的四叉树中，最多含有 (4h+1-1)/3 结点。 （4）在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6 个。 （5）一棵高度为5的满二叉树中的结点数为 63 个，一棵高度为3的满四叉树中的结点数为 85 个。 （6）在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有 6 个。 （7）对于一棵含有40个结点的理想平衡树，它的高度为 5 。 （8）若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一堆数组a 中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为2×i+1 ，右子女结点为 2×i+2 ，双亲结点（i ≥1）为??2/)1(-i 。 9．n 个结点可构造出多少种不同形态的二叉树？若有3个数据1，2，3，输入它们构 造出来的中序遍历结果都为1，2，3的不同二叉树有哪些？ [解答] 有n n C 2/ (n+1)种。当n=3时，中序遍历都为1，2，3的不同二叉树有5种： 第六章答案 6． 1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】 具有3个结点的树具有3个结点的二叉树 6.3已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k 的结点，则该树中有多少个叶子结点？ 【解答】设树中结点总数为n,则n=n0 + n1 + …… + n k 树中分支数目为B,则B=n1 + 2n2 + 3n3+ …… + kn k 因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 即n0 + n1 + …… + n k = n1 + 2n2 + 3n3+ …… + kn k + 1 由上式可得叶子结点数为：n0 = n2 + 2n3+ …… + (k-1)n k + 1 6.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1 所以n2=n0 –1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=99 6.6 试分别找出满足以下条件的所有二叉树: (1) 前序序列与中序序列相同; (2) 中序序列与后序序列相同; (3) 前序序列与后序序列相同。 【解答】 (1) 前序与中序相同：空树或缺左子树的单支树； (2) 中序与后序相同：空树或缺右子树的单支树； (3) 前序与后序相同：空树或只有根结点的二叉树。 6.9 假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 【解答】 构造哈夫曼树如下： 第6章树和二叉树自测题 一、填空题 1．树是一种________结构。在树结构中，________结点没有直接前趋。（层次，根） 2．一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。（子孙结点，祖先） 3．二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。（空、只有根结点、根和根的左子树、根和根的右子树、根和根的左右子树） 4．树在计算机内的表示方式有_______、_______、_________。（双亲表示法、孩子表示法、双亲孩子表示法） 5．对任何二叉树，若度为2的节点数为n 2，则叶子数n =______。（n =n 2 +1） 6. 高度为k(k>=1)的二叉树至多有______个结点。(2k-1) 7. 二叉树第i(i>=1)层上至多有______个结点。(2i-1) 8. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。（最大值，完全二叉树） 9．具有n个结点的完全二叉树的高度为______。（log 2 n） 10. 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X 有： (1)若i=1，则结点X是______；若i〉1，则X的双亲PARENT(X)的编号为______。(根 结点，[i/2]) (2) 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为 ______。（左孩子，右孩子，2i） (3)若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。（右 孩子，2i+1） 11. 二叉树通常有______存储结构和______存储结构两类存储结构。(顺序，链接) 12．具有n个结点的二叉链表中，一共有________个指针域，其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。(2n，n-1，n+1) 13. 一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。(访问根结点、遍历左子树、遍历右子树) 14. 若以N、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。(NLR、LNR、LRN、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历) 15. 在二叉链表中，指针p所指结点为叶结点的条件是______。(结点的左右孩子域均为空指针) 16. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶结点。（12） 17．设根结点的层数为１，具有n个结点的二叉树的最大高度是______。(n) 18. 已知二叉树前序序列为ABDEGCF，中序序列为DBGEACF，则后序序列是____。(DGEBFCA) 19. 若一个二叉树的叶结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。(先(前)序) 20. 先根次序遍历树(森林)等同于按______遍历对应的二叉树；后根次序遍历树(森林)等同 封皮 （按学校要求手工填写） 成绩评定表 课程设计任务书 摘要 树结构在客观世界中广泛存在，如族谱、各种社会组织机构等都可以用树形结构来表示；树结构在计算机中应用也很广泛，如文件夹；其中二叉树结构是比较常用的一种数据结构，简单来说每个结点最多有两个孩子。本文采用C++语言来描述二叉树类模板的设计并实现其功能，并且采用VS2010应用程序来实现程序。 关键词：二叉树类模板；MFC 目录 1 需求分析 (1) 2 算法基本原理 (1) 3 类设计 (1) 4 基于控制台的应用程序 (2) 4.1类的接口设计 (2) 4.2类的实现 (3) 4.3主函数设计 (8) 4.4基于控制台的应用程序测试 (9) 5 基于MFC的应用程序 (10) 5.1基于MFC的应用程序设计 (10) 5.1.1 MFC程序界面设计 (11) 5.1.2 MFC程序代码设计 (13) 5.2基于MFC的应用程序测试 (17) 结论 (20) 参考文献 (21) 1需求分析 进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能: （1）采取顺序存储结构或链式存储结构实现二叉树的存储; （2）实现二叉树的建树; （3）实现二叉树的前序、中序、后序遍历； （4）能够求解二叉树的结点总数和叶子结点总数； （5）能够求解二叉树的高度； （6）将上述功能作为类的成员函数实现，编写主函数测试上述功能。 整个二叉树类模板程序中的存储采用的是链式存储结构。在整个二叉树类中所有数据成员和成员函数均采用公有方式，类中有一个二叉树结点的定义，有建立二叉树的成员函数，有先序、中序、后序遍历的成员函数，有求解结点数、叶子节点数、二叉树深度的成员函数，它的功能在类里定义一个调用各个成员函数的成员函数来实现对二叉树的操作，然后在主函数中通过对模板的实例化产生对象，用对象调用成员函数的方式实现预期功能。 2算法基本原理 一颗二叉树有许多个结点组成，每个结点有三个区域分别存有数据和它的左右孩子指针。 大体思路：先构造一棵二叉树，然后依次实现前序、中序、后序遍历，统计二叉树的结点总数，统计二叉树的叶子结点数，求出二叉树的高度这些功能。 在主函数中实例化char,int,float数据类型的类对象，然后根据类对象来实现功能。 3 类设计 第六章树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ B ） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 3.设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G 4.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ）A．5 B．6 C．7 D．8 5.在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ A ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 7. 树是结点的有限集合，它（ C )根结点，记为T。其余结点分成为m（m>0）个(A)的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的(C )。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(A)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（C）。供选择的答案： （1）(4) A.有0个或1个 B.有0个或多个 C.有且只有一个 D.有1个或1个以上 （2） A.互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A.权 B.维数 C.次数 D.序 （5） A.丰满树 B.查找树 C.平衡树 D.完全树 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ） A．9 B．11 C．15 D．不确定 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ C ）个 A．4 B．5 C．6 D．7 10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ D ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 11．具有10个叶结点的二叉树中有（ B）个度为2的结点， A．8 B．9 C．10 D．ll 12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ） A． 250 B．500 C．254 D．505 E．以上答案都不对 13.设给定权值总数有n个，其哈夫曼树的结点总数为( D ) A．不确定 B．2n C．2n+1 D．2n-1 14.有n个叶子的哈夫曼树的结点总数为（ D ）。 A．不确定 B．2n C．2n+1 D．2n-1 15．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（C ）。 第5章树和二叉树练习题答案 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.满二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.设一棵完全二叉树有700个结点，则共有350个叶子结点。 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。 7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按L R N次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B。 解：法1：先由已知条件画图，再后序遍历得到结果； 法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前 序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中， 根结点在最前面，是B；则后序遍历中B一定在最后面。 法3：递归计算。如B在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同 样处理，则问题得解。数据结构-6 树和二叉树
基于二叉树模型的期权定价
《数据结构》习题汇编06第六章树和二叉树试题
二叉树遍历方法技巧
习题6树和二叉树.docx
基于二叉树遍历系统设计与实现
数据结构第六章树和二叉树习题及答案
第5章--树和二叉树习题
第6章树和二叉树习题
数据结构第六章树和二叉树练习及答案
第5章 树与二叉树习题参考答案
第6-10章--树和二叉树--答案
第6章 树和二叉树答案
第6章树和二叉树自测题
二叉树类模板的设计与实现
第六章树和二叉树讲解
树和二叉树练习题答案
相关主题
文本预览