二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
1．顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图5-5(a)是一棵完全二叉树，图5-5（b）给出的图5-5(a)所示的完全二叉树的顺序存储结构。
(a) 一棵完全二叉树(b) 顺序存储结构图5-5 完全二叉树的顺序存储示意图
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不
宜用顺序存储结构。最坏的情况是右单支树，如图5-7 所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。
(a) 一棵二叉树(b) 改造后的完全二叉树
(c) 改造后完全二叉树顺序存储状态
图5-6 一般二叉树及其顺序存储示意图
(a) 一棵右单支二叉树(b) 改造后的右单支树对应的完全二叉树
(c) 单支树改造后完全二叉树的顺序存储状态
图5-7 右单支二叉树及其顺序存储示意图
结构5-1二叉树的顺序存储
#define Maxsize 100 //假设一维数组最多存放100个元素
typedef char Datatype; //假设二叉树元素的数据类型为字符
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;
2．链式存储结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图5-8所示。
(a) 一棵二叉树(b) 二叉链表存储结构
图5-8 二叉树的二叉链表表示示意图为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：
这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。
图5-9给出了图5-8 (a)所示的一棵二叉树的三叉链表表示。
图5-9二叉树的三叉链表表示示意图
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。
结构5-2二叉树的链式存储
#define datatype char //定义二叉树元素的数据类型为字符typedef struct node //定义结点由数据域，左右指针组成{ Datatype data;
struct node *lchild,*rchild;
}Bitree;
二叉树的存储表示 1二叉树的顺序存储表示 2二叉树的链式存储表示 3三叉链表 1二叉树的顺序存储表示 二叉树的顺序存储结构的定义如下： #define MAXSIZE = 100； //暂定二叉树中节点数的最大值为100 Typedef struct { ElemType *data ； //存储空间基址（初始化时分配空间） Int nodeNum ； //二叉树中节点数 }SqBiTree ； //二叉树的顺序存储结构 为了能在存储结构中反映出节点之间的逻辑关系，必须将二叉树中节点依照一定规律安排在这组存储单元中。对于完全二叉树，只要从根起按层序存储即可。 显然，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为2k -1的一维数组。 二叉树的顺序存储图如图1所示： 2 6 320 116 5402 106 543216 （a ）满二叉树（b ）一般二叉树 图1 顺序存储
2二叉树的链式存储表示 二叉树有不同的链式结构，其中最常用的是二叉链表与三叉链表。二叉链表的结点形式如表1所示： 表1链式存储 date域：称为数据域，用于存储二叉树结点中的数据元素， 1child域：称为左孩子指针域，用于存放指向本结点左孩子的指针(左指针)。 rchild域：称为右孩子指针域，用于存放指向本结点右孩子的指针(右指针)二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。 根指针：每个二叉链表还必须有一个指向根结点的指针。根指针具有标识二叉链表的作用，对二叉链表的访问能从根指针开始。 图2中（a）（b）表示一棵二叉树及其二叉链表。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。 二叉链表的类型定义如下： Typedef struct btnode *bitreptr； Struct btnode { Datatype data； Bitreptr lchild,rchild； }； Bitreptr root； 若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的的左右孩子，其余的n+1个指针域为NULL。 在二叉链表这种存储结构上，二叉树的多数基本运算如求根,求左、右孩子等很容易实现。但求双亲运算PARENT(BT,X)的实现却比较麻烦，而且其时间性能不高。
第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
一、实验名称：二叉树两种存储结构的应用 二、实验目的和要求： 1．掌握二叉树的遍历思想及二叉树的存储实现。 2．掌握二叉树的基本操作：建立二叉树、二叉树的遍历 3．选择一种形式完成二叉树的显示 4．掌握二叉树的常见算法的程序实现 5．实验报告中要写出测试数据、错误分析以及收获 三、上机实验内容一：二叉树的建立及相关算法的实现 1．完成的功能包括如下几点： ①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。 分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在结点则输入@ ②显示二叉树 ③求二叉树的高度及二叉树的叶子个数等等 ④在主函数中设计一个简单的菜单，分别调试上述算法 四、上机实验内容二：哈夫曼编码/译码系统 1．要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。 2．设计分析 在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信息的翻译。要求设置发送者和接收者两个功能。 发送者的功能包括： ①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出现的次数（频率）；③根据字符的种类数和各字符出现的次数建立哈夫曼树；④利用以上哈夫曼树求出各字符的哈夫曼编码；⑤将字符信息转换成对应的编码信息进行传送。 接收者的功能包括： ①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信息还原成发送前的字符信息。 3．结点的类型定义 ①哈夫曼树的存储结构类型定义为：
typedef struct { char data; /*编码对应的字符*/ int weight; /*结点的权值*/ int lchild,rchild,parent;/*左右孩子及双亲的下标*/ }HTNode; ②哈夫曼编码的存储结构类型定义为： typedef struct { char bits[N]; /*存放哈夫曼编码的字符数组*/ int start; /*记录编码的起始位置，因为每种字符的编码长度不同*/ }HCode; 说明：只占用2个课内学时，学生可利用开放实验室利用课余时间完成本次实验内容。
第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题
1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 重庆邮电大学 课程设计实验报告 班级：1301416 姓名：陈昊 学号：2014214156 指导老师：夏晨洋 课程名称：数据结构 实验时间：2015年10月26日-2015年11月2日实验地点：数字图书馆负一楼B132 实验五树的存储与遍历操作 一、实验目的 1．理解二叉树的逻辑结构； 2．理解二叉树的存储结构特点，掌握二叉树的存储分配要点； 3．掌握二叉树的基本操作及递归实现，深刻领会二叉树遍历操作的非递归实现。 二、主要数据结构描述 class BiTree { public: BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode #include { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]==VirNode&&BT[2*i+1]==VirNode) n++; for(;i<=BT[0];i++) if(BT[i]!=VirNode) n++; return n; } int countn1(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&(BT[2*i]==VirNode&&BT[2*i+1]!=VirNode|| BT[2*i]!=VirNode&&BT[2*i+1]==VirNode)) n++; return n; } int countn2(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]!=VirNode&&BT[2*i+1]!=VirNode) n++; return n; } //主函数 void main() { SqBitTree T; int n; crebitree(T,5); levellist(T); printf("High=%d\n",high(T)); levellist(T); printf("n2=%d\n",countn2(T)); getch(); } 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 用二叉树实现存储信息用二叉树 实现存储信息.txt老子忽悠孩子叫 教育，孩子忽悠老子叫欺骗，互 相忽悠叫代沟。▲ 男人这花花世 界，我要用什么颜色来吸引你。 #in elude };//学生结构体 struct treeitem { struct treeitem *lchild; struct treeitem *rchild; struct _stude nt mystude nt; };//二叉树结构体 class Stude nt { public: Stude nt(void); ~Stude nt(void); void Create(struct treeitem *Tnode );// 创建 void Find(struct treeitem *tree,int i);// 查看节点是否存在 void Search(Stude nt &tree);〃查询节点 void Chan ge(struct treeitem *Tno de,i nt i);// 修改 void DeleteNode(struct treeitem *tree,int i);//删除 Stude nt *n ode;// 根节点 private: bool tj; int i_id,i_age,i_math; char c_ch; }; .cpp=== Stude nt::Stude nt(void) { tj=false; } Student::~Stude nt(void) { } void Stude nt::Create(struct treeitem *Tnode)// 创建 1 { ci n>>i」d,c_ch,i_age,i_math; if(id!=null&&ch!="&&age!=null&&math!=n 实验五二叉树的存储表示和基本操作 实验内容 1. 二叉树的二叉链表的存储结构 —————二叉树的二叉链表存储表示———————— typedef struct node { ElemType data; /*数据元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ } BTNode; 2. 二叉树的基本操作 （1）创建操作：创建一棵二叉树。 （2）查找操作：查找二叉树中值为x的结点。 （3）查找左孩子操作：查找二叉树中值为x的结点的左孩子。 （4）查找右孩子操作：查找二叉树中值为x的结点的右孩子。 （5）求深度操作：求二叉树的深度。 （6）求宽度操作：求二叉树的宽度。 （7）求结点个数操作：求二叉树的结点个数。 （8）求叶子结点个数操作：求二叉树的叶子结点个数。 （9）输出操作：以括号表示法输出二叉树。 3. 链式队列操作实现的步骤 （1）实现将链式队列的存储结构和基本操作程序代码。 （2）实现main主函数。 4.程序代码完整清单 #include 1 完全二叉树的顺序存储 #include 习题六树和二叉树 一、单项选择题 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 , 它的前序遍历是 实验课程名称数据结构与算法 实验项目名称二叉树的存储与实现 年级 08 级 专业数学类 学生姓名 学号 理学院 实验时间：年月日 学生实验室守则 一、按教学安排准时到实验室上实验课，不得迟到、早退和旷课。 二、进入实验室必须遵守实验室的各项规章制度，保持室内安静、整洁，不准在室内打闹、喧哗、吸烟、吃食物、随地吐痰、乱扔杂物，不准做与实验内容无关的事，非实验用品一律不准带进实验室。 三、实验前必须做好预习（或按要求写好预习报告），未做预习者不准参加实验。 四、实验必须服从教师的安排和指导，认真按规程操作，未经教师允许不得擅自动用仪器设备，特别是与本实验无关的仪器设备和设施，如擅自动用或违反操作规程造成损坏，应按规定赔偿，严重者给予纪律处分。 五、实验中要节约水、电、气及其它消耗材料。 六、细心观察、如实记录实验现象和结果，不得抄袭或随意更改原始记录和数据，不得擅离操作岗位和干扰他人实验。 七、使用易燃、易爆、腐蚀性、有毒有害物品或接触带电设备进行实验，应特别注意规范操作，注意防护；若发生意外，要保持冷静，并及时向指导教师和管理人员报告，不得自行处理。仪器设备发生故障和损坏，应立即停止实验，并主动向指导教师报告，不得自行拆卸查看和拼装。 八、实验完毕，应清理好实验仪器设备并放回原位，清扫好实验现场，经指导教师检查认可并将实验记录交指导教师检查签字后方可离去。 九、无故不参加实验者，应写出检查，提出申请并缴纳相应的实验费及材料消耗费，经批准后，方可补做。 十、自选实验，应事先预约，拟订出实验方案，经实验室主任同意后，在指导教师或实验技术人员的指导下进行。 十一、实验室内一切物品未经允许严禁带出室外，确需带出，必须经过批准并办理手续。 学生所在学院：理学院专业：数学类班级：08级 实验6：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算 a) 统计叶子结点的个数。 b) 求二叉树的深度。 2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。 3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。 4、 自动完成求值运算和输出结果。 四、实验环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； - + / a * b - e f C d 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、功能分析 存储结构 typedef union{ int Operator; // 操作符 float Operand; // 操作数 }Int_Float; //表达式树 typedef struct BinaryTreeNode{ Int_Float Data; //数据域 int IsOperator; //判断是不是操作数的标志位 struct BinaryTreeNode *RChild;//左子树 struct BinaryTreeNode *LChild;//右子树 }BiTreeNode, *lpBiTreeNode; //栈的定义 typedef struct { lpBiTreeNode *base; lpBiTreeNode *top; int stacksize; }SqStack; 函数一览表 lpBiTreeNode GetTop( SqStack s );//取栈顶结点函数 int IsEmpty( SqStack s );//判空函数 int InitStack( SqStack &s );//初始化栈函数 int Pop( SqStack &s, lpBiTreeNode &e );//出栈函数 int Push( SqStack &s, lpBiTreeNode e );//入栈函数 int In( int c, int* op );// 判断c是否在op中 int Precede( int theta1, int theta2 );//比较运算符号的优先级 int isNum( int c );//判断是不是数 int GetInput(Int_Float *Result);//读入输入的数 lpBiTreeNode CreateBiTree();//创建二叉树 bool calculate(lpBiTreeNode Root, float *result);//计算二叉树化表达式的值int getLeafNum(lpBiTreeNode Root);//计算二叉树的叶子结点数 第6章树和二叉树 6.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.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结 点的左、右孩子指针，dada为结点的数据域。请完成下列各题： 1）画出二叉树bt的逻辑结构 2）写出按先序、中序、后序遍历二叉树所得到的结点序列 3）画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构，如图所示， 1）画出二叉树表示 2）写出前序遍历，中序遍历和后序遍历的结果 3）写出结点值c的父结点，其左、右孩子。 4）画出将此二叉树还原成森林的图 3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、 2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点 的权的次序构造），求出每个字符的Huffman编码。 5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。 学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990 学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 } 运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图： 实验名称:二叉树链式存储结构 实验类型：验证性实验 班级：20102111 学号：2010211102 姓名： 实验日期：2012.5.27 1.问题描述 二叉链表的C语言描述； 基本运算的算法——建立二叉链表、先序遍历二叉树、中序遍历二叉树、后序遍历二叉树、后序遍历求二叉树深度。 2.数据结构设计 typedef struct Bitnode { char data; struct Bitnode *lchild,*rchild; }Bitnode,*Bitree; 3.算法设计 建立二叉链表：void createBitree(Bitree &T) { char ch; if((ch=getchar())=='#') T=NULL; else{T=(Bitnode*)malloc(sizeof(Bitnode)); T->data=ch; createBitree(T->lchild); createBitree(T->rchild); } } 先序遍历二叉树：void preorder(Bitree &T) { if(T!=NULL) {printf("%c",T->data); preorder(T->lchild); preorder(T->rchild);}} 中序遍历二叉树：void inorder(Bitree &T) {if(T!=NULL) { inorder(T->lchild); printf("%c",T->data); inorder(T->rchild); } 后序遍历二叉树：void postorder(Bitree &T) { if(T!=NULL) {postorder(T->lchild); postorder(T->rchild); printf("%c",T->data); } }//后序遍历 后序遍历求二叉树深度：int Depth(Bitree &T) {//返回深度 int d,dl,dr; if(!T) d=0; else {dl=Depth(T->lchild); dr=Depth(T->rchild); d=1+(dl>dr?dl:dr) ; } return d; } 4.运行、测试与分析 运行程序，显示菜单， （1）如图1.1: 图1.1 （2）结果图1.2： 图1.2树的存储与遍历操作
二叉树的顺序存储结构
数据结构树和二叉树习题
用二叉树实现存储信息
实验五--二叉树的存储结构和基本操作
完全二叉树的顺序存储
数据结构第六章树和二叉树习题及答案
二叉树的存储与实现
实验二叉树及其应用(严选材料)
数据结构—— 树和二叉树知识点归纳
数据结构习题 树 数据机构c语言版
数据结构实验报告之树与二叉树
二叉树链式存储结构 第六章实验报告
相关主题
文本预览