当前位置：文档之家 › 数据结构实验报告二二叉树实验

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

  • 格式：doc
  • 大小：5.01 MB
  • 文档页数：4

第 1 页 共 4 页 实验报告

课程名称：数据结构

实验编号

及实验名称 实验二：二叉树实验 系 别

姓 名 学 号 班 级

实验地点 实验日期 实验时数

指导教师 同组其他成员 成 绩

一、实验目的及要求

在二叉链存储结构下，设计二叉树结点类，并在此基础上设计二叉树类，再通过调用二叉树类的成员函数，构造并遍历二叉树、完成指定应用。从而充分理解二叉树的二叉链存储结构，掌握在这种存储结构下二叉树的构造及各种基本操作、应用的实现。

二、实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）

1．使用软件：JDK，Eclipse

2．实验设备：装有Windows 7的个人计算机

三、实验内容及步骤（包含简要的实验步骤流程）

采用二叉树的二叉链存储结构，完成如下功能：

（1）编写一个Java程序，设计并实现二叉树的结点类。

（2）编写一个Java程序，在二叉树的结点类的基础上，设计并实现二叉树类, 其中包含由二叉树的括号表示串创建二叉链表的算法，先根遍历递归算法、中根遍历递归算法、后根遍历递归算法算法，层序遍历算法，由后根遍历序列和中根遍历序列建立二叉树的算法，统计二叉树中结点个数算法，求二叉树深度算法。

（3）在纸上画一棵含有不少于10个结点的二叉树，要求二叉树中包含只有左孩子结点的结点、只有右孩子结点的结点、既有左孩子结点又有右孩子结点的结点。并对此二叉树进行先根、中根、后根、层序遍历，写下各种遍历序列。

（4）编写主程序，输入（3）中二叉树的括号表示字符串，并由此建立这棵二叉树的二叉链表bt1。

（5）在主程序中调用各种（先根、中根、后根、层次）遍历算法输出bt1的各种遍历序列，与（3）中写下的各遍历序列对照看是否正确；输出bt1的结点个数和深度并检查正确性。

（6）在主程序中根据（5）中得到的中根、后根遍历序列串，调用由后根遍历序列和中根遍历序列建立二叉树的算法，建立二叉链表bt2。

（7）输出bt2的先根、层次遍历序列、结点个数及二叉树的深度，并与bt1进行比较。

（8）多次运行程序，对不同的二叉树验证程序的运行结果。

第 2 页 共 4 页 四、实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）

第 3 页 共 4 页 五、实验总结（包括心得体会、问题回答及实验改进意见，可附页）

这次实验主要是建立二叉树，和二叉树的先序、中序、后续遍历算法。通过这次实验，我巩固了二叉树这部分知识,从中体会理论知识的重要性。在做实验之前，要充分的理解本次实验的理论依据，这样才能达到事半功倍的效果。如果在没有真正理解实验原理之盲目的开始实验，只会浪费时间和精力。例如进行二叉树的遍历的时候，要先理解各种遍历的特点。先序遍历是先遍历根节点，再依次先序遍历左右子树。中序遍历是先中序遍历左子树，再访问根节点，最后中序遍历右子树。而后序遍历则是先依次后续遍历左右子树，再访问根节点。掌握了这些，在实验中我们就可以融会贯通，举一反三。其次要根据不光要懂得代码的原理，还要对题目有深刻的了解，要明白二叉树的画法，在纸上先进行自我演练，对照代码验证自己写的正确性。

第 4 页 共 4 页 六、教师评语

1． 完成所有规定的实验内容，实验步骤正确，结果正确；

2． 完成绝大部份规定的实验内容，实验步骤正确，结果正确；

3． 完成绝大部份规定的实验内容，实验步骤基本正确，结果基本正确；

4． 基本完成规定的实验内容，实验步骤基本正确，所完成的结果基本正确；

5． 未能很好地完成规定的实验内容或实验步骤不正确或结果不正确。

评定等级为：

教师签名：

合集下载

数据结构二叉树实验报告

数据结构二叉树实验报告

一 、实验目的和要求

(1)掌握树的相关概念，包括树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节

点、树的深度、森林等定义。

