文档介绍：中国矿业大学计算机学院实验报告
课程名称 数据结构 试验名称 树、图的实现与应用
班级 ********** 姓名 ****** 学号 *******
仪器组号 **** 实验日期 ********
一、实验目的
1 理解树结构的逻辑特性
2 熟练掌握二叉树的逻辑结构特性及各种存储方法
3 熟练掌握二插树的各种基本操作,尤其是三种遍历
4 熟练掌握图的存储结构
5 掌握图的邻接矩阵和邻接表表示分别进行深度和广度优先搜索遍历的
算法。
6 了解图的最小生成树算法。
二、实验要求
1 实验之前认真准备,编写好源程序。
2 实验中认真调试程序,对运行结果进行分析,注意程序的正确性和健壮
性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题
1、给定一棵用链表表示的二叉树,其根指针为 root ,试写出求二叉树结
点数目。
2、对图的邻接矩阵和邻接表表示分别进行深度优先搜索遍历算法的实现。
四、程序清单和运行结果
1、
#include<>
#include<>
#include<>
template <class T>
struct BinTreeNode {//二叉树结点类定义
T data; //数据域
BinTreeNode<T> *leftChild, *rightChild;
//左子女、右子女链域
BinTreeNode ():leftChild(NULL),rightChild(NULL){}
//构造函数
BinTreeNode (T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r =
NULL)
{ data = x; leftChild = l; rightChild = r; }};
template <class T>
class BinaryTree { //二叉树类定义
public:
BinaryTree (T value) : RefValue(value), root(NULL) // 构造函数
{
CreateBinTree (cin,root);
}
BinaryTree (BinaryTree<T>& s);
//复制构造函数
~BinaryTree () { destroy(root); } // 析构函数
bool IsEmpty () { return root == NULL;}// 判二叉树空否
int Height () { return Height(root); } //求树高度
int Size (){ return Size(root); } // 求结点数
BinTreeNode<T> *getRoot () const { return root; }// 取根
void preOrder (void (*visit) (BinTreeNode<T> *p)) // 前序遍历
{ preOrder (root, visit); }
void inOrder (void (*visit) (BinTreeNode<T> *p)) //中序遍历
{ inOrder (root, vi