文档介绍：该【数据结构实验报告树形数据结构实验】是由【guoxiachuanyue013】上传分享，文档一共【69】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实验报告树形数据结构实验】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验报告书
课程名:
数据结构
题
目:
树形数据结构实验(1)
班
级:
学
号:
姓
名:
评语
成绩:指导教师:
批阅吋间:年
第2页
第1页
一、目的与要求
1)熟练掌握二叉树的二叉链表表示创建算法与实现;
2)熟练掌握栈的前序、中序与后序递归遍历算法与实现;
3)熟练掌握前序、中序与后序遍历线索二叉树的基本算法与实现;
4)按照实验题目要求独立正确地完成实验内容(提交程序清单及相关实验数据与运行结果);
5)认真书写实验报告,并按时提交。
二、实验内容或题目
1)创建二叉树:广义表式创建与先序创建;
2)遍历二叉树:先,中,后,层序遍历,广义表式遍历,凹凸式遍历;
3)二叉树属性:深度,宽度,结点数,叶子结点数
4)二叉树路径:叶子结点到根结点的路径;
5)二叉树线索:中序线索二叉树;
6)二叉树置空:清空二叉树。
三、实验步骤与源程序
1)
#include<>
#include<>
#include<>
#include<>
#include<>
/**********************************
对象--
二叉数
****************
****************
第2页
第1页
typedefcharElemType;//定义元素类型
#defineMAXSIZE100//确定二叉树的最大结点数
/******************************
叉数
的结点
类定义
******************************
classBTreeNode
private:
intltag,rtag;//线索标记
BTreeNode*left;//左子树指针
BTreeNode*right;//右子树指针
public:
ElemTypedata;//数据域
//构造函数
BTreeNode()
ltag=0;
rtag=0;
left=NULL;
right=NULL;
//带参数初始化的构造函数
BTreeNode(ElemTypeitem,intltag1,intrtag1,BTreeNode*left1,BTreeNode*right1)
data=item;
ltag=ltag1;
第2页
第1页
rtag=rtag1;
第2页
第1页
//递归创建二叉树,被函数CreateBTree1调用
第2页
//递归创建二叉树,被函数CreateBTree1调用
第2页
left=left1;
right=right1;
BTreeNode*&Left()//返回结点的左孩子
returnleft;
//返回结点的右孩子
BTreeNode*&Right()
returnright;
friendclassBinaryTree;//二叉树类为二叉树结点类的友元类
/**********************************
叉数
的类定义
*******************************
classBinaryTreeprivate:
BTreeNode*root;
public:
//
BinaryTree(){root=NULL;}
//判断二叉树是否为空
boolBTreeEmpty(){returnroot==NULL;}
/****************************
创建
叉数的相关成员函数
***********************
//按照二叉树的广义表表示创建二叉树
voidCreateBTree1();
//递归创建二叉树,被函数CreateBTree1调用
第2页
//递归创建二叉树,被函数CreateBTree1调用
第2页
voidCreate1(BTreeNode*&BT);
//按一定次序输入二叉树中结点的值(一个字符),空格表示空树voidCreateBTree2(intmake);
//递归先序创建二叉树,被函数CreateBTree2调用
voidGreate2(BTreeNode*&BT,intmark);
//复制二叉树
voidBTreeCopy(BTreeNode*&root,BTreeNode*&BT);
/****************************
遍历二叉数的相关成员函数
***********************
//按任一种遍历次序输出二叉树中的所有结点
voidTraverseBTree(intmark);
//用于遍历的递归函数,被函数TraverseBTree调用voidTraverse(BTreeNode*&BT,intmark);
//先序遍历的递归函数
voidPreOrder(BTreeNode*&BT);
//先序遍历的非递归函数一
voidPreOrder_N1(BTreeNode*&BT);
//先序遍历的非递归函数二
voidPreOrder_N2(BTreeNode*&BT);
//中序遍历的递归函数
voidInOrder(BTreeNode*&BT);
//中序遍历的非递归函数一
voidInOrder_N1(BTreeNode*&BT);
第3页
//中序遍历的非递归函数二
voidInOrder_N2(BTreeNode*&BT);
//后序遍历的递归函数
voidPostOrder(BTreeNode*&BT);
//后序遍历的非递归函数一
voidPostOrder_N1(BTreeNode*&BT);
//后序遍历的递归函数
voidPostOrder_N2(BTreeNode*&BT);
//层序遍历的非递归函数
voidLayerOrder(BTreeNode*&BT);
//按照二叉树的广义表表示输出整个二叉树
voidGPrintBTree();
//广义表形式输出整个二叉树的递归函数,被函数Print调用voidGPrint(BTreeNode*&BT);
//以凹凸表示法输出二叉树
voidOPrintTree();
/**********************************
叉树
的属性
*****************************
****************计算二叉数深度,宽度,叶子,结点的相关成员函数
****************
//求二叉树的深度
intBTreeDepth();
//用于求二叉树深度的递归函数,被BTreeDepth调用
第4页intDepth(BTreeNode*&BT);
//求二叉树的宽度
intBTreeWidth();
//求二叉树中所有结点数
intBTreeCount();
//用于求二叉树所有结点数的递归函数,被函数BTreeCount调用
intCount(BTreeNode*&BT);
//求二叉树中所有叶子结点数
intBTreeLeafCount();
//用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调
用
intLeafCount(BTreeNode*&BT);
//输出二叉树的所有叶子结点
voidBTreeLeafPrint();
//用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用voidLeafPrint(BTreeNode*&BT);
/***********************二叉树中从根结点到叶子结点的路径相关函数
****************/
//输出从根结点到叶子结点的路径,以及最长路径
voidBTreePath();
//输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用
voidPathLeaf(BTreeNode*&BT,ElemTypepath[],intpathlen);
//求最长路径的递归函数,被函数BTreePaht调用
第5页