实验课程名称数据结构与算法
实验项目名称二叉树的存储与实现
年级 08 级
专业数学类
学生姓名
学号
理学院
实验时间：年月日
学生实验室守则
一、按教学安排准时到实验室上实验课，不得迟到、早退和旷课。
二、进入实验室必须遵守实验室的各项规章制度，保持室内安静、整洁，不准在室内打闹、喧哗、吸烟、吃食物、随地吐痰、乱扔杂物，不准做与实验内容无关的事，非实验用品一律不准带进实验室。
三、实验前必须做好预习（或按要求写好预习报告），未做预习者不准参加实验。
四、实验必须服从教师的安排和指导，认真按规程操作，未经教师允许不得擅自动用仪器设备，特别是与本实验无关的仪器设备和设施，如擅自动用或违反操作规程造成损坏，应按规定赔偿，严重者给予纪律处分。
五、实验中要节约水、电、气及其它消耗材料。
六、细心观察、如实记录实验现象和结果，不得抄袭或随意更改原始记录和数据，不得擅离操作岗位和干扰他人实验。
七、使用易燃、易爆、腐蚀性、有毒有害物品或接触带电设备进行实验，应特别注意规范操作，注意防护；若发生意外，要保持冷静，并及时向指导教师和管理人员报告，不得自行处理。仪器设备发生故障和损坏，应立即停止实验，并主动向指导教师报告，不得自行拆卸查看和拼装。
八、实验完毕，应清理好实验仪器设备并放回原位，清扫好实验现场，经指导教师检查认可并将实验记录交指导教师检查签字后方可离去。
九、无故不参加实验者，应写出检查，提出申请并缴纳相应的实验费及材料消耗费，经批准后，方可补做。
十、自选实验，应事先预约，拟订出实验方案，经实验室主任同意后，在指导教师或实验技术人员的指导下进行。
十一、实验室内一切物品未经允许严禁带出室外，确需带出，必须经过批准并办理手续。
学生所在学院：理学院专业：数学类班级：08级
二叉树的存储表示 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)的实现却比较麻烦，而且其时间性能不高。
1 完全二叉树的顺序存储 #include 一、实验名称：二叉树两种存储结构的应用 二、实验目的和要求： 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个课内学时，学生可利用开放实验室利用课余时间完成本次实验内容。 重庆邮电大学 课程设计实验报告 班级：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(); } 用二叉树实现存储信息用二叉树 实现存储信息.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 树 Content 树 1 二叉树2二叉树的遍历3 树和森林4堆和优先权队列5哈夫曼树及其应用 6 PART TWO 二叉树 ?二叉树的定义和性质 ?特殊二叉树 ?二叉树ADT与存储表示 ?二叉树的基本运算 二叉树ADT ADT BinaryTree{ 数据： 二叉树是结点的有限集合，它或者为空集合，或者由一个根和两棵子树构成，这两棵子树也是二叉树。运算： Create(bt)：构造一棵空二叉树bt。 NewNode(x,ln,rn)：创建一个新节点，该结点的值为x，ln和rn为该结点的左右孩子结点。 IsEmpty(bt)：若二叉树bt为空，则返回TRUE，否则返回FALSE。 ClearTree(bt)：清除二叉树bt中的所有结点，使之成为空二叉树。 Root(bt,x)：若二叉树bt非空，则获取根结点中的数据，并返回TRUE，否则返回FALSE。 MakeTree(bt,x,left,right)：构造一棵二叉树bt，根结点的值为x，left和right为该根结点的左右子树。 PreOrderTree(bt)：先序遍历二叉树bt。 InOrderTree(bt)：中序遍历二叉树bt。 PostOrderTree(bt)：后序遍历二叉树bt。 …… } 性质6: 对完全二叉树中的结点，按照从上到下、从左到右依次顺 序从0开始编号，则对于编号为i的节点而言，可知： ?若i=0，则该结点为根结点 ?若i>0，则该结点的父节点为?(i-1)/2? ?若2i+1＜n，则该结点的左孩子为2i+1，否则无左孩子 ?若2i+2＜n，则该结点的右孩子为2i+2，否则无右孩子 ?完全二叉树的顺序存储表示： ?结点按从上到下、从左到右，逐层顺序存储于一块连续的存储单元（即数组）?根结点存储在下标为0的位置，其他结点按上述性质中的编号规则依次顺序存储 实验课程名称数据结构与算法 实验项目名称二叉树的存储与实现 年级 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);//计算二叉树的叶子结点数 二叉树的存储分类 【摘要】本篇论文主要包含以下几个方面：二叉树的定义（在树的基础上），二叉树的性质，二叉树的存储结构，二叉树的遍历，由浅如深的介绍了二叉树的主要内容和结构特性、程序实现，同时文章多处用到图示的方法将抽象的计算方法变成教为直观的图解。在文章的最后还做了简单的总结，让人们对二叉树在生活中的应用及未来的发展有了一定的了解。 数据结构中二叉树对解决生活问题有着很大的帮助，因此，我们更应该深入的学习和了解二叉树的原理及实际的应用，而这当中又以二叉树的存储为重中之重，因此熟练掌握二叉树的存储分类为以后更方便的解决计算机相关问题做好铺垫，只有详细学习二叉树，了解二叉树的存储结构，才能更好的完成以后将要面临的任务。 【关键词】二叉树，二叉树的顺序存储，二叉树的链式存储 Abstract: This thesis mainly includes the following aspects: binary tree definition (on the base of the tree), the nature of the binary tree, the storage structure of the binary tree, binary tree traversal, achieved by such as the shallow deep introduced binary tree of the main content and structure characteristics, program. At the same time, the number of used calculation method of graphical representation of the abstract into teaching visual graphic. At the end of the article also made a simple summary, so that people on the two fork tree in the life of the application and the future development of a certain understanding. Binary tree data structure to solve the problem of life has a great help. Therefore, we should be more in-depth study and understanding of binary tree theory and practical application, and this and the binary tree storage as the most important, therefore master binary tree storage classification is more convenient for computer to solve the problems related to pave the way, only the detailed study of binary tree, understand the storage structure of the binary 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.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。 实验八 二 叉 树 的 性 质 与 链 式 存 储 结 构 指导老师：朱芳 学号：13011432 班级：13083414 姓名：张杭俊 【实验目的】 ●了解树结点和结点间关系的基本概念 ●了解树的结点访问的方法 ●掌握二叉树的链式存储结构 ●掌握二叉树结点的递归访问方法 ●掌握二叉树的遍历 【实验内容】 1.观察如图所示的二叉树并回答问题 1)写出前序、中序和后序的遍历序列 前序：ABDECFG 中序：DBEAFGC 后序：DEBGFCA 2)分别写出单支结点和叶子结点 单支结点：C、F 叶子结点：D、E、G 3)以“#”补充所有结点的空分支 4)写出补充空分支后二叉树的前序遍历序列 前序：ABD##E##CF#G### 5)在工程BiTree中添加二叉树的中序或后序遍历接口，并在主函数中将 第（4）小题的遍历序列写入main函数的数组A[]中进行验证结果如下： 2.验证题 函数调用和返回动作发生的顺序 调用顺序root结点返回顺序返回值 1 A 9 3 2 B 5 2 3 D 3 1 4 NULL 1 0 5 NULL 2 0 6 NULL 4 0 7 C 8 1 8 NULL 6 0 9 NULL 7 0 调试过程： 3.计算题 仿照第(2)题，在main函数中，定义数组A[]=“ABD##E##C#F##”;调用函数 CreateBTree_Pre(root,A)；根据A[]中的数据建立如图二叉树，调用并验证递归函数int BTreeDepth(BTNode *root)计算该二叉树深度过程 函数调用和返回动作发生的顺序 调用顺序root结点返回顺序返回值 1 A 13 3 2 B 7 2 3 D 3 1 4 NULL 1 0 5 NULL 2 0 6 E 6 1 7 NULL 4 0 8 NULL 5 0 9 C 12 2 10 NULL 8 0 11 F 11 1 12 NULL 9 0 13 NULL 10 0 调试过程： 4.二叉树的非递归遍历 数据结构实验报告 知识范畴：树 完成日期：2018年05月05日 实验题目：二叉树的基本算法一(二叉链表的建立、遍历以及生成完全二叉树顺序存储结构) 实验内容及要求： 设二叉树结点数据域为字符类型，从键盘输入先序递归遍历字符序列（用#字符表示NULL 指针域）建立二叉链表存储结构，然后输出其先、中、后序递归遍历结点访问次序以及层次遍历结点访问次序(层次遍历所需队列要求采用循环队列)； 建立该二叉树对应的完全二叉树顺序存储结构，输出完全二叉树顺序存储结构(哑元素采用@字符表示)。 如：二叉树如下所示，则输出的完全二叉树顺序结构为：A@B@@C@@@@@@D 实验目的：掌握二叉树二叉链表存储结构的建立、遍历等基本算法。 数据结构设计简要描述： 采用单向链表，每个结点包含字符类型的数据域和两个指针域。结构如下： typedef struct node { ElemTp data; //数据域 struct node *lchild; //左指针 struct node *rchild; //右指针 } 采用循环队列存放链表中的结点，结构如下： typedef struct { ElemType *elem; int n; //队列容量 int f; //队头指针 int r; //队尾指针 } A B C D 算法设计简要描述： 采用先序遍历的方法建立二叉树。先序中序后序遍历采用递归算法反复调用自身，当结点为空时结束递归。 层次遍历时将根放入循环队列，然后在循环体中取出队首元素，打印数据域。再将左右儿子放入队列尾，队空时结束循环。同时，将层次遍历的结果存入字符串，并记录字符串的做i 后一个字符。 将二叉树转化为完全二叉树时也采用层次遍历的方法，结束条件为从队列取出元素的数据域等于字符串的最后一个字符。单结点为空时创建结点，并为空结点创建空间，为指针域赋值’@’。同时输出层次遍历的结果。 输入/输出设计简要描述： 从键盘连续输入字符，字符’#’表示空结点。单需要创建队列时需手动输入队列的大小。输出均有文字提示信息。当队列空间不足时提示队满，并退出程序。 编程语言说明： 使用Visual C++编程。主要代码采用C语言实现。输入输出采用scanf和printf函数，动态分配内存空间采用malloc操作符。编程注释采用C/C++规范。 主要函数说明： void initQueue(SqQueue &q) //初始化队列 void clearQueue(SqQueue &q) //清空队列 int empty(SqQueue &q) //判断队空 int full(SqQueue &q) //判断队满 int inQueue(SqQueue &q, ElemType e) //队尾入队 int outQueue(SqQueue &q, ElemType &e) //队头出队 BiT crtBT()//用先序遍历算法建立二叉树 void preorder(BiT bt) //先序遍历 void midorder(BiT bt) //中序遍历 void lasorder(BiT bt) //后序遍历 void layertravel(BiT bt,char str1[],int &n) //二叉树按层次遍历 void fullBT(BiT bt,char str1[],int n) //建立完全二叉树并输出 程序测试简要报告： 输入：A#BC#D### 树的结构如下： 实验名称:二叉树链式存储结构 实验类型：验证性实验 班级：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 二叉树的基本性质等考点讲解 1、树的基本概念 树是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。 2、二叉树及其基本性质 （1）什么是二叉树 二叉树是一种很有用的非线性结构，它具有以下两个特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 *：根据二叉树的概念可知，二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有2棵子树）。 （2）二叉树的基本性质 性质1 在二叉树的第k层上，最多有2k-1 个结点。 性质2 深度为m的二叉树最多有个2m-1个结点。 性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。 性质4 具有n个结点的二叉树，其深度至少为[log2n]+1 ，其中 [log2n]表示取log2n的整数部分。 3、满二叉树与完全二叉树 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 *：根据完全二叉树的定义可得出：度为1的结点的个数为0或1。 下图a表示的是满二叉树，下图b表示的是完全二叉树： 完全二叉树还具有如下两个特性： 性质5 具有n个结点的完全二叉树深度为[log2n]+1 。 性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k=1，2，…，n）的结点有以下结论： ①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。 ②若2k≤n，则编号为k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。 ③若2k+1≤n，则编号为k的右子结点编号为2k+1；否则该结点 #include数据结构实验指导书 二叉树两种存储结构的应用
树的存储与遍历操作
二叉树的顺序存储结构
用二叉树实现存储信息
实验五--二叉树的存储结构和基本操作
5.2-3 (有修改)二叉树ADT及存储表示
二叉树的存储与实现
实验二叉树及其应用(严选材料)
二叉树存储分类
数据结构习题 树 数据机构c语言版
二叉树的性质与链式存储结构-实验8报告讲解
二叉链表的建立、遍历以及生成完全二叉树顺序存储结构
二叉树链式存储结构 第六章实验报告
二叉树的基本性质等考点讲解
设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目
相关主题
文本预览