数据结构 实验四 二叉树的基本操作

实验四二叉树的基本操作

一、实验目的：

（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；

（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想；

（3）掌握二叉树和叶子数、深度之间的关系及联系。

二、实验内容：

构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。

三、实验步骤：

(一) 需求分析

1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。

2．程序的执行命令为：

1）构造结点类型，然后创建二叉树。

2）根据提示，从键盘输入各个结点。

3）通过选择一种方式（先序、中序或者后序）遍历。

4）输出结果，结束。

(二)概要设计

1.二叉树的二叉链表结点存储类型定义

typedef struct Node {

DataType data;

struct Node *LChild;

struct Node *RChild;

}BitNode,*BitTree;

2.建立如下图所示二叉树：

3.本程序包含六个模块

1) 主程序模块

2)先序遍历模块

3)中序遍历模块

4)后序遍历模块

5）叶子数模块

6）深度模块

四、测试结果

1. 进入演示程序后的显示主界面：

请输入二叉树中的元素；

先序、中序、后序遍历和叶子数、深度分别输出结果。

2.测试结果

以扩展先序遍历序列输入，其中#代表空子树：ABC##DE#G##F### 先序遍历序列为：ABCDEGF

中序遍历序列为：CBEGDFA

后序遍历序列为：CGEFDBA

此二叉树的叶子数为：3

此二叉树的深度为：5

3.程序运行结果截图：

五、源代码

#include

#include

//节点声明，数据域、左孩子指针、右孩子指针