(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。

(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

(4)掌握二叉树的性质。

(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。

(6)重点掌握二叉树的基本运算和各种遍历算法的实现。

(7)掌握线索二叉树的概念和相关算法的实现。

(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码的产生方法。

(9)掌握并查集的相关概念和算法。

(10)灵活运用二叉树这种数据结构解决一些综合应用问题。

二、实验内容

注：二叉树b为如图7-123所示的一棵二叉树

图7-123+

实验7.1 编写一个程序algo7-1.cpp,实现二叉树的各种运算，并在此基础上设计一个程序

exp7-1.cpp完成如下功能：

(1)输出二叉树b;

(2)输出H节点的左、右孩子节点值；

(3)输出二叉树b的深度；

(4)输出二叉树b的宽度；

(5)输出二叉树b的节点个数；

(6)输出二叉树b的叶子节点个数。

实验7.2设计一个程序exp7-2.cpp,实现二叉树的先序遍历、中序遍历和后序遍历和非递归算法，

以及层次变量里的算法。并对图7-123所示的二叉树b给出求解结果。

b+

A

C

F G

I

K

L+

N M+ E+

Hd

J D ₄ B 实验7.3对如图7-123所示的二叉树，设计一个程序exp7-3.cpp,完成如下功能：

(1)输出所有的叶子节点；

(2)输出所有从叶子节点到根节点的路径；

(3)输出(2)中的第一条最长的路径。

三 、 实验过程描述

实现二叉树的各种的基础程序algo7-1.cpp如下：

的1501-1.CPP

include《stdio.h》

数据结构实验报告——中序遍历二叉树

数据结构实验报告——中序遍历二叉树

班级：380911班 学号：57000211 姓名：徐敏

实验报告

一，实验目的：

·掌握二叉树的链式存储结构；

·掌握构造二叉树的方法；

·加深对二叉树的中序遍历的理解；

二，实验方法：

·用递归调用算法中序遍历二叉树。

三，实验步骤：

·通过链式存储建立一颗二叉树。

·设计一个算法实现中序遍历二叉树。

四，具体实验步骤：

#include

#include

#define LEFT 0

#define RIGHT 1

#define TRUE 1

#define FALSE 0

typedef struct _BTNODE{

char c;

struct _BTNODE *lchild;

struct _BTNODE *rchild;

}BTNODE,*PBTNODE;

void PrintBTree(PBTNODE p,int depth);

void ConstructBTree(PBTNODE p);

void InorderTraverse(PBTNODE p);

void main(){

PBTNODE p;

p=(PBTNODE)calloc(1,sizeof(BTNODE));

printf("Input the data:");

ConstructBTree(p);

PrintBTree(p,0);

printf("Now InorderTraverse:");

InorderTraverse(p);

printf("\nPress any key to continue...");

getchar();

}

void PrintBTree(PBTNODE p,int depth){ 班级：380911班 学号：57000211 姓名：徐敏

int i;

if(p==NULL){

return;

}else{

数据结构实验六 二叉树的创建

数据结构实验六 二叉树的创建

实验六 二叉树的创建与遍历

实验目的：

通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。

实验内容与要求：

基于二叉链表存储结构实现二叉树的基本运算，要求：

⑴ 建立非空二叉树（方法不唯一，可以选择几种方式创建）；

⑵ 实现二叉树的先、中、后序递归遍历算法；

⑶ 实现二叉树的非递归先（或中、或后）序遍历算法中的一种；

⑷ 实现二叉树的层序遍历算法；

⑸ 自主完成二叉树的其他操作（本小题选做）。

记录运行结果并对递归算法和非递归算法的效率加以分析。

备注：考虑到大部分同学对于指针内容的掌握程度有所不同，故本次作业用时2周，在第11周上机结束后的周五提交。

//信计1202 李洋 1130112207 程序实现二叉链表的存储结构实现二叉树的基本操作

#include

#include

#define maxszie 100

#define S 0

#define N 0

typedef struct node

{

char data;

int center;

struct node *lchild;

struct node *rchild;

}btnode;

void createbtree(btnode * bt)

{ char ch;

ch=getchar();

if(ch==',')

{ S--;

bt=NULL;

}

else

{

S++;

if(S>=N)

N=S;

bt=(btnode *)malloc(sizeof(btnode));

bt->data=ch;

bt->center=S;

createbtree(bt->lchild);

createbtree(bt->rchild);

}

}

void visit(btnode *root)

{

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

[精品]【数据结构】二叉树实验报告

[精品]【数据结构】二叉树实验报告

[精品]【数据结构】二叉树实验报告

二叉树实验报告

一、实验目的：

1.掌握二叉树的基本操作；

2.理解二叉树的性质；

3.熟悉二叉树的广度优先遍历和深度优先遍历算法。

二、实验原理：

1.二叉树是一种树形结构，由n(n>=0)个节点组成；

2.每个节点最多有两个子节点，称为左子节点和右子节点；

3.二叉树的遍历分为四种方式：前序遍历、中序遍历、后序遍历和层次遍历。

三、实验环境：

1.编程语言：C++；

2.编译器：Dev-C++。

四、实验内容：

1.定义二叉树节点结构体：

struct BinaryTreeNode

{

int data; // 节点数据

BinaryTreeNode *leftChild; // 左子节点指针

BinaryTreeNode *rightChild; // 右子节点指针

};

2.初始化二叉树：

queue q; // 使用队列存储节点 q.push(root);

int i = 1; // 创建子节点

while (!q.empty() && i < length)

{

BinaryTreeNode *node = q.front();

q.pop();

if (data[i] != -1) // 创建左子节点