实验四 二叉树的操作
班级:计算机1002班
姓名:**
学号:**
完成日期:20XX.6.14
题目:对于给定的一二叉树,实现各种约定的遍历。
一、实验目的:
(1)掌握二叉树的定义和存储表示,学会建立一棵特定二叉树的方法;
(2)掌握二叉树的遍历算法(先序、中序、后序遍历算法)的思想,并学会遍历算法的递归实现和非递归实现。
二、实验内容:构造二叉树,再实现二叉树的先序、中序、后序遍历,最后统计二叉树的深度。
三、实验步骤:
(一) 需求分析
1. 二叉树的建立首先要建立一个二叉链表的结构体,包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树,所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程,遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法,这个过程需要按照不同的遍历的方法,先输出根结点还是先输出左右孩子,可以用选择语句来实现。
2.程序的执行命令为:
1)构造结点类型,然后创建二叉树。
2)根据提示,从键盘输入各个结点。
3)通过选择一种方式(先序、中序或者后序)遍历。
…… …… 余下全文
实验六、树和二叉树的操作
一、实验目的
1.进一步掌握树的结构及非线性特点,递归特点和动态性。
2.进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法。
二、实验内容
二叉树的实现和运算
三、实验要求
1.用C++/C完成算法设计和程序设计并上机调试通过。
2.撰写实验报告,提供实验结果和数据。
3.分析算法,并简要给出算法设计小结和心得。
四、程序实现
#include<iostream.h>
#include<stdlib.h>
typedef char DataType;
typedef struct BitNode
{
DataType data;
struct BitNode *lchild,*rchild;
}*BitTree;
void BinTreeInit(BitTree &BT)//初始化二叉树,即把树根指针置空
{
BT=(BitTree)malloc(sizeof(BitNode));
BT->data=NULL;
cout<<"二叉树初始化成功!"<<endl;
…… …… 余下全文
宁波工程学院电信学院计算机教研室
实验报告
1、熟悉二叉树树的基本操作。
2、掌握二叉树的实现以及实际应用。
3、加深二叉树的理解,逐步培养解决实际问题的编程能力。
1台WINDOWS环境的PC机,装有Visual C++ 6.0。
【问题描述】
现需要编写一套二叉树的操作函数,以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括:
1> 创建二叉树CreateBTNode(*b,*str):根据二叉树括号表示法的字符串*str生成对应的链式存储结构。
2> 输出二叉树DispBTNode(*b):以括号表示法输出一棵二叉树。
3> 查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4> 求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空,则其高度为0;否则,其高度等于左子树与右子树中的最大高度加l。
…… …… 余下全文
XX学院实验报告
五、实验总结和思考:(填写收获和体会,分析成功或失败的原因)
收获:只有通过不断练习,才能获取经验,避免下次犯同样的错误!
成功和失败: 在实验过程中,遇到了一些细节性的问题,不好寻找,导致结果错误。
结果:找到了问题所在,发现了一些平时不曾注意的问题。
附件:(源代码)
/* 说明
1、树的元素类型为字符形;
2、实现对二叉树的先序遍历操作;
3、实现对二叉树的中序遍历操作;
4、实现对二叉树的后序遍历操作;
5、求二叉树的深度;
6、求二叉树的叶结点数;
7、将二叉树中所有结点的左、右子树相互交换;
*/
#include "stdio.h"
#include "conio.h"
#define OVERFLOW -1
typedef char telemtype;
…… …… 余下全文
(1)问题描述:①用先序递归过程建立二叉树 (存储结构:二叉链表)。
输入数据按先序遍历所得序列输入,当某结点左子树或右子树为空时,输入‘*’号,如输入abc**d**e**得到的二叉树为:
…… …… 余下全文
一 实验题目
实现二叉树的基本操作的代码实现
二 实验目的
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,<root,x1>∈H,且存在D1上的关系H1 ?H;若Dr≠Φ,则Dr中存在惟一的元素xr,<root,xr>∈H,且存在上的关系Hr ?H;H={<root,x1>,<root,xr>,H1,Hr};
// (4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。
…… …… 余下全文