实验四二叉树的操作及应用
实验学时：4
实验类型：（设计型）
一、实验目的
1.理解并掌握二叉树的逻辑结构和物理结构——二叉链表；
2.掌握二叉树的遍历方法；
3.掌握二叉树的构造方法；
4. 掌握计算二叉树结点个数、高度、叶子结点个数算法实现；
5. 掌握交换二叉树左右子树以及复制一棵二叉树算法的实现。
二、实验条件
Visual C++ 6.0
三、实验原理及相关知识
1.二叉树的存储结构描述；
2.二叉树中序、前序、后序、层次遍历的基本思想；
3.构造二叉树的基本思想；
4.求二叉树结点个数、高度、叶子结点个数算法的基本思想；
5.交换二叉树左右子树以及复制一棵二叉树算法的基本思想。
四、实验步骤
1.确定存储结构，写出二叉链表结构类型的具体定义。
2.基本操作的算法实现
(1)中序、前序、后序、层次遍历的递归算法的基本思想及算法实现；
(2)利用先序序列构造二叉树方法的基本思想及算法实现；
(3)求结点个数、高度、叶子结点个数、交换二叉树左右子树以及复制一棵二叉树的递归算法的基本思想及算法实现。
五、思考题及其它
1.线索二叉树的构造及线索化方法的算法实现。
【参考程序1】
#include
#include
#include
#define MaxSize 20
typedef int ElemType;
#define OK 1
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
//建立二叉树（按先序序列生成二叉树,#表示空节点）
void CreateBiTree(BiTree *T)
{
char ch;
scanf("%c",&ch);
getchar();/*回车键（每次输入一个字符后，需敲回车键）*/
if(ch=='#')
{
printf("不产生子树。\n");
*T=NULL;
}
else
{
if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))
{
printf("分配空间失败");
return;
}//生成一个新节点
(*T)->data = ch;
printf("产生左右子树。\n");
;
;
}
}
//递归前序遍历
void Preorder(BiTNode *T)
{
if(T)
{
printf("%c ",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//递归中序遍历
void Inorder(BiTNode *T)
{
if(T)
{
;
;
;
}
}
//递归后序遍历
void Postorder(BiTNode *T)
{
if(T)
{
;
;
;
}
}
//层次遍历二叉树
void Translever(BiTNode *T)
{
struct node
{
BiTNode *vec[MaxSize];
int f,r; //r为队尾，f为队头}queue;
BiTNode *p;
p=T;
queue.f=0;
queue.r=0;
if(T)
printf("%c ", p->data);
queue.vec[queue.r]=p;
queue.r=queue.r+1;
while(queue.f { p=queue.vec[queue.f]; queue.f=queue.f+1; if(p->lchild) { printf("%c ",p->lchild->data); queue.vec[queue.r]=p->lchild; queue.r=queue.r+1; } if(p->rchild) { ; ; ; } printf("\n"); } //按广义表形式输出二叉树 void Disptree(BiTNode *T) { if(T) { printf("%c",T->data); if(T->lchild || T->rchild) { printf("("); Disptree(T->lchild); if(T->rchild) printf(","); Disptree(T->rchild); printf(")"); } } } void main() { BiTree T=NULL; int j; int sign = 1; int num; printf("本程序可以进行建立二叉树、递归先序、中序、后序遍历二叉树、层次遍历二叉树、输出二叉树的扩展序列的操作。\n"); printf("请将二叉树的先序序列输入以建立二叉树。\n"); printf("您必须一个一个地输入字符。\n"); while(sign) { printf("请选择: \n"); printf("1.生成二叉树（#表示空结点） \n"); printf("2.递归先序遍历 3.递归中序遍历\n"); printf("4.递归后序遍历 5.层次遍历\n"); printf("6.输出二叉树的广义表形式 \n"); printf("0.退出程序\n"); scanf("%d",&j); getchar(); switch(j) case 1: printf("生成二叉树:"); CreateBiTree(&T); printf("\n"); printf("\n"); break; case 2: if(T) { printf("递归先序遍历二叉树:"); Preorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case 3: if(T) { printf("递归中序遍历二叉树:"); Inorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case 4: if(T) { printf("递归后序遍历二叉树:"); Postorder(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; case 5: if(T) { printf("层次遍历二叉树:"); Translever(T); printf("\n"); } else printf("二叉树为空!\n"); break; case 6: if(T) { printf("输出二叉树:"); Disptree(T); printf("\n"); printf("\n"); } else printf("二叉树为空!\n"); break; default: sign=0; printf("程序运行结束，按任意键退出!\n"); } } } 【参考程序2】 #include #include #include #define MaxSize 20 typedef int ElemType; #define OK 1 int count; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; //建立二叉树（按先序序列生成二叉树,#表示空节点） void CreateBiTree(BiTree *T) { char ch; scanf("%c",&ch); getchar();/*回车键（每次输入一个字符后，需敲回车键）*/ if(ch=='#') { *T=NULL; } else { if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) { printf("分配空间失败"); return; }//生成一个新节点 (*T)->data = ch; printf("产生左右子树。\n"); CreateBiTree(&((*T)->lchild)) ; CreateBiTree(&((*T)->rchild)) ; } } int Count_Tree(BiTree t)//计算二叉树的结点个数。 { int lcount,rcount; if(t==NULL) return 0; return lcount+rcount+1; } int Height(BiTree t) //计算二叉树的高度 { int h1,h2; if(t==NULL) return 0; else { h1=Height(t->lchild); //求左子树的高度 h2=Height(t->rchild); if(h1>h2) return h1+1; //求右子树的高度 return h2+1; } } void Countleaf(BiTree t,int * count) //计算二叉树的叶子结点的个数{ if(t==NULL) *count=0; if(t->lchild==0 && t->rchild==0) (*count)++; if(t->lchild!=0) Countleaf(t->lchild,count); if(t->rchild!=0) Countleaf(t->rchild,count); } void S(BiTree t) //交换二叉树的左右子树 { BiTree p; if(t==NULL) return; S(t->lchild); S(t->rchild); p=t->lchild; t->lchild=t->rchild; t->rchild=p; } void Copybitree(BiTree t1,BiTree t2) //复制一棵二叉树 { if (t1==NULL) {t2=NULL; return;} t2=(BiTree)malloc(sizeof(BiTNode)); t2->data=t1->data; } void Preorder(BiTree T) { if(T) { printf("%c ",T->data); Preorder(T->lchild); Preorder(T->rchild); } } void main() { BiTree T=NULL,T1=NULL; int j; int sign = 1; int num; count=0; printf("本程序可以建立二叉树、求二叉树的结点个数、高度、叶子结点个数，交换二叉树的左右子树，复制一棵二叉树。\n"); printf("请将二叉树的先序序列输入以建立二叉树。\n"); printf("您必须一个一个地输入字符。\n"); while(sign) { printf("请选择: \n"); printf("1.生成二叉树（#表示空结点）\n"); printf("2.递归求结点个数 3.递归求高度\n "); printf("4.递归求叶子结点个数 5.递归交换二叉树左右子树\n"); printf("6.递归复制一棵二叉树7.输出二叉树\n"); printf("0.退出程序\n"); scanf("%d",&j); getchar(); switch(j) { case 1: printf("生成二叉树:"); CreateBiTree(&T); printf("\n"); printf("\n"); break; case 2: if(T) { printf("递归求二叉树的结点个数：\n"); printf("二叉树的结点个数为：%d\n",Count_Tree(T)); } else printf("二叉树为空!\n"); break; case 3: if(T) { printf("递归求二叉树的高度：\n"); printf("二叉树的高度为：%d\n",Height(T)); } else printf("二叉树为空!\n"); break; case 4: if(T) { printf("递归求二叉树的叶子结点个数：\n"); Countleaf(T,&count); printf("二叉树的叶子结点个数为：%d\n",count); } else printf("二叉树为空!\n"); break; case 5: if(T) { printf("递归交换二叉树左右子树：\n"); S(T); Preorder(T); printf("\n"); } else printf("二叉树为空!\n"); break; case 6: if(T) { printf("递归复制二叉树左右子树：\n"); Copybitree(T,T1) ; Preorder(T1); printf("\n"); } else printf("二叉树为空!\n"); break; case 7: if(T) { printf("二叉树的遍历序列为："); Preorder(T); printf("\n"); } else printf("二叉树为空!\n"); break; default: sign=0; printf("程序运行结束，按任意键退出!\n"); } } } 二叉树的基本操作实现及其应用 一、实验目的 1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< //二叉树的基本操作 #include 课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）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．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include #include { inorder(p->lchild); printf("%c ",p->data); inorder(p->rchild); } } void postorder(TREE *p) //后序遍历 { if (p!=NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c ",p->data); } } void shu(TREE *p,int len) //数的形状{ if (p!=NULL) { shu(p->lchild,len+1); for (int i=1;i<=4*len;i++) { printf(" "); } printf("%c",p->data); printf("------\n"); shu(p->rchild,len+1); } } int shendu(TREE *p) //计算深度 { int l,r; if (p==NULL) { return 0; } l=shendu(p->lchild)+1; r=shendu(p->rchild)+1; if (l>=r) //左右子树比较return l; else 二叉树的基本操作及实现 二叉树的基本操作及实现的代码如下： #include 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 二叉树的应用研究 苏雨洁 （盐城工学院优集学院江苏盐城224001） 摘要：课堂上学习可以知道，二叉树可以简单明了的表示很多繁琐的信息数据。同时，二叉树在有很多方面有具体的应用。通过搜集各方面的资料发现，越来越多的领域开始选择使用二叉树模型来进行设计投资决策，并以此为平台，实现了很多的功能，本文结合了多领域的知识，给出了在生活方面，学习方面，以及理财投资方面的多种实例，并且加以概括和介绍。 关键词：二叉树；数据结构；结点；数组；期权 Study on the application of the binary tree SU Yujie (UGS College, Yancheng Institute of Technology, Yancheng, Jiangsu 224001) Abstract: Through learning in the classroom we can know, binary tree can be simple and clear to show many complicated data.At the same time,binary tree have specific applications in many aspects.Through the collection of information in many aspects,we can find that more and more fields start to use the binomial tree model to design,invest and making descisions. Use it as a platform ,achieving a lot of functions. This article incorporates knowledge from many fields and show a variety of examples in the aspects of living, learning, and financial investment.And summarize and introduce. Key words: Binary tree;Data structure; Node; Array; Option 0引言 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。逻辑上二叉树有五种基本形态：空二叉树，只有一个根结点的二叉树，右子树为空的二叉树，左子树为空的二叉树，完全二叉树；本文根据二叉树的性质形态，研究了二叉树在各个领域的应用实例，并且展望了二叉树在更多领域的应用。 1二叉树在学习上的应用 1.1二叉树平面坐标网及其应用 平面坐标系是把平面上的点映射为一对有序实数，坐标系是形数结合的桥梁。在图形，图像处理中，要处理的点数很多，能都有效的表示点就成为能否有效地处理图形图像的基本问题。数学上普遍使用切分方法，把一个复杂的几何对象近似表示成简单的几何对象的几何，集合中简单的几何对象位置就由其特征点（或点集）的坐标决定。把复杂的几何对象近似的 班级：数媒1101 学号：0305110125 课程名称：数据结构实验 实验名称：二叉树及其操作的实现 实验内容和目的： 内容：1. 创建二叉树； 2. 用递归方法实现二叉树的各种遍历。 目的：1.掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 2.掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍 历算法的递归实现和非递归实现。 实验步骤： 1.首先定义二叉树的存储形式； 2.用CreateBiTree( )构造二叉链表表示的二叉树T； 3. 用PreOrder ( bitree *t )、InOrder ( bitree *t)、PostOrder ( bitree * t )这三个函数 对二叉树依次进行先序、中序、后序遍历，并输出遍历序列。 实验代码/文件描述： #include "stdio.h" #include "stdlib.h" #define maxsize 64 #define null 0 typedef char datatype; typedef struct node { datatype data; struct node * lchild, * rchild; } bitree; bitree * bitr; bitree *Q[maxsize]; bitree *CREATREE( ) { char ch ; int front , rear ; bitree *root , *s ; root = null ; front = 1 ; rear = 0 ; ch = getchar( ) ; while ( ch != '#' ) { s = null ; if ( ch != '@' ) { s =(bitree*) malloc(sizeof(bitree)); s->data = ch ; s->lchild = null ;s->rchild =null; } rear ++; Q[rear] = s ; if (rear == 1 ) root = s ; else { if ( s && Q[front] ) if (rear%2==0 ) Q[front]->lchild = s ; else Q[front]->rchild = s ; if ( rear%2==1 ) front ++; } ch = getchar ( ) ; } return root ; } void PreOrder ( bitree *t ) { if ( t != null ) { printf("\t%c\n",t->data); PreOrder ( t->lchild ); PreOrder ( t->rchild ); } } void InOrder ( bitree *t) { if ( t != NULL ) { InOrder ( t->lchild ); printf("\t%c\n", t->data); InOrder ( t->rchild ); } } 郑州轻工业学院数据结构实验报告 题目 学生姓名 学号 专业班级 完成时间 2016年月日 目录 一、系统功能介绍 (2) 二、需求分析 (2) 三、概要设计 (2) 四、详细设计 (5) 五、调试分析 (8) 六、使用说明 (8) 七、测试结果 (9) 八、心得体会 (10) 九、附录（程序代码） (11) 一、系统功能介绍 该系统主要功能是实现二叉树的定义和基本操作，包括定义二叉树的结构类型以及各个操作的具体函数的定义和主函数的定义。 各操作主要包括：初始化二叉树、按先序次序建立二叉树、检查二叉树是否为空、前序、中序、后序遍历树的方式、求树的深度、求树的结点数目、清空二叉树等九个对树的操作。 二、需求分析 本系统通过函数调用实现二叉树初始化，建立二叉树，检查树空与否，用前序、中序、后序遍历二叉树，求树的深度，求树的结点数目，清空二叉树等功能。 1）输出的形式和输出值的范围：在选择操作中，都以整型（数字）选择操作，插入和输出的数值都是char类型的字符； 2）输出的形式：在每次操作后，都会提示操作是否成功或者操作的结果； 3）程序达到的功能：完成初始化、检查是否为空、请空、遍历、求树的深度、求树的结点数目等功能； 4)测试数据设计： A,按先序次序建立二叉树。依次输入a,b,c,d,e,f,g.建立二叉树。 B,分别按先序，中序和后序遍历输出二叉树中的结点元素。 C,求树的高度和结点数。 三、概要分析 为了实现上述功能，定义二叉树的抽象数据类型。 ADT BinTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: 若D=￠，称BinTree为空二叉树 若D≠￠,则R={H},H是如下的二元关系； （1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱； （2）若D-{root}≠￠，则存在D-{root}={D1,Dr},且D1∩Dr=￠； （3）若D≠￠，则中存在唯一的元素x1, 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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．能够利用二叉树解决具体问题。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉软件：DOS或Windows操作系统+Turbo C； 三、实验要求 ⒈要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的 操作。 ⒉输入数据：树中每个结点的数据类型设定为字符型。 3．设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历，求该二叉树所有叶子结点总数。 四、实验内容 附：参考程序为类C语言程序，非标准C语言程序，需要进行相应的修改。 二叉链表结构如下：P134 typedef struct lnode {char data; struct lnode *lchild,*rchild; }lnode,*tree; 1．建树子函数P137 status creat(tree &t) {//按先序次序输入二叉树中结点的值，’.’字符表示空树 scanf(&ch); if(ch=='.') t=null; else {t=(tree)malloc(sizeof(lnode)); t->data=ch; creat(t->lchild); creat(t->rchild);} return ok; } 2．先序遍历子函数P136 preorder(tree t) { if(t!=null) {printf(t->data); preorder(t->lchild); preorder(t->rchild); } } 3．后序遍历子函数P136 postorder(tree t) {if(t!=null) {postorder(t->lchild); postorder(t->rchild); printf(t->data); } } 五、思考题 1. 已知二叉树先序和中序序列，唯一地构造一棵二叉树并且验证其正确性。 2. 建立一个二叉树，并且按层次遍历操作。 六、报告要求 1．报告要求用专门的实验报告纸书写，字迹清晰，格式规范。 2．报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求。 实验四-二叉树操作实现 实验四二叉树操作实现 实验日期：2017 年 4 月20 日 实验目的及要求 1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； 2. 重点掌握二叉树的创建、遍历及求深度等算法； 3. 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 实验内容 键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。 二叉树结点类型定义： typedef char datatype; typedef struct tnode{ datatype data; struct tnode *lchild,*rchild; } BiTNode,*BiTree; 任务 1．题目要求 创建一个程序文件sy4.cpp，自定义相应函数完成以下操作： （1）void visit(BiTree p) /*输出p指针指向的结点*/ （2）void Preorder(BiTree T) /*前序遍历*/ （3）void Inorder(BiTree T) /*中序遍历*/ （4）void Postorder(BiTree T) /*后序遍历*/ （5）BiTree CreateTree( ) /*以前序遍历的顺序建立二叉树*/ （6）int deep(BiTree T) /*求二叉树深度*/ （7）int leaf(BiTree T) /*求叶子结点数*/ （8）int OneChild(BiTree T) /*求1度结点数*/ （9）int TwoChild(BiTree T) /*求2度结点数*/ （10）void Exchange(BiTree T) /*二叉树左右子树交换*/ （11）BiTree InorderLastNode(BiTree T); /*找二叉树中序遍历最后一个结点*/ 2．请回答下列问题 （1）在n个结点二叉树的二叉链表存储中，其指针域的总数为2n 个，其中n-1 个用于链接孩子结点，n+1 个空闲着。 （2）在二叉链表存储中，数据域值为data，左右子树的指针分别为left和right，则判断： 指针p所指结点为0度结点的条件是p->left==NULL&&p->right==NULL ；指针p所指结点为1度结点的条件是(p->left==NULL&&p->right!=NULL)||(p->left!=NULL&&p->right==NULL) ； 指针p所指结点为2度结点的条件是p->left!=NULL&&p->right!=NULL 。（3）T为二叉树的根的地址，该树是空二叉树满足条件：T==NULL 。 3．sy14.cpp源程序清单（含必要的注释） #include 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include public class Tree if(root==null) return false; if(data!=null) { if(!isEmptyTree() && root.equals(data)) return true;//如果树不空，而且根等于data返回true if(!leftChild.isEmptyTree() && leftChild.exists(data)) return true; if(!right.isEmptyTree() && right.exists(data)) return true; } return false; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Tree 数据结构程序报告(平衡二叉树的操作) 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 1.需求分析 1．建立平衡二叉树并进行创建、查找、插入、删除等功能。 2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。 3．测试数据：自选数据 2.概要设计 1.抽象数据类型定义： typedef struct BSTNode { int data; int bf; //节点的平衡因子 struct BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; void CreatBST(BSTree &T); //创建平衡二叉树 void R_Rotate(BSTree &p); //对以*p 为根的二叉排序树作左旋处理 void L_Rotate(BSTree &p); //对以*p 为根的二叉排序树作左旋处理 void LeftBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理bool InsertA VL(BSTree &T,int e,bool &taller); //插入结点e bool SearchBST(BSTree &T,int key); //查找元素key是否在树T中 void LeftBalance_div(BSTree &p,int &shorter); void RightBalance_div(BSTree &p,int &shorter); 实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 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); } 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014-12-18 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下： ①void InitBTree( BTreeNode *&BT ); //初始化二叉树BT ②void CreateBTree( BTreeNode *&BT, char *a ); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree( BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值 ⑤int FindBTree( BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT); //后序遍历二叉树BT实验三 二叉树的基本操作实现及其应用
二叉树的基本 操作
二叉排序树的建立及遍历的实现
实验三二叉树的基本操作
二叉树的建立及其应用程序代码
二叉树的基本操作及实现.cpp
数据结构——二叉树基本操作源代码
二叉树的应用研究
二叉树及其操作的实现
二叉树基本操作+数据结构+实验报告
数据结构实验三——二叉树基本操作及运算实验报告
实验5 二叉树建立及应用
实验四-二叉树操作实现
二叉树基本操作经典实例
java二叉树的建立与应用代码
数据结构程序报告(平衡二叉树的操作)
数据结构二叉树实验报告
实验10 二叉树的基本操作
相关主题
文本预览