实验5 二叉搜索树、平衡二叉搜索树(2学时)
实验五二叉搜索树、平衡二叉搜索树（2学时）
(时间：第12周三56节)
一、实验目的
1.掌握二叉搜索树的基本概念，掌握二叉搜索树的插入结点和删
除结点的算法；
2.掌握中序迭代器及其应用；
3.掌握线索二叉树的基本概念，掌握中序线索二叉树的创建和基
于中序线索的中序遍历算法和中序迭代器，了解前序线索二叉树与前序迭代器和后序线索二叉树和后序迭代器。
4.掌握平衡二叉搜索树的基本概念，掌握平衡二叉搜索树的插入
结点和调整平衡的算法；
5.了解二叉搜索树、平衡二叉搜索树的应用。
二、实验内容
1、实现二叉搜索树类，并完成以下操作：
（1）依次输入整形数据数值：8，11，10，3，2，6，4，5创建二叉搜索树，并垂直二叉搜索树；
（2）删除数值为3的结点，再垂直二叉搜索树；
（3）再插入数值为3的结点，垂直二叉搜索树。
2、在二叉搜索树类中加入中序迭代器，用中序迭代器对上面创
建的二叉搜索树进行中序遍历。
3、创建中序线索二叉树，实现基于中序线索的中序遍历算法（非
递归，且不用栈）和中序迭代器（不用栈）。设创建二叉树的程序为： template
void BinaryTree
{
char ch;
cout<<"请输入结点值：";
cin>>ch;
if(ch=='#') //用符号#表示序列中的外部结点
{
t = NULL;
}
else
{
t=new BTNode(ch);
CreateBTree_Pre_Rec(t->left);
CreateBTree_Pre_Rec(t->right);
}
}
输入的二叉树如图1所示，其中#为外部结点。
4、创建平衡二叉搜索树类并实现插入元素的算法。依次输入整形数据：1，2，3，4，5，6，7，8，9，10，11，12创建平衡二叉搜索树，然后垂直输出该平衡二叉搜索树。
三、思考题 A B D C E F # # # # # # #
1、若输入关键字序列分别为（7, 8, 3, 5, 9, 1）或（9, 3, 1, 7, 5, 8），运用二叉排序树的生成算法生成对应的二叉排序树，并写出它们的中序遍历序列。
2、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A. LL
B. LR
C. RL
D. RR
3、什么是动态查找？
4、拓展题：
（1）编写算法判断一棵二叉树是不是二叉搜索树。
（2）创建前序线索二叉树，实现不用栈的非递归前序遍历算法，并用该算法对所创建的前序线索二叉树进行前序遍历。实现前序迭代器，并用前序迭代器前序遍历二叉树。
（3）创建后序线索二叉树，并实现基于后序线索的后序遍历。实现逆后序迭代器，并用逆后序迭代器输出二叉树的逆后序遍历序列。
（4）编写程序，通知在一段文本中每一个单词出现的频率和所在行号。
（5）完成带有迭代器的平衡二叉搜索树类的实现（删除运算可以省略）。
最优二叉搜索树
#include wyf 实现二叉排序树的各种算法 一.需求分析 (1)系统概述： 本系统是针对排序二叉树设计的各种算法，提供的功能包括有：（1）插入新结点（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) 二.总体设计 (1)系统模块结构图 (2)数据结构设计 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针} BiTNode,*BiTree; typedef BiTree SElemType; typedef BiTree QElemType; typedef struct { QElemType *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; typedef struct { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 Status InitStack(SqStack &S) { // 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE // 请补全代码 S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) return (ERROR); S.top = S.base ; 最优二叉查找树 【源程序】 //本程序测试用例为课本例题 #include } return C[1][n]; } int main() { int n; double p[100]; printf("请输入字符个数："); scanf("%d",&n); printf("\n"); printf("请输入每个字符的查找概率："); for(inti=0; i 实验题目：实验九——二叉树实验 算法设计（3） 问题分析： 1、题目要求：编写算法交换二叉树中所有结点的左右子树 2、设计思路：首先定义一个二叉树的数据类型，使用先序遍历建立该二叉树，遍历二叉树，设计左右子树交换的函数，再次遍历交换之后的二叉树，与先前二叉树进行比较。遍历算法与交换算法使用递归设计更加简洁。 3、测试数据： A、输入：1 2 4 0 0 5 0 0 3 0 0 交换前中序遍历：4 2 5 1 3 交换后中序遍历：3 1 5 2 4 交换前：交换后： B、输入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0 交换前中序遍历：11 7 17 18 19 3 13 6 16 交换后中序遍历：16 6 13 3 19 18 17 7 11 概要设计： 1、为了实现上述功能：①构造一个空的二叉树；②应用先序遍历输入，建立二叉树；③中序遍历二叉树；④调用左右子树交换函数；⑤中序遍历交换过后的二叉树。 2、本程序包括4个函数： ①主函数main（） ②先序遍历二叉树建立函数creat_bt（） ③中序遍历二叉树函数inorder（） ④左右子树交换函数 exchange（） 各函数间关系如下： 详细设计： 1、结点类型 typedef struct binode //定义二叉树 { int data; //数据域 struct binode *lchild,*rchild; //左孩子、右孩子 }binode,*bitree; 2、各函数操作 ① 先序遍历建二叉树函数 bitree creat_bt() { 输入结点数据； 判断是否为0{ 若是，为空； 不是，递归；} 返回二叉树； } ② 左右子树交换函数 void exchange(bitree t) { 判断结点是否为空{ 否，交换左右子树； 递归；} } ③ 中序遍历函数 void inorder(bitree bt) { 判断是否为空{ 递归左子树； 输出； 递归右子树；} } main （） creat_bt （） inorder （） exchange （） 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); } 二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) 《算法分析与设计》 实验报告 题目： 姓名： 班级： 学号： 指导教师： 完成时间： 一、实验题目 给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。 二、实验目的 1. 理解时间复杂度的概念。 2. 深入地掌握C语言编程。 3. 通过编程直观地理解算法分析的意义 三、实验要求 给定一系列键值和权重，构造最优二叉排序树，使得总的查找次数最少。要求的输出格式为：第一行为最优的查找次数，第二行为最优二叉排序树的前序遍历得到的序列，然后一个空行，随后为源代码。算法的输入如下(冒号前为键值，冒号后为权重)：1:0 2:56 3:19 4:80 5:58 6:47 7:35 8:89 9:82 10:74 11:17 12:85 13:71 14:51 15:30 16:1 17:9 18:36 19:14 20:16 21:98 22:44 23:11 24:0 25:0 26:37 27:53 28:57 29:60 30:60 31:16 32:66 33:45 34:35 35:5 36:60 37:78 38:80 39:51 40:30 41:87 42:72 43:95 44:92 45:53 46:14 47:46 48:23 49:86 50:20 51:77 52:84 53:99 54:99 55:61 56:39 57:26 58:29 59:84 60:2 61:37 62:9 63:67 64:5 65:0 66:91 67:27 68:27 69:58 70:69 71:83 72:72 73:48 74:20 75:74 76:46 77:45 78:94 79:74 80:10 81:59 82:38 83:73 84:60 85:57 86:36 87:15 88:22 89:42 90:80 91:51 92:98 93:75 94:34 95:16 96:65 97:49 98:6 99:69 100:50 101:14 102:94 103:14 104:90 105:69 106:30 107:42 108:7 109:96 110:68 111:15 112:87 113:82 114:58 115:19 116:17 江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院 江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改 6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include 一、填空题（20 分） 1. 一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊 类型问题的一系列运算，此外，算法还应具有以下五个重要特性: , , , _________ , _______ 。 2. 算法的复杂性有_____________ 和__________ 之分，衡量一个算法 好坏的标准是_______________________ 。 3. 某一问题可用动态规划算法求解的显著特征是 4. 若序列X={B,C,A,D,B,C,D} ，Y={A,C,B,A,B,D,C,D} ，请给出序列X 和Y 的一个最长公共子序列 ____________________________ 。_ 5. 用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少 应包含__________ 。 6. 动态规划算法的基本思想是将待求解问题分解成若干 _______ ， 先求解_____ ，然后从这些_____ 的解得到原问题的解。 7. 以深度优先方式系统搜索问题解的算法称为_____________ 。 8.0-1 背包问题的回溯算法所需的计算时间为 _______________ ,用动态 规划算法所需的计算时间为 ____________ 。 9. 动态规划算法的两个基本要素是 ____________ 和_________ 。 10. 二分搜索算法是利用______________ 实现的算法。 二、综合题（50 分） 1. 写出设计动态规划算法的主要步骤。 2. 流水作业调度问题的johnson 算法的思想。 3. 若n=4,在机器M1和M2上加工作业i所需的时间分别为日和b i, 且(a i,a2,a3,a4)=(4,5,12,10) , (b i,b2,b3,b4)=(8,2,15,9) 求 4 个作业 的最优调度方案，并计算最优值。 4. 使用回溯法解0/1 背包问题：n=3，C=9，V={6,10,3} ， W={3,4,4}, 其解空间有长度为3 的0-1 向量组成，要求用一棵完全二叉树表示其解空间(从根出发，左 1 右0) ，并画出其解空间树，计算其最优值及最优解。 5. 设S={X i,准…，X n}是严格递增的有序集，利用二叉树的结点 来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i。( 2)在二叉搜索树的叶结点中确定X€( X , X+1),其概率为 a i。在表示S的二叉搜索树T中，设存储元素X的结点深度为C ；叶结点(X , X+1)的结点深度为d i，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]= {X , X+i，?…，X}最优值为m[i][j], W[i][j]= a i-1 +b i+ ? ? ? +b+a，贝S m[i][j](1<=i<=j<=n) 递归关系表达式为什么？ 6. 描述0-1 背包问题。 三、简答题 ( 30分) 1?流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为a i 和b i ，请写出流水作业调度问题的johnson 法则中对 a i 和 b i 的排序算法。(函数名可写为sort(s,n) ) 实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include 二叉查找树（BST，Binary Search Tree），又名二叉搜索树或二叉检索树，是一颗满足如下条件的树： 1、每个节点包含一个键值 2、每个节点有最多两个孩子 3、对于任意两个节点x和y，它们满足下述搜索性质: a、如果y在x的左子树里，则key[y] <= key[x] b、如果y在x的右子树里，则key[y] >= key[x] 最优二叉查找树（Optimal BST，Optimal Binary Search Tree） 最优二叉查找树是使查找各节点平均代价最低的二叉查找树。具体来说就是：给定键值序列K = 二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include 浙江大学城市学院实验报告 课程名称数据结构与算法 实验项目名称实验五二叉搜索树的基本操作 学生姓名蓝礼巍专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1．掌握二叉搜索树的基本概念。 2．掌握二叉搜索树基本操作的实现。 二. 实验内容 1. 设在一棵二叉搜索树的每个结点的data域中，含有关键字key域和统计相同关键字元素个数的count域。当向该树插入一个元素时，若树中已有相同关键字值的结点，则使该结点的count域值增1，否则由该元素值生成一个新结点插入到该树中，并使其count域值为1。当向该树删除一个元素时，若树中该元素结点的count域值大于1，则使该结点的count域值减1，否则（count 域值等于1）删除该结点。编写头文件bstree.h，实现上述二叉搜索树的存储结构定义与基本操作实现函数；编写主函数文件test8_1.cpp，验证头文件中各个操作。 基本操作包括： ①void InitBSTree(BTreeNode *&bst); //初始化该二叉搜索树 ②void PrintBSTree(BTreeNode *bst); //以广义表形式输出该二叉搜索树（输出内容包括关键字值与相同元素个数值） ③void Insert (BTreeNode *&bst, ElemType item); //插入一个元素到该二叉搜索树（用非递归算法实现） ④int Delete (BTreeNode *&bst , ElemType item); //从二叉搜索树中删除某个元素（用非递归算法实现） ⑤ElemType MaxBSTree(BTreeNode *bst); //求该二叉搜索树的最大关键字值（用非递归算法实现） 2.选做：编写下列操作的实现函数，添加到头文件bstree.h中，并在主函数文件test8_1.cpp中添加相应语句进行测试。 ①void PrintNode1(BTreeNode *bst); //按递减序打印二叉搜索树中所有左子树为空，右子树非空的结点数据域的值 ②void PrintNode2(BTreeNode *bst, int x ); 二叉搜索树 锁定 本词条由“科普中国”百科科学词条编写与应用工作项目审核。 在二叉排序树b中查找x的过程为： 若b是空树，则搜索失败，否则： 若x等于b的根结点的数据域之值，则查找成功；否则： 若x小于b的根结点的数据域之值，则搜索左子树；否则： 查找右子树。 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &*p){ //在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，//则指针p指向该数据元素结点，并返回TRUE，否则指针指向查找路径上访问的最后//一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL if(!T){ p=f; return FALSE;} //查找不成功 else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功 else if LT(key,T->data.key) return SearchBST(T->lchild, key, T, p); //在左子树中继续查找 else return SearchBST(T->rchild, key, T, p); //在右子树中继续查找 pascal语言实现 type Link = ^tree; Tree = record D :longint; Left :link; Right :link; End; function search(n :longint;t :link):boolean; Begin If t^.d < n then begin If t^.right = nil then exit(false) else exit(search(n,t^.right)); End; If t^.d > n then begin If t^.left = nil then exit(false) else exit(search(n,t^.left)); End; Exit(true); End; 插入算法 向一个二叉排序树b中插入一个结点s的算法，过程为： 若b是空树，则将s所指结点作为根结点插入，否则： 若s->data等于b的根结点的数据域之值，则返回，否则： 若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。 南昌大学实验报告 学生姓名：李木子学号：专业班级：软工 实验类型：□验证□综合□设计□创新实验日期：实验成绩：一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历三、实验基本原理 四、主要仪器设备及耗材 电脑， 五、实验步骤 ************************************** * 链式二叉树的创建与遍历 * ************************************** ************************************** * 链式二叉树的结构体定义 * ************************************** <> <> ; { ; *; *; }; ************************************** * 链式二叉树函数声明 * ************************************** *(); (*); (*); (*); ************************************** * 链式二叉树创建函数 * ************************************** *() { ; *; (); ('') ; ('\'); { (*)(()); >; >(); >(); } ; } ************************************** * 链式二叉树递归前序遍历函数 * ************************************** (*) { () { ("\">); 二叉树的创建与遍历 一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。 二、运行环境 Visual C++ 三、需求分析 1、建立一棵用二叉链表方式存储的二叉树。 2、从键盘接受扩展先序序列，以二叉链表作为存储结构。 3、建立二叉树，并将遍历结果打印输出。采用递归和非递归两种 方法实现。 四、设计概要 //——————二叉树的二叉链表存储表示—————— typedef struct BiTBode{ TElemType data; Struct BiTNode *lchild, *rchild //左右孩子指针 }BiTNode, *BiTree; //—————基本操作的函数原型说明———————— Status CreateBiTree(BiTree &T); //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。 //构造二叉树链表表示的二叉树T。 Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //先序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e)); //采用二叉链表存储结构，visit是对结点操作的应用函数。 //后序遍历二叉树T，对每个结点调用函数visit一次且仅以次。 //一旦visit（）失败，则操作失败。 —————先序遍历二叉树基本操作的递归算法———— Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){ //采用二叉链表存储结构，visit是对数据元素操作的应用函数， 二叉树的遍历实验报告 一、需求分析 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。 对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。 二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。 基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。 二、系统总框图 三、各模块设计分析 （1）建立二叉树结构 建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。 二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。 要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。 建立左右子树时，仍然是调用create （）函数，依此递归进行下去， 直到遇到结束标志时停止操作。 （2）输入二叉树元素 输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。 （3）先序遍历二叉树 当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （4）中序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （5）后序遍历二叉树 当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。 （6）主程序 需列出各个函数，然后进行函数调用。 四、各函数定义及说明 因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。 typedef struct BiTNode { char data; struct BiTNode *Lchild; struct BiTNode *Rchild; 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN 与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include 南昌大学实验报告 学生姓名：李木子学号：8000113146 专业班级：软工133 实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验项目名称 二叉树的遍历 二、实验目的 学会链式二叉树的结构体定义，创建与前序中序后序遍历 三、实验基本原理 四、主要仪器设备及耗材 电脑，VC6.0 五、实验步骤 /**************************************/ /* 链式二叉树的创建与遍历 */ /**************************************/ /**************************************/ /* 链式二叉树的结构体定义 */ /**************************************/ #include /**************************************/ /* 链式二叉树函数声明 */ /**************************************/ BinTreeNode * CreateTree(void); void PreOrder( BinTreeNode * t ); void InOrder( BinTreeNode * t ); void PostOrder( BinTreeNode * t ); /**************************************/ /* 链式二叉树创建函数 */ /**************************************/ BinTreeNode * CreateTree(void) { char ch ; BinTreeNode * t ; ch=getchar(); if(ch=='#') t=NULL; else if( ch=='\n'); else { t=( BinTreeNode*)malloc(sizeof( BinTreeNode )); t->data =ch ; t->lchild=CreateTree(); t->rchild=CreateTree(); } return t ; } /**************************************/ /* 链式二叉树递归前序遍历函数 */ /**************************************/ void PreOrder( BinTreeNode * t ) { if(t) { printf("%c\t",t->data);实现二叉排序树的各种算法
最优二叉查找树_动态规划
二叉树实验报告
数据结构二叉树实验报告
二叉树的建立和遍历的实验报告doc
《算法设计与分析》--最优二叉排序树
实验四 二叉树的遍历和应用04
算法设计与分析考试题及答案(1)
实验八：二叉树的遍历与应用
最优二叉查找树
二叉树的遍历算法实验报告
实验5 二叉搜索树的基本操作(大作业)
二叉搜索树
数据结构实验二叉树的遍历
二叉树实验报告
二叉树的遍历实验报告
数据结构实验三——二叉树基本操作及运算实验报告
数据结构二叉树遍历实验报告
数据结构实验二叉树的遍历