数据结构实验报告树形数据结构实验(1).doc

实验报告书课程名: 数据结构题目: 树形数据结构实验( 1) 班级: 学号: 姓名: 评语: 成绩: 指导教师: 批阅时间:年月日《数据结构》实验报告- 1- 一、目的与要求 1 )熟练掌握二叉树的二叉链表表示创建算法与实现; 2 )熟练掌握栈的前序、中序和后序递归遍历算法与实现; 3 )熟练掌握前序、中序和后序遍历线索二叉树的基本算法与实现; 4 )按照实验题目要求独立正确地完成实验内容(提交程序清单及相关实验数据与运行结果); 5 )认真书写实验报告, 并按时提交。二、实验内容或题目 1) 创建二叉树:广义表式创建和先序创建; 2) 遍历二叉树:先,中,后,层序遍历,广义表式遍历,凹凸式遍历; 3) 二叉树属性:深度,宽度,结点数,叶子结点数 4) 二叉树路径:叶子结点到根结点的路径; 5 )二叉树线索:中序线索二叉树; 6 )二叉树置空:清空二叉树。三、实验步骤与源程序 1) 头文件 #include <> #include <> #include <> #include <> #include <> /********************************** 对象-- 二叉数**************** ****************/ typedef char ElemType; // 定义元素类型#define MAXSIZE 100 // 确定二叉树的最大结点数/****************************** 二叉数的结点类定义******************************/ class BTreeNode { private: int ltag,rtag; // 线索标记 BTreeNode *left; // 左子树指针 BTreeNode *right; // 右子树指针 public: ElemType data; // 数据域// 构造函数 BTreeNode() { ltag=0; rtag=0; left=NULL; right=NULL; } // 带参数初始化的构造函数《数据结构》实验报告- 2- BTreeNode(ElemType item,int ltag1,int rtag1,BTreeNode *left1,BTreeNode *right1) { data=item; ltag=ltag1; rtag=rtag1; left=left1; right=right1; } BTreeNode *&Left() // 返回结点的左孩子{ return left; } // 返回结点的右孩子 BTreeNode *&Right() { return right; } friend class BinaryTree; // 二叉树类为二叉树结点类的友元类}; /********************************** 二叉数的类定义*******************************/ class BinaryTree { private: BTreeNode *root; public: // 构造函数. 初始化二叉树为空 BinaryTree() { root=NULL; } // 判断二叉树是否为空 bool BTreeEmpty() { return root==NULL; } /**************************** 创建二叉数的相关成员函数***********************/ // 按照二叉树的广义表表示创建二叉树 void CreateBTree1(); // 递归创建二叉树, 被函数 CreateBTree1 调用 void Create1(BTreeNode *&BT); // 按一定次序输入二叉树中结点的值( 一个字符), 空格表示空树 void CreateBTree2(int make); // 递归先序创建二叉树, 被函数 CreateBTree2 调用 void Greate2(BTreeNode*&BT,int mark); // 复制二叉树 void BTreeCopy(BTreeNode *&root,BTreeNode *&BT); /**************************** 遍历二叉数的相关成员函数***********************/ 《数据结构》实验报告- 3- // 按任一种遍历次序输出二叉树中的所有结点 void TraverseBTree(int mark); // 用于遍历的递归函数, 被函数 TraverseBTree 调用