typedef struct BiTNode{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//先序建立二叉树

BiTree CreateBiTree(){

char ch;

BiTree T;

scanf("%c",&ch);

if(ch=='#')T=NULL;

else{

T = (BiTree)malloc(sizeof(BiTNode));

T->data = ch;

T->lchild = CreateBiTree();

T->rchild = CreateBiTree();

}

return T;//返回根节点

}

//先序遍历

void PreOrderTraverse(BiTree T){ if(T){

printf("%c",T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

}

}

//中序遍历

void InOrderTraverse(BiTree T){ if(T){

InOrderTraverse(T->lchild);

printf("%c",T->data);

InOrderTraverse(T->rchild);

}

}

//后序遍历

void PostOrderTraverse(BiTree T){ if(T){

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

printf("%c",T->data);

}

}

//求二叉树的深度

int Depth(BiTree T)

{

int dep=0,depl,depr;

if(!T) dep=0;

else

{

depl=Depth(T->lchild);

depr=Depth(T->rchild);

dep=1+(depl>depr?depl:depr);

}

return dep;

}

//计算叶子节点数

int leef(BiTree T){

if(!T)

return 0;

else

if(T->lchild ==NULL&&T->rchild ==NULL)

return 1;

else

return leef(T->lchild) +leef(T->rchild );

}

//主函数

void main(){

BiTree T;

printf("请按先序输入序列（其中的“#”表示空）\n\n");

T = CreateBiTree();//建立二叉树

printf("\n先序遍历结果为：");

PreOrderTraverse(T);//先序遍历输出

printf("\n\n中序遍历结果为：");

InOrderTraverse(T);//中序遍历输出

printf("\n\n后序遍历结果为：");

PostOrderTraverse(T);//后序遍历输出

printf("\n\n二叉树深度为：%d\n",Depth(T)); Depth(T);//计算二叉树深

printf("\n叶子节点数为：%d\n\n",leef(T)); leef(T);//计算叶子节点数

}

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

数据结构中二叉树中序遍历的教学分析

数据结构中二叉树中序遍历的教学分析 袁宇丽,　胡　玲 Ξ(内江师范学院计算机与信息科学系,　四川　内江　641112) 摘　要:数据结构的教学应注重方法的应用,在二叉树的中序遍历中使用投影法可以使遍历过程简单化, 再由其中的一种遍历递归算法(先序)推导得到另外两种(中序,后序)的遍历递归算法,让学生加深对整个遍 历过程的了解与掌握。 关键词:数据结构;二叉树;遍历;算法 中图分类号:G 642　文献标识码:A 文章编号:1671-1785(2006)04-0109-03 1　引言 《数据结构》是计算机学科的一门专业技术基础课,也是计算机程序设计的重要理论技术基础课。目的是在于让学生学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据结构选择适当的逻辑结构,存储结构及其相应的算法;并初步掌握算法的时间分析和空间分析的技术;培养学生进行复杂程序设计的能力和数据抽象的能力。但从学生角度而言,在学习该门课程时普遍反映较难,总觉得课程内容抽象,不易理解,好些具体算法不知从何下手。针对以上情况,任课教师在讲授该门课程时更应注重方法的应用,从多角度,多侧面展现知识点,化抽象为具体,化特殊为一般,不应只局限于教材上的一种解题模式,应结合自己的理解,补充新方法,这样才能更好的拓宽学生的思路,达到化难为易,举一反三的效果。下面以具体实例说明。 2　二叉树中序遍历的投影法 在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题,即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等。遍历对线性结构来说,是一个容易解决的问题。而对二叉树则不然,由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,从而便于访问。 回顾二叉树的定义可知,二叉树是由三个基本单元组成:根结点、左子树、右子树。因此,若能依次遍历这三部分,便是遍历了整个二叉树。若限定先左后右的顺序,则分为三种情况:先(根)序遍历,中(根)序遍历,后(根)序遍历。二叉树的遍历及其应用是数据结构中一个很重要的知识点,要求学生能根据所给二叉树得到相应的三种遍历序列(前序,中序,后序),并能写出这三种遍历算法。以中序遍历而言,教材[1]结合图给出了中序遍历过程示意图,并具体分析了该遍历的递归执行过程。但递归调用及返回对学生来说本身就是一个较难掌握的知识,往往出现进入递归后不知怎样层层返回,所图1　二叉树 以书上在说明二叉树的中序遍历时借用递归调用与返回的 方法向学生展示整个遍历过程对初学者总感觉有一定难度。 我们在这里补充一种教材上没有提到的二叉树中序遍历的 直观方法:投影法。分析中序遍历的实质,是按先中序访问左子树,再访问根结点,最后中序访问右子树的顺序进行的。直 观上想,处于二叉树最左下方的结点应该是第一个要访问的结点,再结合二叉树本身的构造特点,是有严格的左右子树 之分的,所以投影法就是根据二叉树的结构特征得来的。对 于一棵二叉树,从根结点所在的层开始,将所有非空左子树 完全位于当前根结点的左方,将所有非空右子树完全位于当? 901?第21卷第4期N o 14V o l 121 内江师范学院学报JOU RNAL O F N E I J I AN G T EA CH ER S COLL EGE 收稿日期:2005-11-11 　作者简介:袁字丽(1979-),女,四川自贡人,内江师范学院助教,硕士。

数据结构二叉树实验报告

实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include #include #include #define OK 1 #define ERROR 0 typedef struct TNode//结构体定义 {

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）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

实验三 二叉树的基本操作实现及其应用

二叉树的基本操作实现及其应用 一、实验目的 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<<"二叉树初始化成功!"<>ch; if(ch=='#') BT=NULL; else { if(!(BT=(BitTree)malloc(sizeof(BitNode)))) exit(0);

数据结构 二叉树练习题答案

数据结构第6章树和二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树 （若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。

（应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31)

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

二叉树的基本操作实验

实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、实验前的准备工作 1、掌握树的逻辑结构。 2、掌握二叉树的逻辑结构和存储结构。 3、掌握二叉树的各种遍历算法的实现。 一实验分析 本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。 二概要设计 功能实现

1.int CreatBiTree(BiTree &T) 用递归的方法先序建立二叉树, 并用链表储存该二叉树 2.int PreTravel(BiTree &T) 前序遍历 3. int MidTravel(BiTree &T) 中序遍历 4.int PostTravel(BiTree &T) 后序遍历 5.int Depth(BiTree &T) //计算树的深度 6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。 7. int exchang(BiTree &T) 交换左右子树，利用递归，当有左右孩子时才交换 三详细设计 #include #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

数据结构实验报告-二叉树的实现与遍历

《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师

一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验-二叉树的操作

******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include #include #define M 100 typedef struct node //二叉链表节点结构 {int data; //数据域 struct node *lchild,*rchild; //左孩子右孩子链 }bitree; bitree *que[M]; //定义一个指针数组，说明队列中的元素bitree 指针类型 int front=0, rear=0; //初始化循环列队 bitree *creat() //建立二叉树的递归算法 {bitree *t; int x; scanf("%d",&x); if(x==0) t=NULL; //以x=0 表示输入结束 else {t=malloc(sizeof(bitree)); //动态生成节点t，分别给节点t 的数据域，t->data=x; //左右孩子域赋值，给左右孩子赋值时用到 t->lchild=creat(); // 了递归思想 t->rchild=creat(); }

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);

正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

数据结构之二叉树概述

数据结构之二叉树 第一篇：数据结构之链表 第二篇：数据结构之栈和队列 在这篇文章里面，我们主要探讨和树相关的话题。 首先，我们来对树进行定义：树是n（n>= 0）个节点的有限集。在任何一个非空树中：（1）有且仅有一个特定的称为“根”的节点；（2）当n>1时，其余节点可分为m（m>0）个互相相关的有限集T1、T2、T3……，其中每一个集合本身又是一棵树，并且称为根的子树。 对于我们这篇文章里讨论的二叉树，它是一种特殊的树形结构，每个节点至多只有两颗子树，并且子树有左右之分，其次序不能随意颠倒。 接下来，我们使用java代码来定义一棵树： 1public class BinNode { 2private int m_Value; 3private BinNode m_Left; 4private BinNode m_Right; 5public void setValue(int m_Value) { 6this.m_Value = m_Value; 7 } 8public int getValue() { 9return m_Value; 10 } 11public void setLeft(BinNode m_Left) { 12this.m_Left = m_Left; 13 } 14public BinNode getLeft() { 15return m_Left; 16 } 17public void setRight(BinNode m_Right) { 18this.m_Right = m_Right; 19 } 20public BinNode getRight() { 21return m_Right; 22 } 23 24public boolean isLeaf() 25 { 26return m_Left == null && m_Right == null; 27 } 28 }

数据结构实验报告之树与二叉树

学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件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 << " "; } } 运行截图：

