二叉排序树的建立及查询
一、上机实验的问题和要求：
复习二叉排序树的生成及查找算法，编写完整的程序。
实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。
二、源程序及注释：
#include
#include
typedef int InfoType;
typedef int KeyType; //假定关键字类型为整数
typedef struct node //结点类型
{
KeyType key; //关键字项
InfoType otherinfo; //其它数据域，InfoType视应用情况而定下面不处理它
struct node *lchild,*rchild;//左右孩子指针
}BSTNode;
typedef BSTNode *BSTree; //BSTree是二叉排序树的类型
BSTNode *SearchBST(BSTree T,KeyType key)
{ //在二叉排序树T上查找关键字为key 的结点，成功时返回该结点位置，否则返回NULL
if(T==NULL||key==T->key) //递归的终结条件
return T; //若T为空，查找失败；否则成功，返回找到的结点位置
if(key
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); //继续在右子树中查找
}
void InsertBST(BSTree *T,int key)
{ //插入一个值为key的节点到二叉排序树中BSTNode *p,*q;
if((*T)==NULL)
{ //树为空树
(*T)=(BSTree)malloc(sizeof(BSTNode));
(*T)->key=key;
(*T)->lchild=(*T)->rchild=NULL;
}
else
{
p=(*T);
while(p)
{
q=p;
if(p->key>key)
p=q->lchild;
else if(p->key p=q->rchild; else { printf("\n该二叉排序树中含有关键字为%d的节点!\n",key); return; } } p=(BSTree)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; if(q->key>key) q->lchild=p; else q->rchild=p; } } BSTree CreateBST(void) { //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回 BSTree T=NULL; //初始时T为空树 KeyType key; scanf("%d",&key); //读入一个关键字 while(key) { //假设key=0是输入结束标志 InsertBST(&T,key); //将key插入二叉排序树T scanf("%d",&key); //读入下一关键字 } return T; //返回建立的二叉排序树的根指针 } void ListBinTree(BSTree T) //用广义表表示二叉树 { if (T!=NULL) { printf("%d",T->key); if (T->lchild!=NULL||T->rchild!=NULL) { printf("("); ListBinTree(T->lchild); if (T->rchild!=NULL) printf(","); ListBinTree(T->rchild); printf(")"); } } } void main() { BSTNode *SearchBST(BSTree T,KeyType key); void InsertBST(BSTree *Tptr,KeyType key); BSTree CreateBST(); void ListBinTree(BSTree T); //用广义表表示二叉树BSTree T; BSTNode *p; int key; printf("请输入关键字（输入0为结束标志）：\n"); T=CreateBST(); ListBinTree(T); printf("\n"); printf("请输入欲查找关键字："); scanf("%d",&key); p=SearchBST(T,key); if(p==NULL) printf("没有找到%d！\n",key); else printf("找到%d！\n",key); ListBinTree(p); printf("\n"); } 三、运行输出结果： 四、调试和运行程序过程中产生的问题及采取的措施： 1、输入数据时，总是不能得到结果，原因：在建立二叉树函数定义中，是对指针的值进行了修改； 解决方法：用指向指针的指针。 2、实验中经常会出现前后字符不一致的情况，主要原因是自己在编程时比较马虎，遇到比较长的程序，就容易出错。 解决方法：平时应多加练习，要仔细认真检查自己是否出现错误。 3、在类似(*T)->key=key的语句中，括号没加，程序无法运行； 解决方法：加上括号即可。 五、思考题： 请思考采用其他存储结构实现的二叉排序树建立算法。 用下列程序代替源程序中的相应的部分。 void InsertBST(BSTree *Tptr,KeyType key) { BSTNode *f,*p=*Tptr; while(p) { if(p->key==key) return; f=p; p=(key } p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; if(*Tptr==NULL) *Tptr=p; else if(key f->lchild=p; else f->rchild=p; } BSTree CreateBST(void) { BSTree T=NULL; KeyType key; scanf("%d",&key); while(key) { InsertBST(&T,key); scanf("%d",&key); } return T; } 六、实验总结： 在开始编程时，不知道从何入手，自己在上课听讲了，而且也懂了。在编程时想自己独立完成，但看到要求之后突然感觉很迷茫，不得以看得借鉴老师提供的代码。其中有诸多原因，首先自己在编程经验上严重欠缺，这使得自己在接到一道题时无从下手，另外对二叉排序树的理解不够深入，所有编程都是建立在对其算法结构有深入理解的基础上的。而且听懂不意味着理解，只有在自己亲自编程的实践过程中，才能逐渐加深理解。 自己C语言的底子不够厚实，今后要加强C语言知识的理论学习，系统地掌握C语言。这样才能给实践提供良好的理论基础。 二叉排序树的基本操作的实现 ————————————————————————————————作者: ————————————————————————————————日期: 二叉排序树的基本操作的实现 一设计要求 1.问题描述 从磁盘读入一组数据,建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。 2.需求分析 建立二叉排序树并对其进行查找,包括成功和不成功两种情况。 二概要设计 为了实现需求分析中的功能,可以从以下3方面着手设计。 1.主界面设计 为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。 图1二叉排序树的基本操作的主菜单 2.存储结构的设计 本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成,还有指向该左孩子和右孩子的指针。 3.系统功能设计 本程序设置了5个子功能菜单，其设计如下。 1)建立二叉排序树。根据系统提示,输入节点的关键字,并以0作为结束的标识符。 该功能由Bｓtｒee Creａte（)函数实现。 2)插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已 经存在,则不插入。该功能由Bstree Inｓerｔ(y)函数实现。 3)查询二叉排序树的信息。每次进行查询,成功则显示“查询到该节点”,不成功 则“显示查询不到该节点“该功能由Ｂsｔree Seaｒcｈ()函数实现。 4)删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除， 删除的方式是输入关键字，查询到该节点后删除。该功能由ＢｓtreeＤelete() 函数实现。 5)遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。 该功能由ｖoｉd Ｔraveｒse()实现。 三模块设计 1.模块设计 本程序包含两个模块:主程序模块和二叉排序树操作模块。其调用关系如图2 课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能： （1）建立二叉排序树； （2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 排序二叉树的建立及其遍历的实现 摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据 组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言 我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归 调用，这将极大的方便算法设计。 1．需求分析 建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。 该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。 //二叉树的基本操作 #include 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 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 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程 数据结构与算法 课程设计 名称 二叉排序树运算学生姓名顾成方 学号0704011033 专业班级08计科(2) 指导教师王昆仑张贯虹 2010 年 5 月 题目：（二叉排序树运算问题）设计程序完成如下要求：对一组数据构造二叉排序树，并在二叉排序树中实现多种方式的查找。基本任务：⑴选择合适的储存结构构造二叉排序树；⑵对二叉排序树T作中序遍历，输出结果；⑶在二叉排序树中实现多种方式的查找，并给出二叉排序树中插入和删除的操作。 ⑷尽量给出“顺序和链式”两种不同结构下的操作，并比较。 一、问题分析和任务定义 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。 实现本程序需要解决以下几个问题： 1、如何构造二叉排序树。 2、如何通过中序遍历输出二叉排序树。 3、如何实现多种查找。 4、如何实现插入删除等操作。 二叉排序树的定义： ⑴其左子树非空，则左子树上所有结点的值均小于根结点的值。 ⑵若其右子树非空，则右子树上所有结点的值大于根结点的值。 ⑶其左右子树也分别为二叉排序树。 本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。 本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include 数据结构 实 验 报 告 实验名称：______二叉排序树___________ 学生姓名：____________________ 班级：_______________ 班内序号：_______________________ 学号：________________ 日期：________________ 1．实验要求 根据二叉排序树的抽象数据类型的定义，使用二叉链表实现一个二叉排序树。 二叉排序树的基本功能： 1.二叉排序树的建立 2.二叉排序树的查找 3.二叉排序树的插入 4.二叉排序树的删除 5.二叉排序树的销毁 6.其他：自定义操作编写 测试main()函数测试二叉排序树的正确性 2. 程序分析 2.1 存储结构 二叉链表 2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程图等) 2.2.1. 2.2.2.伪代码 1.从文件读取待建树元素 2.建树，若待插入元素比根节点小，向左子树前进并重复比较左子树根节点，若待插入元素比根节点大，向右子树前进并重复比较右子树根节点，直至找到空节点则插入该元素，不断插入直至不剩下元素。 3.用户选择操作。 4.若用户选择查找，则现由用户输入待查找数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至关键码相等，则输出节点情况。 5.若用户选择插入，则现由用户输入待插入数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至到空节点，则插入该元素。 6.若用户选择删除，则现由用户输入待删除数值。从根节点开始比较，若较小则移至左子树，若较大则移至右子树，直至关键码相等； 1）.若该节点为叶子节点，则直接删除； 2）.若该节点无左子树，则其双亲节点直接与其右子树根节点连接，再删除该节点； 3）.若该节点有左子树，则其左子树的最右节点数值直接覆盖该节点数值，再删除最后节点。 7.若用户选择销毁，则不断执行删除操作直至不剩余节点。 8.若用户选择退出，则程序结束。 2.3 关键算法分析 关键代码即删除操作，代码如下： void Delete(BiNode* &R) { BiNode* q=new BiNode; BiNode *s=new BiNode; if(R->lch==NULL){ q=R; R=R->rch; delete q;} else if(R->rch==NULL){ q=R; R=R->lch; delete q; } else{ q=R; s=R->lch; while(s->rch!=NULL) { q=s; s=s->rch;} R->data=s->data; if(q!=R) 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #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 ; 内蒙古科技大学 本科生课程设计论文《数据结构与算法》 题目：二叉排序树的操作 学生姓名：贺英杰 学号：1367159108 专业：软件工程 班级：13-1班 指导教师：周李涌 日期：2015年1月6日 内蒙古科技大学课程设计任务书课程名称数据结构与算法课程设计 设计题目二叉排序树的操作 指导教师周李涌时间2015.1.5——2015.1.9 一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风 二、设计资料及参数 每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。 二叉排序树的操作 以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。 要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数： 创建二叉排序树 输出二叉排序树 在二叉排序树中查找给定值 在二叉排序树中插入新结点 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。 三、设计要求及成果 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 四、进度安排 资料查阅与讨论（1天） 系统分析（2天） 系统的开发与测试（5天） 编写课程设计说明书和验收（2天） 五、评分标准 1. 根据平时上机考勤、表现和进度，教师将每天点名和检查 2. 根据课程设计完成情况，必须有可运行的软件。 3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。 4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问 六、建议参考资料 1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.11 2．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社 2007.2 3.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社 2007.6 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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需求分析 2.1在日常生活中，人们几乎每天都要进行“查找”工作。所谓“查找”即为 在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），即关键字。 2.2本程序意为对一个已经建立的动态查找表——二叉树——判断其是否是二 叉排序树和平衡二叉树。 3数据结构设计 3.1抽象数据类型二叉树的定义如下： ADT BinaryTree{ 3.1.1数据对象D：D是具有相同特性的数据元素的集合。 3.1.2数据关系R: 若D=NULL，则R=NULL，称BinaryTree为空的二叉树； 若D!=NULL,则R={H}，H是如下的二元关系: 3.1.2.1在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 3.1.2.2若D-{root}!=NULL,则存在D-{root}={Dl,Dr},且Dl与Dr相交为空； 3.1.2.3若Dl！=NULL，则Dl中存在唯一的元素xl, 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 5.1树的概念 树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4； 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林； 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。 5.树的表示 树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树 1.二叉树的基本形态： 二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——(a)； (2)只有一个根结点的二叉树——(b)； (3)右子树为空的二叉树——(c)； (4)左子树为空的二叉树——(d)； (5)完全二叉树——(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。 2.两个重要的概念： (1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图： 完全二叉树 1页 编号：B04900083 学号：8 Array课程设计 教学院计算机学院 课程名称数据结构与算法 题目二叉排序树与平衡二叉排序树基本操 作的实现 专业计算机科学与技术 班级二班 姓名 同组人员 指导教师成俊 2015 年12 月27 日 课程设计任务书 2015 ～2016 学年第 1 学期 学生：专业班级：计科二 指导教师：成俊工作部门：计算机学院 一、课程设计题目:二叉排序树与平衡二叉排序树基本操作 二、课程设计容 用二叉链表作存储结构，编写程序实现二叉排序树上的基本操作：以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T；对二叉排序树T作中序遍历；计算二叉排序树T的平均,输出结果；输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历；否则输出信息“无结点x”； 判断二叉排序树T是否为平衡二叉树；再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT；计算平衡的二叉排序树BT的平均查找长度，输出结果。 三、进度安排 1．分析问题，给出数学模型，选择数据结构. 2．设计算法，给出算法描述 3．给出源程序清单 4. 编辑、编译、调试源程序 5. 撰写课程设计报告 四、基本要求 编写AVL树判别程序，并判别一个二叉排序树是否为AVL树。二叉排序树用其先序遍历结果表示，如：5，2，1，3，7，8。 实现AVL树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二叉排序树转变为AVL树的操作。 实现提示主要考虑树的旋转操作。 目录 一、课程设计题目: 二叉排序树与平衡二叉排序树基本操作 (1) 二、课程设计容 (1) 三、进度安排 (1) 四、基本要求 (1) 一、概述 (3) 1.课程设计的目的 (3) 2.课程设计的要求 (3) 二、总体方案设计 (4) 三、详细设计 (6) 1.课程设计总体思想 (6) 2.模块划分 (7) 3.流程图 (8) 四、程序的调试与运行结果说明 (9) 五、课程设计总结 (14) 参考文献 (14) 学号 数据结构课程设计 设计说明书 排序二叉树的遍历 起止日期：2011 年12月12日至2011 年12月16日 学生姓名 班级 成绩 指导教师(签字) 电子与信息工程系 2011年12月16日 天津城市建设学院 课程设计任务书 2011 —2012 学年第二学期 电子与信息工程系软件工程专业班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2011 年12月12 日至2011 年12月16 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 指导教师（签字）： 教研室主任（签字）： 批准日期： 2011 年 12 月 17 日 主要内容： 一、需求分析： 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 我自己的思想：首先设想把源程序分成头文件，调用和主函数三部分。在头文件中申明类和定义结构体，把先序，中序，后序，层次和叶子节点数的函数定义在类中。然后在调用文件中，把几个函数的实现定义写在里面。最后在主函数中把输出结果以菜单的样式输出来的方式写完主函数程序。实现的过程是先想好自己要输入的是什么，然后通过输入节点制，判断其是否是满足前序遍历，满足则可以实现下后面的功能。 二、问题求解： 现实中的问题：给同学排队问题。 层次是从头开始每一层一层的排，然后分别记号码。 前序是先从最上面的那一个开始往左手边开始排，排之前先计算好人数，然后开始排，排玩左边排右边。 中序是先从最左边开始，然后左斜上角，然后右下角，再左斜上角，直到最上层为止，然后安这个顺序继续排右边的。 后序是先从最左边开始的，左边的一次排过来，然后直接排右边的，也是安依次的顺序，最后才是最上层的。 二叉排序树的实现 一、实验内容与要求 1）实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 二、实验方案 1.选择链表的方式来构造节点，存储二叉排序树的节点。 //树的结构 struct BSTNode { //定义左右孩子指针 struct BSTNode *lchild,*rchild; //节点的关键字 TElemType key; }; int depth=0; //定义一个 struct BSTNode 类型的指针 typedef BSTNode *Tree; 2.对树的操作有如下方法： // 创建二叉排序树 Tree CreatTree(Tree T)； //二叉树的深度，返回一个int值为该树的深度 int TreeDepth(Tree T) //树状输出二叉树，竖向输出 void PrintTree(Tree T , int layer)； //查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点 Status SearchBST(Tree T , TElemType key , Tree f,Tree &p)； //向树中插入节点 Status InsertBST(Tree &T , TElemType e)； //删除节点 Status Delete(Tree &T)； //删除指定节点，调用Delete(Tree &T)方法 Status DeleteData(Tree &T , TElemType key)； //非递归先序遍历 void x_print(Tree T); //非递归中序遍历 Void z_print(Tree T ); //非递归后序遍历 void h_print(Tree T); 3.对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现 //自定义类型以 SElemType作为栈中指针返回的值的类型 //也就是要返回一个节点的指针 typedef Tree SElemType; //栈的结构 struct Stack { //栈底指针 SElemType *base; //栈顶指针 SElemType *top; //栈的容量 int stacksize; }; 4.栈的操作方法： //创建一个空栈 Status InitStack(Stack &S)； //获取栈顶元素并删除栈中该位置的元素 SElemType Pop(Stack &S,SElemType &elem) 二叉树的基本操作实验报告 学号姓名实验日期 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. 掌握二叉树的存储实现 2. 掌握二叉树的遍历思想 3. 掌握二叉树的常见算法的程序实现 二、实验环境 VC++6.0 三、实验内容 1.输入字符序列，建立二叉树的二叉链表结构。（可以采用先序序列） 2.实现二叉树的先序、中序、后序的递归遍历算法。 3.实现二叉树的先序、中序、后序的非递归遍历算法。 4.求二叉树的高度。 5.求二叉树的结点个数。 6.求二叉树的叶子结点的个数。 四、实验要求： 分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述子函数。 五、实验步骤和结果 1.打开vc，新建文本，命名二叉树算法，编写代码。 2.编写代码： #include BiTNode *base; BiTNode *top; int stacksize; } SqStack;//栈类型 void InitStack(SqStack *S)//创建二叉树 { S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } void Push(SqStack *S,BiTNode e)//进栈 { if(S->top - S->base >= S->stacksize)//如果栈空间不足 { S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(B iTNode)); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *(S->top)=e; S->top++; } BiTNode Pop(SqStack *S)//出栈 { S->top --; return *S->top; } int StackEmpty(SqStack *S)//判断栈是否非空 { if(S->top == S->base ) return 1; else return 0; } /*---------------------------------------------递归部分-------------------------------------------*/二叉排序树的基本操作的实现
二叉排序树的建立及遍历的实现
二叉树的基本 操作
实验10 二叉树的基本操作
二叉排序树运算-数据结构与算法课程设计报告_l
实验三二叉树的基本操作
北邮数据结构实验—二叉排序树
数据结构——二叉树基本操作源代码
实现二叉排序树的各种算法
《二叉排序树的操作》课程设计报告
数据结构实验三——二叉树基本操作及运算实验报告
数据结构课程设计---二叉排序树和平衡二叉树的判别
二叉树基本操作经典实例
各类型二叉树例题说明
二叉排序树与平衡二叉排序树基本操作的实现
数据结构 课程设计 排序二叉树
二叉排序树实验报告
二叉树的基本操作实验报告
二叉树排序算法
- 实验5 二叉搜索树的基本操作(大作业)
- 二叉排序树地创建、删除、插入等操作
- 数据结构课程设计-二叉排序树的简单应用报告
- 二叉排序树及其应用(算法与数据课程设计)
- 二叉排序树的基本操作的实现
- 二叉排序树运算-数据结构与算法课程设计报告_l
- 二叉排序树与平衡二叉排序树基本操作的实现
- 二叉排序树的实现
- 实验5-二叉搜索树的基本操作(大作业)
- 数据结构——二叉排序树的基本操作的实现
- 北邮数据结构实验—二叉排序树
- 二叉树—基本操作与二叉排序树
- 二叉排序树实验报告
- 二叉排序树的建立、插入和删除操作
- 二叉排序树与平衡二叉排序树基本操作的实现
- 数据结构课程设计_二叉排序树
- 二叉排序树的创建、删除、插入等操作
- 数据结构实验-二叉排序树应用实验报告
- 二叉排序树的操作课程设计报告
- 二叉排序树的实现