实验报告书课程名：数据结构题目：树形数据结构实验（1）班级：学号：姓名：评语：成绩：指导教师：批阅时间：年一、目的与要求1）熟练掌握二叉树的二叉链表表示创建算法与实现；2）熟练掌握栈的前序、中序与后序递归遍历算法与实现；3）熟练掌握前序、中序与后序遍历线索二叉树的基本算法与实现;4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告,并按时提交。二、实验内容或题目1)创建二叉树：广义表式创建与先序创建；2)遍历二叉树：先，中，后，层序遍历，广义表式遍历，凹凸式遍历；3)二叉树属性：深度，宽度，结点数，叶子结点数4)二叉树路径：叶子结点到根结点的路径；5）二叉树线索：中序线索二叉树；6）二叉树置空：清空二叉树。三、实验步骤与源程序1)头文件Btree.h#include#include#include#include#include/**********************************对象--二叉数********************************/第0页typedefcharElemType;//定义元素类型#defineMAXSIZE100//确定二叉树的最大结点数/******************************二叉数的结点类定义******************************/classBTreeNodeprivate:intltag,rtag;//线索标记BTreeNode*left;//左子树指针BTreeNode*right;//右子树指针public:ElemTypedata;//数据域//构造函数BTreeNode()ltag=0;rtag=0;left=NULL;right=NULL;//带参数初始化的构造函数BTreeNode(ElemTypeitem,intltag1,int*left1,BTreeNode*right1)data=item;ltag=ltag1;rtag=rtag1;第1页rtag1,BTreeNodeleft=left1;right=right1;BTreeNode*&Left()//返回结点的左孩子returnleft;//返回结点的右孩子BTreeNode*&Right()returnright;friendclassBinaryTree;//二叉树类为二叉树结点类的友元类/*****************************************************************/classBinaryTreeprivate:BTreeNode*root;public://构造函数.初始化二叉树为空BinaryTree(){root=NULL;}//判断二叉树是否为空boolBTreeEmpty(){returnroot==NULL;}/****************************创建二叉数的相关成员函数***********************///按照二叉树的广义表表示创建二叉树voidCreateBTree1();//递归创建二叉树,被函数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(BTreeN...