数据结构实验报告—二叉树

算法与数据结构》课程实验报告

一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验-二叉树的操作

******************************* 实验题目：二叉树的操作 实验者信息：班级 13007102,姓名 庞文正，学号 1300710226 实验完成的时间 3:00 ****************************** 一、 实验目的 1, 掌握二叉树链表的结构和二叉树的建立过程。 2, 掌握队列的先进先出的运算原则在解决实际问题中的应用。 3, 进一步掌握指针变量、指针数组、动态变量的含义。 4, 掌握递归程序设计的特点和编程方法。 二、 实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。 （所谓层次遍历，是 指从二叉树的根结点开始从上到下逐层遍历二叉树， 在同一层次中从左到右依次访问各个节 点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加 深对算法的理解。 三、 算法设计与编码 1. 本实验用到的理论知识 总结本实验用到的理论知识， 实现理论与实践相结合。 总结尽量简明扼要， 并与本次实验密 切相关，最好能加上自己的解释。 本算法要采用一个循环队列 que,先将二叉树根结点入队列，然后退队列，输出该 结点；若它 有左子树，便将左子树根结点入队列； 若它有右子树，便将右子树根结点入队列， 直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。 2. 算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include #include #define M 100 typedef struct node //二叉链表节点结构 {int data; // 数据域 struct node *lchild,*rchild; }bitree; bitree *que[M]; //定义一个指针数组，说明队列中的元素 int front=0, rear=0; 〃初始化循环列队 bitree *creat() 〃建立二叉树的递归算法 {bitree *t; int x; scanf("%d”,&x); if(x==0) t=NULL; 〃以 else {t=malloc(sizeof(bitree)); t->data=x; t->lchild=creat(); t->rchild=creat(); //左孩子右孩子链 x=0表示输入结束 bitree 指针类型 〃动态生成节点t,分别给节点t 的数据域， //左右孩子域赋值，给左右孩子赋值时用到 // 了递归思想

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;